将棋
（将棋/26歩から転送）
この研究室では将棋を研究しています。
本将棋
[編集]△後手 なし
| 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | |
| 香 | 桂 | 銀 | 金 | 王 | 金 | 銀 | 桂 | 香 | 一 |
| 飛 | 角 | 二 | |||||||
| 歩 | 歩 | 歩 | 歩 | 歩 | 歩 | 歩 | 歩 | 歩 | 三 |
| 四 | |||||||||
| 五 | |||||||||
| 六 | |||||||||
| 歩 | 歩 | 歩 | 歩 | 歩 | 歩 | 歩 | 歩 | 歩 | 七 |
| 角 | 飛 | 八 | |||||||
| 香 | 桂 | 銀 | 金 | 玉 | 金 | 銀 | 桂 | 香 | 九 |
▲先手 なし
将棋の初期局面（平手）
基本的な性質
[編集]- 将棋は二人零和有限確定完全情報ゲームです。
- 将棋は先手必勝、後手必勝、引き分けのいずれかです（ツェルメロの定理）。
- パスできれば将棋は先手必勝または引き分けです（strategy-stealing argument）。
- n×nの将棋が先手必勝かどうかを判定する問題はEXPTIME完全です[1]。
- 1983年5月[要出典]、千日手の成立条件が「同一手順3回」から「同一局面4回」に変更されました。従来のルールでは将棋は無限ゲームです（Thue–Morse sequence）[2]。
- ステイルメイトは詰みかどうか（打ち歩ステイルメイトは打ち歩詰めか）は規定されていません。
- 連続王手の千日手となる逆王手でしか王手を解除できない局面は詰みかどうか（打ち歩の王手でそのような局面にすることは打ち歩詰めか）は規定されていません（最後の審判）。
- 双方連続王手の千日手は起こらないと予想されていますが、完全な証明は知られていません[3][4]。
- 将棋は先手必勝、後手必勝、引き分けのいずれかです（ツェルメロの定理）。
- 将棋の局面数（state-space complexity）Lは、4.65 × 1062 < L < 9.14 × 1069を満たすことが証明されており、1068〜1069と予想されています[5][6]。
- 将棋の棋譜数（game-tree complexity）は、平均合法手数が約80通り、平均手数が約115〜125手なので[7]、80115 ≈ 10220と下限が推定されています[5][8]。
- 将棋の初期局面は7手すきです[9]。
perft
[編集]チェスでは、ある局面（特に初期局面）からn手目までの指し手の組合せの総数はperftと呼ばれます[10][11][12]。
将棋の初期局面では、初手は30通り、2手目までは30 × 30 = 900通りで、3手目以降は次のようになります[13][14]。
| 深さ | ノード数 | 取る手 | 成り | 王手 | 詰み |
|---|---|---|---|---|---|
| 0 | 1 | 0 | 0 | 0 | 0 |
| 1 | 30 | 0 | 0 | 0 | 0 |
| 2 | 900 | 0 | 0 | 0 | 0 |
| 3 | 25470 | 59 | 30 | 48 | 0 |
| 4 | 719731 | 1803 | 842 | 1121 | 0 |
| 5 | 19861490 | 113680 | 57214 | 71434 | 0 |
| 6 | 547581517 | 3387051 | 1588324 | 1730177 | 0 |
| 7 | 15086269607 | 156289904 | 78496954 | 79636812 | 29 |
| 8 | 416062133009 | 4713670699 | 2222896064 | 2047229309 | 3420 |
| 9[15] | >11661472222632 | >192307327995 | >96264455880 | >83245184398 | 657904 |
| 10[16][17] | >328508718203382 | >5991530109830 | >2853105172082 | >2310279117871 | 42154478 |
| 11 | 3.95 × 109[18] |
最多合法手局面
[編集]△後手 金3桂3歩17
| 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | |
| 飛 | 一 | ||||||||
| 玉 | 銀 | 銀 | 銀 | 王 | 二 | ||||
| 角 | 三 | ||||||||
| 四 | |||||||||
| 五 | |||||||||
| 六 | |||||||||
| 七 | |||||||||
| 八 | |||||||||
| 香 | 香 | 香 | 九 |
▲先手 飛角金銀桂香歩
合法手が最多（593通り）の局面
一つの局面の合法手の数の最大値は593で、合法手が最多の局面は左右反転、同じ種類の持ち駒の数の違いを除いて、一通りに定まることが証明されています[19][20][21][22]。
利かずの駒並べ
[編集]駒落ち
[編集]香落ち
[編集]角落ち
[編集]飛車落ち
[編集]二枚落ち
[編集]太閤将棋
[編集]△上手 なし
| 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | |
| 香 | 桂 | 銀 | 金 | 王 | 金 | 銀 | 桂 | 香 | 一 |
| 飛 | 角 | 二 | |||||||
| 歩 | 歩 | 歩 | 歩 | 歩 | 歩 | 歩 | 歩 | 三 | |
| 四 | |||||||||
| 五 | |||||||||
| 六 | |||||||||
| 歩 | 歩 | 歩 | 歩 | 歩 | 歩 | 歩 | 歩 | 歩 | 七 |
| 角 | 飛 | 八 | |||||||
| 香 | 桂 | 銀 | 金 | 玉 | 金 | 銀 | 桂 | 香 | 九 |
▲下手 なし
太閤将棋の初期局面
△8七飛成▲7六歩△8二竜▲2六歩△8六歩で上手優勢になります[24]。
四枚落ち
[編集]六枚落ち
[編集]八枚落ち
[編集]十枚落ち
[編集]△上手 なし
| 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | |
| 王 | 一 | ||||||||
| 二 | |||||||||
| 歩 | 歩 | 歩 | 歩 | 歩 | 歩 | 歩 | 歩 | 歩 | 三 |
| 四 | |||||||||
| 五 | |||||||||
| 六 | |||||||||
| 歩 | 歩 | 歩 | 歩 | 歩 | 歩 | 歩 | 歩 | 歩 | 七 |
| 角 | 飛 | 八 | |||||||
| 香 | 桂 | 銀 | 金 | 玉 | 金 | 銀 | 桂 | 香 | 九 |
▲下手 なし
十枚落ちの初期局面
歩三兵
[編集]裸玉（十九枚落ち）
[編集]△上手 なし
| 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | |
| 王 | 一 | ||||||||
| 二 | |||||||||
| 三 | |||||||||
| 四 | |||||||||
| 五 | |||||||||
| 六 | |||||||||
| 歩 | 歩 | 歩 | 歩 | 歩 | 歩 | 歩 | 歩 | 歩 | 七 |
| 角 | 飛 | 八 | |||||||
| 香 | 桂 | 銀 | 金 | 玉 | 金 | 銀 | 桂 | 香 | 九 |
▲下手 なし
裸玉（十九枚落ち）の初期局面
20手で下手勝ちであることが証明されています[26][27]。
平安将棋
[編集]△後手（持ち駒ルールなし）
| 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | |
| 香 | 桂 | 銀 | 金 | 王 | 金 | 銀 | 桂 | 香 | 一 |
| 二 | |||||||||
| 歩 | 歩 | 歩 | 歩 | 歩 | 歩 | 歩 | 歩 | 歩 | 三 |
| 四 | |||||||||
| 五 | |||||||||
| 六 | |||||||||
| 歩 | 歩 | 歩 | 歩 | 歩 | 歩 | 歩 | 歩 | 歩 | 七 |
| 八 | |||||||||
| 香 | 桂 | 銀 | 金 | 玉 | 金 | 銀 | 桂 | 香 | 九 |
▲先手（持ち駒ルールなし）
平安将棋（9×9と仮定した場合）の初期局面
後手は先手の指し手を線対称に真似すれば負けないことが知られています[28][29][30]。
チェス
[編集]引き分けと予想されています。
はさみ将棋
[編集]△後手
| 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | |
| と | と | と | と | と | と | と | と | と | 一 |
| 二 | |||||||||
| 三 | |||||||||
| 四 | |||||||||
| 五 | |||||||||
| 六 | |||||||||
| 七 | |||||||||
| 八 | |||||||||
| 歩 | 歩 | 歩 | 歩 | 歩 | 歩 | 歩 | 歩 | 歩 | 九 |
▲先手
はさみ将棋の初期局面
千日手になると考えられています。
ミニ将棋
[編集]ごろごろどうぶつしょうぎ
[編集]
5五将棋
[編集]
どうぶつしょうぎ
[編集]
完全解析されており、78手で後手勝ちとなります[33]。
考案者の北尾まどかによれば、ひよこ不成は合法手です[34]。
アンパンマン はじめてしょうぎ
[編集]| ホ | ば | ド |
| カ | ア | し |
完全解析されており、千日手で引き分けとなります[35][36]。
9マス将棋
[編集]3三将棋
[編集]| △後手 銀歩 | ||
|---|---|---|
| 王 | ||
| 玉 | ||
| ▲先手 銀歩 | ||
完全解析されており、27手で先手勝ちとなります[39][40][41][42]。
脚注
[編集]- ↑ 安達ら 1987。
- ↑ 田中 2013。
- ↑ 林 1997。
- ↑ 2008年にやねうらお[1][2][3][4]、やまいも[5][6]が証明を試みていますが、いずれも不備が指摘されています。
- ↑ 5.0 5.1 篠田 2008。
- ↑ コンピュータ将棋基礎情報研究所: 将棋の局面数 1: 局面数は無量大数
- ↑ 松原・半田 1994。
- ↑ コンピュータ将棋基礎情報研究所: 将棋の棋譜数: "10の220乗" 説の真相!?
- ↑ ▲2六歩▲2五歩▲2四歩▲2三歩成▲2二と▲3一との6手で詰めろがかかります（▲4一と以下、（1）△同玉は▲2一飛成△5二玉▲3二竜△5一玉▲4一金まで7手で詰み、（2）△5二玉は▲2二飛成△4一玉▲2一竜以下同様に9手で詰み、（3）△6二玉は▲2二飛成△5二金▲同竜△同玉▲5一金△6二玉▲5二金打△7二玉▲6一銀まで11手で詰み）。
- ↑ Chess Programming Wiki: Perft
- ↑ Chess Programming Wiki: Perft Results
- ↑ OEIS: A048987: Number of possible chess games at the end of the n-th ply
- ↑ @ak11: 将棋でPerftしてみたまとめ
- ↑ やねうら王 公式サイト: 将棋でPerftしてみたまとめのまとめ
- ↑ やねうら王 公式サイト: 将棋におけるperftの世界記録を更新中
- ↑ やねうら王 公式サイト: perft 10終わった
- ↑ やねうら王 公式サイト: perft10の結果が間違っていた!?
- ↑ 『Web Fairy Paradise』第107号、p. 65。
- ↑ 野崎 1990、ページ数不明。
- ↑ 篠田 1999。
- ↑ State of the Digital Shogics [最先端計数将棋学]: 最多合法手局面
- ↑ コンピュータ将棋基礎情報研究所: 一局面の合法手の最大数が593手であることの証明
- ↑ 松元隆二: 利かずの駒並べの全解探索
- ↑ 鈴木 1999。
- ↑ GodwhaleChild 5.0.5 + QQRなどのソフトで、Hashを20GBほど確保し、MultiPV = 14でShogiGUIの検討モードを使用し、上手のすべての合法手に対して、下手▲7八飛▲7六歩▲7五歩▲同歩（△1六歩〜△9六歩を突いてきた場合）▲7六飛…のような手順を入力することにより、初期局面で「先手勝ち（詰み 32手）」と表示されます。
- ↑ @math26: "命題：19枚落ち（上手王のみ）は20手以内に下手が勝つことが可能である。証明：下手が偶数手目に78飛76歩75歩74歩73歩成72と73飛成33角成と指せば、17手目に上手玉がどこにあっても残り3手で詰みである。 http://t.co/My6LajzBl5"
- ↑ @SuzukiShogi: "自作プログラムで検証した結果62085秒で「不可能」と答えました。 RT @math26 問1. 19枚落ち（上手は玉のみ）は20手以内に下手が勝つことが知られていますが、これを「18手以内」に縮めることは可能でしょうか。"
- ↑ 旦代 1997。
- ↑ 飯田ら 1998。
- ↑ 佐々木ら 2000。
- ↑ 柴原ら 2005。
- ↑ 柴原ら 2006。
- ↑ 田中 2009。
- ↑ @nemurineko: "@Goryudyuma はい。ひよこ成らずは合法手です。どうぶつしょうぎは動き間違いや二手指しを除いて、反則は基本的にありません。"
- ↑ 塩田ら 2013。
- ↑ 5ちゃんねる 将棋・チェス板: 【アンパンマンはじめてしょうぎ】を攻略したい
- ↑ 後藤ら 2003。
- ↑ 南雲 1980。
- ↑ キリル・クリュコフ・山田琢磨 2003。また、考案者の南雲夏彦によっても必勝手順が知られていたとされます[7]。
- ↑ あんちっく: 3三将棋の必勝法（あんちっく検証）
- ↑ 5ちゃんねるの関連スレッド[8][9][10][11][12][13][14]
- ↑ 2ch名人: 3×3将棋、どちらが勝つ?
参考文献
[編集]- 安達博行、亀川裕之、岩田茂樹「n×n盤面上の将棋の指数時間完全性について」、『電子情報通信学会論文誌』第J70-D巻第10号、1987年、pp. 1843-1852。
- 飯田弘之、吉村仁、森田和郎、Jos W. H. M. Uiterwijk「Retrograde Analysis of the KGK Endgame in Shogi: Its Implications for Ancient Heian Shogi」、『Lecture Notes in Computer Science』第1558巻、シュプリンガー・フェアラーク、1999年、pp. 167-182。
- 後藤智章、柴原一友、乾伸雄、小谷善行「小さな将棋の解」、『ゲームプログラミングワークショップ2003論文集』、pp. 25-32。
- 佐々木宣介、梶原羊一郎、飯田弘之「平安将棋の終盤戦の数理解析」、『日本応用数理学会論文誌』第10巻4号、2000年、pp. 327-334。
- 塩田好、石水隆、山本博史「「アンパンマンはじめてしょうぎ」の完全解析」、『2013年度 情報処理学会関西支部 支部大会 講演論文集』。
- 篠田正人「将棋における最大分岐数」、『コンピュータ将棋協会誌』第12巻、1999年、pp. 57-58。
- 篠田正人「将棋における実現可能局面数について」、『情報処理学会シンポジウムシリーズ』第2008巻第11号、pp. 116-119。
- 柴原一友、但馬康宏、小谷善行「小さな将棋の解を得る手法の提案」、『ゲームプログラミングワークショップ2005論文集』第15号、pp. 134-137。
- 柴原一友、但馬康宏、小谷善行「引き分けの証明向きのGHI問題対処法とその3x4将棋への応用」、『情報処理学会論文誌』第47巻12号、2006年、pp. 3328-3342。
- 鈴木宏彦『81枡物語: 盤上に輝く忘れられぬ局面』島朗協力、毎日コミュニケーションズ、1999年。ISBN 978-4-8399-0126-4
- 田中哲朗「「どうぶつしょうぎ」の完全解析」、『情報処理学会研究報告』第2009-GI-22巻第3号、pp. 1-8。
- 田中哲朗「ゲームの解決」、『数学』第65巻第1号、日本数学会、2013年、pp. 93-102。
- 旦代晃一「平安将棋の謎 (2)」、『詰棋めいと』第24号、詰将棋研究会、1997年、pp. 70-71。
- 南雲夏彦「3三将棋と駒成将棋」、『カピタン』第20号、加藤徹編、現代将棋研究会、1980年、p. 14。
- 野崎昭弘『ロジカルな将棋入門』筑摩書房、1990年。ISBN 978-4-480-05141-7
- 林忠一郎「将棋の結論とグラフ理論」、『コンピュータ将棋協会誌』第10巻、1997年、pp. 70-75。
- 松原仁、半田剣一「ゲームとしての将棋のいくつかの性質について」、『情報処理学会研究報告』第1994-ICS-096巻第83号、pp. 21-30。
