アンパンマン将棋 アンパンマン将棋 のの 完全解析 完全解析

アンパンマン将棋 アンパンマン将棋

の の

完全解析 完全解析

近畿大学理工学部情報学科 情報論理工学研究室

08-1-037-0094 滝口　直

目次 目次 -1 -1 （発表の流れ） （発表の流れ）

•

アンパンマン将棋とは

o

盤と駒

初期配置

o

進行とゲーム目標

初期配置

•

ゲーム理論研究

o

一般的なゲームの総局面数

本研究の目的

o

どうぶつしょうぎの完全解析手法

アンパンマン将棋の総局面数

目次 目次 -2 -2 （発表の流れ） （発表の流れ）

•

アンパンマン将棋のプログラム

o

コンピューター

の手法

評価値計算

o

クラス説明

• AI

対戦の結果

•

部分解析

•

結論

•

今後の課題

•

参考文献

「アンパンマンはじめて

「アンパンマンはじめて しょうぎ」とは

しょうぎ」とは

• 2012

年 6 月

日発売

•

女流棋士の北尾まどか初段 が考案

•

子供向けの将棋

•

アンパンマンというキャラ クター性により、人気商品

•

イベント開催

Official website

より

駒と盤 駒と盤

•

「アンパンマン、バイキンマン」

前、斜め前、横の５方向

•

「カレーパンマン、どきんちゃん」

前、斜め前の３方向

•

「食パンマン、ホラーマン」

縦、横の３方向

•

３ ×５の盤

Oficial website

より

初期配置 初期配置

•

５行目は、アンパンマンの陣地

•

１行目は、バイキンマンの陣地

•

アンパンマン、バイキンマンを

　　　　　　リーダーとする

•

リーダーを中央

•

カレーパンマン、どきんちゃん　　

→リーダーの左側

•

食パンマン、ホラーマン

→ リーダーの右側

初期配置 初期配置

•

５行目は、アンパンマンの陣地

•

１行目は、バイキンマンの陣地

•

アンパンマン、バイキンマンを

　　　　　　リーダーとする

•

リーダーを中央

•

カレーパンマン、どきんちゃん　　

→リーダーの左側

•

食パンマン、ホラーマン

→ リーダーの右側

初期配置 初期配置

•

５行目は、アンパンマンの陣地

•

１行目は、バイキンマンの陣地

•

アンパンマン、バイキンマンを

　　　　　　リーダーとする

•

リーダーを中央

•

カレーパンマン、どきんちゃん　　

→リーダーの左側

•

食パンマン、ホラーマン

→ リーダーの右側

初期配置 初期配置

•

５行目は、アンパンマンの陣地

•

１行目は、バイキンマンの陣地

•

アンパンマン、バイキンマンを

　　　　　　リーダーとする

•

リーダーを中央

•

カレーパンマン、どきんちゃん　　

→リーダーの左側

•

食パンマン、ホラーマン

→ リーダーの右側

初期配置 初期配置

•

５行目は、アンパンマンの陣地

•

１行目は、バイキンマンの陣地

•

アンパンマン、バイキンマンを

　　　　　　リーダーとする

•

リーダーを中央

•

カレーパンマン、どきんちゃん　　

→リーダーの左側

•

食パンマン、ホラーマン

→ リーダーの右側

初期配置 初期配置

•

５行目は、アンパンマンの陣地

•

１行目は、バイキンマンの陣地

•

アンパンマン、バイキンマンを

　　　　　　リーダーとする

•

リーダーを中央

•

カレーパンマン、どきんちゃん　　

→リーダーの左側

•

食パンマン、ホラーマン

→ リーダーの右側

初期配置 初期配置

•

５行目は、アンパンマンの陣地

•

１行目は、バイキンマンの陣地

•

アンパンマン、バイキンマンを

　　　　　　リーダーとする

•

リーダーを中央

•

カレーパンマン、どきんちゃん　　

→リーダーの左側

•

食パンマン、ホラーマン

→ リーダーの右側

進行とゲーム目標 進行とゲーム目標

•

手番をじゃんけんで決める

•

先手から交互に１手ずつ駒を動かす。パスは許されない



チェスと同じゲーム進行

•

ゲーム目標



相手チームのリーダーを取る（捕まえる）



相手チームの陣地にリーダーが入る（トライ）

•

千日手（スリーフォールド・レピティション）



同じ局面が３回でた時点で引き分け



「連続王手の千日手」の概念はなし

ゲーム理論研究 ゲーム理論研究

•

アンパンマン将棋は二人零和有限確定完全情報ゲーム

•

二人零和有限確定完全情報ゲーム＝最も単純なゲーム

o

アンパン将棋、囲碁、五目並べ、オセロなど

o

零和＝ゲーム終了時プレイヤー全員の利得合計が一定（０）

o

有限＝各プレイヤーの可能な手の組み合わせが有限

確定＝不確定要素がない

o

完全情報＝非公開領域がない

•

理論上完全な先読み可能

ゲーム理論研究 ゲーム理論研究

•

アンパンマン将棋は二人零和有限確定完全情報ゲーム

•

二人零和有限確定完全情報ゲーム＝最も単純なゲーム

o

アンパン将棋、囲碁、五目並べ、オセロなど

o 零和＝ゲーム終了時プレイヤー全員の利得合計が一定（０）

o

有限＝各プレイヤーの可能な手の組み合わせが有限

確定＝不確定要素がない

o

完全情報＝非公開領域がない

•

理論上完全な先読み可能

ゲーム理論研究 ゲーム理論研究

•

アンパンマン将棋は二人零和有限確定完全情報ゲーム

•

二人零和有限確定完全情報ゲーム＝最も単純なゲーム

o

アンパン将棋、囲碁、五目並べ、オセロなど

o

零和＝ゲーム終了時プレイヤー全員の利得合計が一定（０）

o 有限＝各プレイヤーの可能な手の組み合わせが有限 o

確定＝不確定要素がない

o

完全情報＝非公開領域がない

•

理論上完全な先読み可能

ゲーム理論研究 ゲーム理論研究

•

アンパンマン将棋は二人零和有限確定完全情報ゲーム

•

二人零和有限確定完全情報ゲーム＝最も単純なゲーム

o

アンパン将棋、囲碁、五目並べ、オセロなど

o

零和＝ゲーム終了時プレイヤー全員の利得合計が一定（０）

o

有限＝各プレイヤーの可能な手の組み合わせが有限

o

完全情報＝非公開領域がない

•

理論上完全な先読み可能

ゲーム理論研究 ゲーム理論研究

•

アンパンマン将棋は二人零和有限確定完全情報ゲーム

•

二人零和有限確定完全情報ゲーム＝最も単純なゲーム

o

アンパン将棋、囲碁、五目並べ、オセロなど

o

零和＝ゲーム終了時プレイヤー全員の利得合計が一定（０）

o

有限＝各プレイヤーの可能な手の組み合わせが有限

確定＝不確定要素がない

o 完全情報＝非公開領域がない

•

理論上完全な先読み可能

ゲーム理論研究 ゲーム理論研究

•

アンパンマン将棋は二人零和有限確定完全情報ゲーム

•

二人零和有限確定完全情報ゲーム＝最も単純なゲーム

o

アンパン将棋、囲碁、五目並べ、オセロなど

o

零和＝ゲーム終了時プレイヤー全員の利得合計が一定（０）

o

有限＝各プレイヤーの可能な手の組み合わせが有限

確定＝不確定要素がない

o

完全情報＝非公開領域がない

•

理論上完全な先読み可能

一般的なゲームの 一般的なゲームの

総局面数 総局面数

•

リバーシ

通り、

•

チェス

通り、

•

将棋

通り、

•

囲碁

通り

•

現在のコンピュータでは解析は不可能

簡略化したゲーム 簡略化したゲーム

•

サイズ

のリバーシ　

対

で後手勝ち

o Joel　Feinstein,　Amenor　Wins　World　6x6　Championships!,　Forty　billion　 noted　under　the　tree　(July　1993),　

•

サイズ

の囲碁　持碁 ( 引き分け

o

清慎一

川嶋俊

探索プログラムによる四路盤囲碁の解

情報処理学会研究 報告

•

サイズ

の囲碁　黒の

目勝ち

o Eric　C.D.　van　der　Welf,　H.Jaap　van　den　Herik,　and　Jos　W.H.M.Uiterwijk,　 Solving　Go　on　Small　Boards,　

本研究の目的 本研究の目的

•

アンパンマン将棋はどちらが必勝か、引き分けか

•

将棋、チェス等の研究に役立つ

o

アンパンマン将棋は千日手が多く発生する

•

本将棋

•

倉庫番ゲーム（コンピューターパズルゲーム）など ループを多く持つ木の探索研究に役立つ

•

アンパン将棋のアプリケーションを作成し、研究の土台を 作る

•AI

対戦を可能にし、一人でもゲームをすることができる

ようにする

どうぶつしょうぎ どうぶつしょうぎ

•

ルール考案者が同じ

•

幼児用将棋

•

３ × ４の盤

•

４種類の駒

•

捕まえた駒は持ち駒にな る

•

後ろ方へ進める

どうぶつしょうぎ official website より

どうぶつしょうぎの どうぶつしょうぎの

完全解析の手法 完全解析の手法

•

田中哲郎氏

「どうぶつしょうぎ」の完全解析

情報 処理学会研究報告

•

後手

目で勝利

手法

•

全ての局面を列挙

o

初期局面から到達可能な全局面を含んだソート済み配列を作る

•

後退解析

により必勝法を導き出 す

o

末端局面集合から始めて、勝敗判定済みの局面集合を増やしていく

総局面数の見積もり 総局面数の見積もり

•

アンパンマン　　

通り

•

バイキンマン　　

通り

•

食パンマン　　　

通り

•

ホラーマン　　　

通り

•

カレーパンマン　

通り

•

ドキンちゃん　　

通り

• 15*11*16*16*13*13*2 /2=　7,138,560

•

総局面数　　　 

通り

•

動物将棋　 

通り

アンパンマン将棋の アンパンマン将棋の

プログラム プログラム

•

着手可能手の発見

o

各自駒が各升へいけるか

リーダーの自殺手を除く

•

王手の発見

o

リーダーが相手のリーダー以外の駒に次の手番で捕られる状況か

王手をかけられているなら王手から抜け出す手を探す

•

勝敗の判定

o

相手リーダーが盤上にいない場合

リーダーが相手ゴールにいる場合

•

千日手の判定

o

盤上の駒の位置を覚え、前から順番に比較、 3 回現れたら引き分け

•

局面の評価値計算

コンピューター

コンピューター AI AI の手法 の手法

•

局面の評価値計算

•

定跡データベース（将棋）

•

一定手数の先読み

•

終盤での必勝読み、完全読み

•

モンテカルロ法（オセロ）など

局面の評価値計算 局面の評価値計算

•

リーダーは前にいるほうが評価は高い

•

盤面上の駒の数が多いほど高い

•

着手可能手が多いほど評価は高い

•

勝利条件を満たすと評価値を無限大

•

敗北条件を満たすと評価値を無限小

•

引き分け条件を満たすと評価値を０

クラス説明 クラス説明

•

クラス

o

実行クラス

将譜の出力

•

クラス

o

盤を管理

•

駒を実際に移動、駒を取り除くなど

•

クラス

o

駒ためのクラス

•

移動方向、初期位置、移動可能な座標など

•

クラス

o

データクラス

•

駒の種類、座標位置、評価をセットし返す。

実験の結果 実験の結果

•

ＡＩ同士の対戦を

回行った

•

先手の

勝

負

引き分け

アンパンマン将棋の部分 アンパンマン将棋の部分

解析 解析

•

1 ：アンパンマン B ４

•

2 ：バイキンマン B ２

•

3 ：カレーパンマン A ４

• A3 　

B ３にきく駒がない

アンパンマン将棋の部分 アンパンマン将棋の部分

解析 解析 * *

•

初手カレーパンマン

の 場合も同じ事が言える

•

1 ：カレーパンマン B ４

•

2 ：バイキンマン B ２

•

3 ：アンパンマン A ４

アンパンマン将棋の部分 アンパンマン将棋の部分

解析 解析 * *

•

初手カレーパンマン

の 場合も同じ事が言える

•

1 ：カレーパンマン A ４

•

2 ：バイキンマン B ２

•

3 ：アンパンマン B ４

アンパンマン将棋の部分 アンパンマン将棋の部分

解析 解析

•

1 ：アンパンマン B ４

•

2 ：バイキンマン A ４

•

3 ：カレーパンマン A ４

アンパンマン将棋の部分 アンパンマン将棋の部分

解析 解析

•

1 ：アンパンマン B ４

•

2 ：バイキンマン A ４

•

3 ：カレーパンマン A ４

•

4 ：ドキンちゃん B ２

•

ドキンちゃんが前へ進むと

アンパンマン将棋の部分 アンパンマン将棋の部分

解析 解析

•

1 ：アンパンマン B ４

•

2 ：バイキンマン A ４

•

3 ：カレーパンマン A ４

•

4 ：ドキンちゃん B ２

•

5 ：食パンマン C ４

• 6 ：ドキンちゃん B3

• 7 ：カレーパンマン B3　

アンパンマン将棋の部分 アンパンマン将棋の部分

解析 解析

•

1 ：アンパンマン B ４

•

2 ：バイキンマン A ４

•

3 ：カレーパンマン A ４

•

4 ：ドキンちゃん B ２

•

5 ：食パンマン C ４

• 6 ：ドキンちゃん A3

• 7 ：カレーパンマン A3　

アンパンマン将棋の部分 アンパンマン将棋の部分

解析 解析

•

1 ：アンパンマン B ４

•

2 ：バイキンマン A ４

•

3 ：カレーパンマン A ４

•

4 ：ドキンちゃん B ２

•

5 ：食パンマン C ２

• 6 ：ドキンちゃん C3

• 7 ：カレーパンマン C3　

アンパンマン将棋の部分 アンパンマン将棋の部分

解析 解析

•

1 ：アンパンマン B ４

•

2 ：バイキンマン A ４

•

3 ：カレーパンマン A ４

•

4 ：ドキンちゃん B ２

• 5 ：食パンマン C ４

• 6 ：ホラーマン B １

• 7 ：食パンマン C ３

• 8 ：ホラーマン C １

アンパンマン将棋の部分 アンパンマン将棋の部分

解析 解析

•

1 ：アンパンマン B ４

•

2 ：バイキンマン A ４

•

3 ：カレーパンマン A ４

•

4 ：ドキンちゃん B ２

•

5 ：食パンマン C ４

•

6 ：ホラーマン B １

•

7 ：食パンマン C ３

•

8 ：ホラーマン C １

•

9 ：食パンマン B ３

• 10

：ホラーマン C ２

• 11

：食パンマン B ２

アンパンマン将棋の部分 アンパンマン将棋の部分

解析 解析

•

1 ：アンパンマン B ４

•

2 ：バイキンマン A ４

•

3 ：カレーパンマン A ４

•

4 ：ドキンちゃん B ２

•

5 ：食パンマン C ４

•

6 ：ホラーマン B １

•

7 ：食パンマン C ３

•

8 ：ホラーマン C １

•

9 ：食パンマン B ３

• 10

：ホラーマン C ２

• 11

：食パンマン B ２

アンパンマン将棋の部分 アンパンマン将棋の部分

解析 解析

•

1 ：アンパンマン B ４

•

2 ：バイキンマン A ４

•

3 ：カレーパンマン A ４

•

4 ：ドキンちゃん B ２

•

5 ：食パンマン C ４

•

6 ：ホラーマン B １

•

7 ：食パンマン C ３

•

8 ：ホラーマン C １

•

9 ：食パンマン B ３

• 10

：ホラーマン C ２

• 11

：食パンマン B ２

アンパンマン将棋の部分 アンパンマン将棋の部分

解析 解析

•

1 ：アンパンマン B ４

•

2 ：バイキンマン A ４

•

3 ：カレーパンマン A ４

•

4 ：ドキンちゃん B ２

•

5 ：食パンマン C ４

•

6 ：ホラーマン B １

•

7 ：食パンマン C ３

•

8 ：ホラーマン C １

•

9 ：食パンマン B ３

• 10

：ホラーマン C ２

• 11

：食パンマン B ２

アンパンマン将棋の部分 アンパンマン将棋の部分

解析 解析

•

1 ：アンパンマン C ４

•

2 ：バイキンマン B ２

•

3 ：カレーパンマン B ４

•

4 ：ドキンちゃん C ２

•

5 ：食パンマン

•

6 ：ホラーマン

•

7 ：食パンマン A ５

•

8 ：ホラーマン A ３

アンパンマン将棋の部分 アンパンマン将棋の部分

解析 解析

•

1 ：アンパンマン C ４

•

2 ：バイキンマン B ２

•

3 ：カレーパンマン B ４

•

4 ：ドキンちゃん C ２

•

5 ：食パンマン

•

6 ：ホラーマン

•

7 ：食パンマン A ５

•

8 ：ホラーマン A ３

結論 結論

• AI

同士の対戦結果から後手有利と推測する。

•

部分解析から両者最善手を指すと千日手と推測する。

•

アンパンマン将棋のプログラムを作成することができ、

完全解析の骨組みを完成させることができた。

今後の課題 今後の課題

•

全ての局面を列挙

o

初期局面から到達可能な全局面を含んだソート済み配列を作る

•

後退解析

により必勝法を導き出 す

o

末端局面集合から始めて、勝敗判定済みの局面集合を増やしていく

•

アプレットを使用したアプリケーション開発

参考文献 参考文献

[1]　アンパンマンはじめてしょうぎ ,　　 セガトイズ(2012),　

http://www.segatoys.co.jp/anpan/product/popup/_legacy/learn/06.html

[2]　岸本章宏 ,　　 柴原一友,　　 鈴木 豪,　　 小谷善行,　　 ゲーム計算メカニズム-将棋･囲碁･オセ ロ･チェスのプログラ

ムはどう動く-:pp2-20,　コロナ社 ,(2010).

[3]　池泰弘,　Java　 将棋のアルゴリズム:工学社(2007).

[4]　池 泰弘 ,　　 コンピュータ将棋のアルゴリズム―最強アルゴリズムの探求とプログラミン グ,工学社

(2005)

[5]　田中哲郎 ,　　 「どうぶつしょうぎ」の完全解析,　　 情報処理学会研究報告 Vol.2009-GI-22　 No.3,　

pp.1-8(2009),　http://id.nii.ac.jp/1001/00062415/

[6]　Janos　Wagner　and　Istvan　Virag,　Solving　renju,　ICGA　Journal,　Vol.24,　No.1,　pp.30- 35　(2001),

http://www.sze.hu/~gtakacs/download/wagnervirag_2001.pdf

[7]　Jonathan　Schaeffer,　Neil　Burch,　Yngvi　Bjorsson,　Akihiro　Kishimoto,　Martin　Muller,　 Robert　Lake,　Paul　Lu,　

and　Steve　Suphen,　Checkers　is　solved,　Science　Vol.317,　No,5844,　pp.1518-1522　 (2007).　

http://www.sciencemag.org/content/317/5844/1518.full.pdf

参考文献 参考文献

[8]　Joel　Feinstein,　Amenor　Wins　World　6x6　Championships!,　Forty　billion　noted　under　the　tree　 (July　1993),　

pp.6-8,　British　Othello　Federation's　newsletter.,　(1993),　http://www.britishothello.org.uk/fbnall.pdf [9]　清慎一,　　川嶋俊,　　探索プログラムによる四路盤囲碁の解,　　情報処理学会研究報告,　Vol.　2000-GI-004,　 pp.69-76,　(2000),　http://id.nii.ac.jp/1001/00058633/

[10]　Eric　C.D.　van　der　Welf,　H.Jaap　van　den　Herik,　and　Jos　W.H.M.Uiterwijk,　Solving　Go　on　Small　 Boards,　

ICGA　Journal,　Vol.26,　No.2,　pp.92-107　(2003).

[11]　日本 5　五将棋連盟,　http://www.geocities.co.jp/Playtown-Spade/8662/

[12]　「ごろごろどうぶつしょうぎ」発売開始！,　　お知らせ,　　日本将棋連盟,　2012　年 11　月 26　日,　 (2012),　

http://www.shogi.or.jp/topics/2012/11/post-652.html

[13]　北尾まどか,　　藤田麻衣子,　　どうぶつしょうぎねっと,　(2010),　http://dobutsushogi.net/

[14]　IBM100　–　Deep　Blue,　IBM,　(1997),　http://www- 03.ibm.com/ibm/history/ibm100/us/en/icons/deepblue/

[15]　Michael　Khodarkovsky　and　Leonid　Shamkvoich,　　人間対機械－チェス世界チャンピオンとスーパー コンピューターの闘いの記録,　　毎日コミュニケーションズ,　(1998)

[16]　伊藤英紀,　A　級リーグ差し手 1　号,　(2013),　http://aleag.cocolog-nifty.com/

[17]　米長邦雄,　　われ敗れたり コンピュータ棋戦のすべてを語る,　中央公論社,　(2012)

参考文献 参考文献

[18]　

日本囲碁規約逐条解説 第十二条

http://www.nihonkiin.or.jp/joho/kiyaku/kiyaku.htm

[19]　

岸本章宏

柴原一友

鈴木 豪

小谷善行

ゲーム計算メカニズム - 将棋･

囲碁･オセロ･チェスのプログラム

はどう動く

コロナ社

[20]　

田中哲郎 ,ボードゲーム「シンペイ」の完全解析情報処理学会研究報告

2006(23),　　pp.65-72(2006)

http://ci.nii.ac.jp/naid/110004683809

[21]　

高橋 大介

佐藤 佳州

モンテカルロ法によるコンピュータ将棋の実

現 ( ゲーム・知識ベース

学生セッション ,人工知能と認知科学

全国大会講演論文集 第

回平成

年

2008-03-13　http://ci.nii.ac.jp/naid/110006865370

[22]　

オセロプログラムと人間はどっちが強いのか？ロジステロとの戦い

http://uguisu.skr.jp/othello/7-2.html

[23]　Michael　Buro　,　LOGISTELLO,　2002,　 https://skatgame.net/mburo/log.html