小さな将棋の解
後藤智章鋼京一友乾併雄小谷新子
東京農工大挙
昭如加割誕里y.ei.加at.ac.jp k-shあa@脳早ei.加at.ac.jp nobU@C児.阻批acお 加知n描∞.加凪ac.jp 概要 将棋割規陸宮勤可非常に大きく、解を求めることは不可能とされている。本海院では、盤を小さくした将 棋の解を求払 J\r-JL4こよる解と罰質量に関して譜諭する。具体的に肱榔こだけ駒を置く配置の 3X3 と 3 X4 の将棋η解を分析しtc.o そ￠梅課、 3X3 は約鎚%、 3X4 は約槌%Cl解を求めることカ時き丸また、 3X3 は負河辺織と後手必勝ぬ哨 2:1 であり、 3X4 は先手~活動略粧品店崎より多いととカめかった。
S
o
l
v
i
n
g
Small 勘ards
o
f
S
h
o
g
i
唄m側面 Gα1'0
Kazu
t
o
m
o
SHIBAHARA
Nobuo 町UI 習油iyukiKOTANI
宮崎o Ui瓜四国産yαfA恒m晶m 血d 古油noo靭Ahø回成
As血噌ba8陶酔瑚lte 四paæ，
n
o
oompu個個n 蜘ep崎町蜘gi.In脳sre鈍四金，鴨 d回伽叫utionof.
t
h
e
s
m
a
l
l
b
o
a
r
d
s
of.血噌， and 也皿 diso踊也edi品開鴎血d 也e 阻醐mtofcalcul甜onbyt
b
.
e
rule. 百e small 晶噌 m伺国也esh噌 d 舗阻d3
x
4
of.arran伊阻倒 by 油i血也epiec四 W鵬PJa:泡d 叫y 岨也.eba吋閤.0佃鱒伊国tly，血也e 個se of 3x3血d 3x4，側6 血d 脚6 of.縦血也mw鵬
fuundre噌舵勘置かMor即V町 it 加medout 伽3x3也凪也era伽of.喧rstmove 羽田"四d
"semnd move
羽田i"areal剛志 2: l.Ittumed 叩t 伽3x4 也at 也ereismore 唱蹴 m腕幅JJS・白血"鎌獄mdmove 訓JJS'.
L はじめに 将棋崎務ゑ先高凶勝・後事凶勝・引き分けの，、 ずれかであるが、状態聾習倒開に大きいととから 解を求める乙とは不可能とされている。オセロ、囲 碁、 E也x[11なEでは盤ηサイズを小さくした場合の 解を求める研究カ守封オ1ている凶。小さ1J:ft臨海降 求める研掬ま、より犬きな盤叫弊を求める研掬こ役 立てられる。一志将償では語格働問蹄砲お払に 行われているカえ盤のサイズを小さくし:問笥患部こ関 してはあまり議論されてb堆い。そこで、本穆院で 6謡腕:/J、さくした将棋明揮を或め、 ，\r-Mこよる解 の分析特f質量などに関して議論する。 龍文の構成島処のようになる。第2 鮒割割i1(O)Jレ ールと関適時売を示し、第3 即で小さな将棋初レー ルを示す。第 4 蜘鯨アルゴリズムを示Lへ第 5 鮒空実酬醐提示す。更に第6 町では千日手姐躍を 加えたアルゴリズムでZ旗甥提示す。第 7 鮒で考察 を示し、最働こ第 8 町でまとめを行う。 2. 将棋のルサレと閲遅曹隣 将棋ま、駒を観的、すタイプのゲームであり、玉を 詰めることを目的とする。その他こも特徴前脚\r ルとして、持ち駒η再事閥、駒η成り、道統王手の 千日手の禁止などがある。 一次元将棋問解は、文 縦訓[4]の鰍『ある。また、苅闘では今後崎砲 として「将棋倒、さなモヲ切羽輸を求める」とと を上げている。 &小さな将棋の!1\r-ル 3.1 本将棋との趣，、 本将棋と遣うJト1レにできるものとして次のもの を扱う。
・
蝿のサイズ￠漉吏
・ 成れる闘の変更(例えば、本将棋を r3J と し、端でしか成れない場合を rlJ とする) ・ 拒開局面ぬ蜘刀変更 また、揖擦中は王を取られる手も生成して、候補 手に王を取る手が:t>tù:J勝ちとしている。8.2拒開局面 次の図は、実験で用いた 2 種類￠躍である。
3 2 1
3 2 1
IZ川川 XI 一I
Z
IY ロ1-I
X
I
Y
I
Z
I ニ I I ユI
x
I
~ぺ zl 四 図 1 3X3 図 2 3x4 x、 y、 z に王・飛・角・金・銀・桂・香・歩・駒 無しを商量する。お互いの手掛こ関して、王は 1 枚、 飛・角・厳撫しはト1 枚、伽まか4 枚としteo 王 が中心となる局面の内、験的噛Tであっても対象な局 面は片方だけとした。また、最初から王に利きがあ る局面も存在する。蹴lる駒れ、 2、 3 の各場合で 試した。全部?亡。弱4 ルーサレである。 4 探索アルゴリズム システムに αH揮擦と PDS の拐捺アルゴリズム を導入した。次にそれぞれのアルゴリズムι禍犠と 導入方法を示す。 ω αH拐調副+反復測ヒ+甘 JJ，- トでだけ反復探化する αH探素である。評価 関数は駒価値だけの脇、ものを手l聞した。到】S と比 べて αH拐擦は、明画や手数などを調べることに有 妨であると尉つれる。またトランスポジションテ ープル似1三官)を使用しteo Tl'には評価値と 最善手を書き込む。Tl'に∞0'ã手必勝)かー∞機 手必勝)カ清かれているか、齢、事醸をしたことが ある場合はTl'の制面値をすぐに返すようにし丸 候補手の1回予付けとしては、まずはTl'に前回探 索時の最善手カ時再Eすれ』藷麹Bこ揮紫する。それ以 臨ま、一手先読みした局面の開園債で並べ替えを行 う。Tl'に登録された評価直は、並べ替えのヒント にはしていなし、。 ω PDS[6]+優越関倒7]+翻崩姐7]+反証駒[8] 翻月数・反誼淵9] とハッシュを利用した多重反複 湖国まである。今回は優越閥系と都月肱反誼跡こ より高漣化したものを使用している。 PDS は、 αH 掃索と比べて真偽を速く静てるのに有効であると思 われる。 なお、最新の証明数探索のアルゴリズムとして 飾品]も発表されているが、千日手の処理柿練 であるた臥今回は導入しなかった。5
.
αH と R聞による実験結果 5.1 実鵬環境 刊は 221エントリ(オ」プンアドレス齢、僧服 時間 1 間 1 分、制艮ノード数 1 間224 ノード、深さ2
10(αH は深さのしき川直、 PDS は達した深さ) で打ち切るものとして、各アルゴリズムで掠擦を行 つ丸 os は Wm伽'wsXP
PrI:企舗.onal， CPU は P回出血.42.8G砲である。なお、 τT の夜開佑計m 題ごとに行うが、これは計算時間に含めないことに した。 羽月o)()内は強制限寸の白方で、臨~dl ノード、 深さの順である。表の不正局面とは、核開局面で先 手嶋附肝玉に利きがある問題である。以下、不 正局面は省いて議論することにする。 3X3 の場合は、 αH ・目)8持こ約 9 曾拘問題を 解くことカ干でき、餌?た陪題のうち先手必勝と後手 必勝は約 2:1 であった。 3X4 の場合は、 αH の場合 嚇句 3 甑 PDS の場合4誠司 5 割の問題を解くこと ができ、ほとんどカ明手必勝であった。 6.S ルールと結果的新 図 3 は 3X3 における、 αH と PDSι蔵院清掬こ よる結果を分析したものである。同じ践が 2 枚ある 問題を省いた 63 題で封載し九 3X3 では、ほとん どの陪題を解くことができたが、駒カ場除、場合と歩 がある場合に解けないことカt多く見られた。 図 4 は 3X4 での図 3 と同様のグラフである。 3 X4 の場合は、践的環レ場合と銀がある場合に締ナ ないことカ事く見られた。一方、桂馬と角がある場 合は解けることカゆかった。 図 5 は 3X4 で αp と PDSι尉鍔時閣を此殺した ものである。両方て鳴紛却現町三けで民載した。こ のグラフから αH より PDS の方制生駒滴いこと がわかる。また、言博事時聞が多くかかる問題ほど PDS の方が大きく高速である傾向があった。値帽畠 9
・抽信銀傘角血晴繍時晴噂端会角
ma
吋吋吋吋吋吋吋聞
mmmmm
…mm
02040ω 図 3 3x3 における腐の有綿こよる結果の分布川市川川崎噌団地鳩山明繍暗暗噌咽噌輔繍
叫叫叫叫叫川川川町内陣内聞開閉開閉
o 20 40 80 図 4 3X4 に制する腐の有綿乙よる結果の分布 1制施。 10 10ω 1000 10倒掬a
6
(ma80) 図 5 3X4 に制沌 aß と軍関明f算時間の比鍛 表 8 ・表 4~~ PDS の成れる駒こよる商務?た教と ノード数の此搬「である。本将棋の成樹ま r3J で、 6. 千日手処趣明導入と実離結果 6.1 千日手のJトルと闘溜附軍 将棋η千日手:lL-Mま、同一局面を 4 回繰り返す と千日朝3] とされている。また、道帯証手の千日手 は熱kである。翻粥唐使っ地籍貯の千日手￠施 理としては[9]、 [1叫、 [1泊などで示されている。 6.2千日手の姐趨 千日手を考慮する場合、 TT に事即するハッシュ コードにZ軒瞭情動唱ないた払正しし鳴礎得られな いことがある。そこで、揮擦に αH揖擦を利用し、 官の最善手を究溺こすることにだけ'町制周す るととにする。 今回描去の局面一致仰民識に切でも手l聞し ている局面コードを用いる。局面コードは、盤面の ハッシュコード 6制、先手持ち駒コード鑓協、後 手持ち駒コード 3助託保十 1創出である。者探さご とに局面コードを記憶し、避去に一致する局面のチ ェックによって千日手俳l胞を行うととにする。 「千醇捌好の勝ち」という探掠と「千日朝ま 先手ι調書ち」という 2 種類棚隠静~iうととbこする。 解カ事掠ってい制ff日手とする。なお、一咽同一 局面手が尉吋千日手として、遅続王手の千日朝ま 鞠こ執kとし;なし、時間な1!.o:.滞臨ま 5.1 と同様だ が、 2 回仰栂間リ々に僧j限した。6
.
8
千日手司自民の実鵬結果 千日手判定靖りで αH揖療を行った結果表 5 の ようになったゐ 3X3 の場合は 15 患 3X4 の場合は 4 題ゐ汗日手として寺町民され九利回は全て、暗闇 棚京驚了したものである。図 6 は千日手綱提の有鰯こよる αHの蹴腕示すグラフであるu 千日手判 定を行った方が、言惇軽叡舟動目することが恥かる。 表5 千日苧拘臨有りの aßの結果
￨
除手必勝降手必鶴|平日J手陣明係正陣針 lh
X
3
1
11~
珂
1司~
8~ 28~
h
X
4
1
吋
q
~ 1叫咽捌
10000 1似悶T
CIQ，∞ 也叫m
-h•
10 10 100 1000 10000 遺常の α ß(ノード} 図 6 3x3 における千日手申鹿併掬ζよる民鍛 7. 考察 3X3 の場合bゑ後手玉に利きjJ精レ 195 題の内、 1回題を解くととカ?できた与先毛凶闘が 119、後手 必勝が路、千日手が 15 である。 3X3 の場合は、ほ とんど僻轟酸 1 秒以内に解くことカ守きた机解 くのに時間のカ功、る問題も存在し丸 3X4 ι場合怯後手Bこ利きカ明恥、 237 題の内、 133 題を解くことカ干できt~ 先手E暢が 127. 後手 必鴫が 2、千日手が 4 である。と￠潟県少なくと も先手指勝カ寝も多いことカめかった与また、 αH よりも優越関係や証鴫峻加えた PDS の方が何 方碍格?た陪題の比の中央官で)約 4.6 価高速であ っ色調事慣e発展した手話;JA とのような小さな 将棋倒鞍求めることにおいても有斑ほょうである。 PDS で伸?なかった陪盾では、バpート局面で￠駈 峡敵・反誼致問階に大きくなることがあった。こ のような問題は、 DAG による証明数同二重罰賞や 千日手などカ官習であると思われるので、今後改善 したし、。 謝1る隈を変えた結県蹴1る駒，~ 1 の場合に解 くのカ灘し川離制見られた。しかし、成り・不成 りのチャンスが増えるとそれ泊7候補手カ噌えるの で、計質量カ糟えることカ噌えられたゐおそらく、 謝1る段を強く締思すると千日手に陥る局面が増え るととから、解くのカ灘しくなることカ噂餌jできる。 今後￠糊題として、 3X4 の有明解である局面的解 を求めること、より難しい問題を解くこと、探察ア ルゴリズムの性飽向上をすることが上げられる。a
おわりに 本輸では、小さな将棋η解として 3X3 と 3X4 の 将榔糊鵠牙、した。と倒防羽鯨アルゴリズム の研殉こなるばかりではなく、ゲームのyト11A7:瀞 析にも役立τ栂院となるであろう。 参考文献 [1]鈴木義乾併肱小谷智子 :Hex ゲームを 解く，開轍告ゲーム情報学\ No.佃7- ∞1 .情 報処理学会。∞'2).[
2
]
H
e
r
i
k
.
H
.
J
.
van 曲1.J
.
U
it
e
r
w
i
j
k
.
a
n
d
J
.
v
a
n
R
i
j
s
w
i
j
c
k
:
G銅es So lv剖伽制 in t陥 Futw'e.A
r
t
i
f
i
c
i
a
l
lntellis肌eJ
o
o
m
a
l
1
3
4
:
p
p
.
2
7
7
-
3
1
2
.
(
2
0
0
2
)
.
[3] 制京仁:将棋η数学的世民卯. ]-]6. 将棋と コンピュータ(]舶の. [4] 株去一部:将棋明器命とグラフ理論Itp
p
.
71か75. コンピュータ将棋協会誌 Vol. 1O(]四η. [司 D.E. 加th 副R. W. 蜘陀:加畑lysiso
f
Alp凶-BetaP
n
m
i
n
g
.
A
r
t
i
f
i
c
i
a
l
I
n
t
e
l
l
ig眠e6(4).p
p
.
2
9
3
-
3
2
6
(
1
9
7
5
)
.
[
6
]
A
ytDIIIlN，郁i:
A
誣
A
N
D
/
O
R
Tn田 S回rchA
I
g
o
r
i
t
h
m
USÍJゆ1)()f 畑berar凶 Disproof Number. Canpl似 GamesL油 Worksmp.p
p
.
4
0
-
4
5
.
10 恥V四ber(
]
9
9
8
)
.
[η 脊尾昌宏:翻暁賠解くアルゴリズムにおける 優越調係の殻痢掠手l聞について，第 5 回ゲーム プログラミングワークショップ.p
p
.
1
2
9
-
1
3
6
(]卿，). [8] 長井歩，今井浩: df担アルゴリズム係繍 棋を解くプログラムへのF諒H. ジャーナルアブス トラクト Vol. 43 恥.田ー 020. 情報処理学会 (2∞12).[凶Louis
V
.
A
I
I
i
s
.
Maart印 vand
e
r
Meu l四，制H.Jæpv加 d四恥rik: Pr∞f-畑出rS回rch. 除port
