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

Presentation on theme: "近畿大学理工学部情報学科 情報論理工学研究室 滝口 直"— Presentation transcript:

1 近畿大学理工学部情報学科 情報論理工学研究室 08-1-037-0094 滝口 直
アンパンマン将棋 の 完全解析 近畿大学理工学部情報学科 情報論理工学研究室 滝口　直

2 目次-1（発表の流れ） アンパンマン将棋とは ゲーム理論研究 盤と駒 初期配置 進行とゲーム目標 一般的なゲームの総局面数 本研究の目的
どうぶつしょうぎの完全解析手法 アンパンマン将棋の総局面数

3 目次-2（発表の流れ） アンパンマン将棋のプログラム AI対戦の結果 部分解析 結論 今後の課題 参考文献 コンピューターAIの手法
評価値計算 クラス説明 AI対戦の結果 部分解析 結論 今後の課題 参考文献

4 「アンパンマンはじめてしょうぎ」とは 2012年6月28日発売 女流棋士の北尾まどか初段が考案 子供向けの将棋
アンパンマンというキャラクター性により、人気商品 イベント開催 Official websiteより

5 駒と盤 「アンパンマン、バイキンマン」 前、斜め前、横の５方向 「カレーパンマン、どきんちゃん」 前、斜め前の３方向
　 前、斜め前、横の５方向 「カレーパンマン、どきんちゃん」 　 前、斜め前の３方向 「食パンマン、ホラーマン」 　 縦、横の３方向 ３×５の盤 Oficial websiteより

6 初期配置 ５行目は、アンパンマンの陣地 １行目は、バイキンマンの陣地 アンパンマン、バイキンマンを リーダーとする リーダーを中央
　　　　　　　　　　リーダーとする リーダーを中央 カレーパンマン、どきんちゃん 　　 →リーダーの左側 食パンマン、ホラーマン →リーダーの右側

7 初期配置 ５行目は、アンパンマンの陣地 １行目は、バイキンマンの陣地 アンパンマン、バイキンマンを リーダーとする リーダーを中央
　　　　　　　　　　リーダーとする リーダーを中央 カレーパンマン、どきんちゃん 　　 →リーダーの左側 食パンマン、ホラーマン →リーダーの右側

8 初期配置 ５行目は、アンパンマンの陣地 １行目は、バイキンマンの陣地 アンパンマン、バイキンマンを リーダーとする リーダーを中央
　　　　　　　　　　リーダーとする リーダーを中央 カレーパンマン、どきんちゃん 　　 →リーダーの左側 食パンマン、ホラーマン →リーダーの右側

9 初期配置 ５行目は、アンパンマンの陣地 １行目は、バイキンマンの陣地 アンパンマン、バイキンマンを リーダーとする リーダーを中央
　　　　　　　　　　リーダーとする リーダーを中央 カレーパンマン、どきんちゃん 　　 →リーダーの左側 食パンマン、ホラーマン →リーダーの右側

10 初期配置 ５行目は、アンパンマンの陣地 １行目は、バイキンマンの陣地 アンパンマン、バイキンマンを リーダーとする リーダーを中央
　　　　　　　　　　リーダーとする リーダーを中央 カレーパンマン、どきんちゃん 　　 →リーダーの左側 食パンマン、ホラーマン →リーダーの右側

11 初期配置 ５行目は、アンパンマンの陣地 １行目は、バイキンマンの陣地 アンパンマン、バイキンマンを リーダーとする リーダーを中央
　　　　　　　　　　リーダーとする リーダーを中央 カレーパンマン、どきんちゃん 　　 →リーダーの左側 食パンマン、ホラーマン →リーダーの右側

12 初期配置 ５行目は、アンパンマンの陣地 １行目は、バイキンマンの陣地 アンパンマン、バイキンマンを リーダーとする リーダーを中央
　　　　　　　　　　リーダーとする リーダーを中央 カレーパンマン、どきんちゃん 　　 →リーダーの左側 食パンマン、ホラーマン →リーダーの右側

13 進行とゲーム目標 手番をじゃんけんで決める 先手から交互に１手ずつ駒を動かす。パスは許されない ゲーム目標
チェスと同じゲーム進行 ゲーム目標 相手チームのリーダーを取る（捕まえる） 相手チームの陣地にリーダーが入る（トライ） 千日手（スリーフォールド・レピティション） 同じ局面が３回でた時点で引き分け 「連続王手の千日手」の概念はなし

14 ゲーム理論研究 アンパンマン将棋は二人零和有限確定完全情報ゲーム 二人零和有限確定完全情報ゲーム＝最も単純なゲーム 理論上完全な先読み可能
アンパン将棋、囲碁、五目並べ、オセロなど 零和＝ゲーム終了時プレイヤー全員の利得合計が一定（０） 有限＝各プレイヤーの可能な手の組み合わせが有限 確定＝不確定要素がない 完全情報＝非公開領域がない 理論上完全な先読み可能

15 ゲーム理論研究 アンパンマン将棋は二人零和有限確定完全情報ゲーム 二人零和有限確定完全情報ゲーム＝最も単純なゲーム 理論上完全な先読み可能
アンパン将棋、囲碁、五目並べ、オセロなど 零和＝ゲーム終了時プレイヤー全員の利得合計が一定（０） 有限＝各プレイヤーの可能な手の組み合わせが有限 確定＝不確定要素がない 完全情報＝非公開領域がない 理論上完全な先読み可能

16 ゲーム理論研究 アンパンマン将棋は二人零和有限確定完全情報ゲーム 二人零和有限確定完全情報ゲーム＝最も単純なゲーム 理論上完全な先読み可能
アンパン将棋、囲碁、五目並べ、オセロなど 零和＝ゲーム終了時プレイヤー全員の利得合計が一定（０） 有限＝各プレイヤーの可能な手の組み合わせが有限 確定＝不確定要素がない 完全情報＝非公開領域がない 理論上完全な先読み可能

17 ゲーム理論研究 アンパンマン将棋は二人零和有限確定完全情報ゲーム 二人零和有限確定完全情報ゲーム＝最も単純なゲーム 理論上完全な先読み可能
アンパン将棋、囲碁、五目並べ、オセロなど 零和＝ゲーム終了時プレイヤー全員の利得合計が一定（０） 有限＝各プレイヤーの可能な手の組み合わせが有限 確定＝不確定要素がない 完全情報＝非公開領域がない 理論上完全な先読み可能

18 ゲーム理論研究 アンパンマン将棋は二人零和有限確定完全情報ゲーム 二人零和有限確定完全情報ゲーム＝最も単純なゲーム 理論上完全な先読み可能
アンパン将棋、囲碁、五目並べ、オセロなど 零和＝ゲーム終了時プレイヤー全員の利得合計が一定（０） 有限＝各プレイヤーの可能な手の組み合わせが有限 確定＝不確定要素がない 完全情報＝非公開領域がない 理論上完全な先読み可能

19 ゲーム理論研究 アンパンマン将棋は二人零和有限確定完全情報ゲーム 二人零和有限確定完全情報ゲーム＝最も単純なゲーム 理論上完全な先読み可能
アンパン将棋、囲碁、五目並べ、オセロなど 零和＝ゲーム終了時プレイヤー全員の利得合計が一定（０） 有限＝各プレイヤーの可能な手の組み合わせが有限 確定＝不確定要素がない 完全情報＝非公開領域がない 理論上完全な先読み可能

20 一般的なゲームの 総局面数 リバーシ 1028通り、 チェス 1050通り、 将棋 1069通り、 囲碁 10170通り
リバーシ 通り、 チェス 1050通り、 将棋 1069通り、 囲碁 通り 現在のコンピュータでは解析は不可能

21 簡略化したゲーム サイズ 6x6 のリバーシ 16 対 20 で後手勝ち サイズ 4x4 の囲碁 持碁(引き分け)
Joel Feinstein, Amenor Wins World 6x6 Championships!, Forty billion noted under the tree (July 1993), サイズ 4x4 の囲碁　持碁(引き分け) 清慎一, 川嶋俊, 探索プログラムによる四路盤囲碁の解, 情報処理学会研究報告, Vol GI-004, サイズ 5x5 の囲碁　黒の 25 目勝ち Eric C.D. van der Welf, H.Jaap van den Herik, and Jos W.H.M.Uiterwijk, Solving Go on Small Boards,

22 本研究の目的 アンパンマン将棋はどちらが必勝か、引き分けか 将棋、チェス等の研究に役立つ
アンパンマン将棋は千日手が多く発生する 本将棋 倉庫番ゲーム（コンピューターパズルゲーム）など ループを多く持つ木の探索研究に役立つ アンパン将棋のアプリケーションを作成し、研究の土台を作る AI対戦を可能にし、一人でもゲームをすることができるようにする

23 どうぶつしょうぎ ルール考案者が同じ 幼児用将棋 ３×４の盤 ４種類の駒 捕まえた駒は持ち駒になる 後ろ方へ進める
どうぶつしょうぎ official website より

24 どうぶつしょうぎの 完全解析の手法 田中哲郎氏, 「どうぶつしょうぎ」の完全解析, 情報処理学会研究報告 Vol.2009-GI-22 No.3, 後手78目で勝利 手法 全ての局面を列挙 初期局面から到達可能な全局面を含んだソート済み配列を作る 後退解析(retrograde analysis) により必勝法を導き出す 末端局面集合から始めて、勝敗判定済みの局面集合を増やしていく

25 総局面数の見積もり アンパンマン 15通り バイキンマン 11通り（アンパンマンの隣接におけない） 食パンマン 16通り（盤外＋１）
アンパンマン　　15通り バイキンマン　　11通り（アンパンマンの隣接におけない） 食パンマン　　　16通り（盤外＋１） ホラーマン　　　16通り（盤外＋１） カレーパンマン　13通り（到達できない升が3つ） ドキンちゃん　　13通り（到達できない升が3つ） 15*11*16*16*13*13*2 /2= 7,138,560 総局面数　　　 7,138,560通り 動物将棋　 1,567,925,964通り

26 アンパンマン将棋の プログラム 着手可能手の発見 王手の発見 勝敗の判定 千日手の判定 局面の評価値計算 各自駒が各升へいけるか
リーダーの自殺手を除く 王手の発見 リーダーが相手のリーダー以外の駒に次の手番で捕られる状況か 王手をかけられているなら王手から抜け出す手を探す 勝敗の判定 相手リーダーが盤上にいない場合 リーダーが相手ゴールにいる場合 千日手の判定 盤上の駒の位置を覚え、前から順番に比較、3回現れたら引き分け 局面の評価値計算

27 コンピューターAIの手法 局面の評価値計算 定跡データベース（将棋） 一定手数の先読み 終盤での必勝読み、完全読み
モンテカルロ法（オセロ）など

28 局面の評価値計算 リーダーは前にいるほうが評価は高い 盤面上の駒の数が多いほど高い 着手可能手が多いほど評価は高い
勝利条件を満たすと評価値を無限大 敗北条件を満たすと評価値を無限小 引き分け条件を満たすと評価値を０

29 クラス説明 クラスAnpanman クラスBoard クラスPiece クラスNextMove 実行クラス 将譜の出力 盤を管理
駒を実際に移動、駒を取り除くなど クラスPiece 駒ためのクラス 移動方向、初期位置、移動可能な座標など クラスNextMove データクラス 駒の種類、座標位置、評価をセットし返す。

30 実験の結果 ＡＩ同士の対戦を 100 回行った 先手の 33 勝 53 負 14 引き分け

31 アンパンマン将棋の部分解析 1：アンパンマンB４ 2：バイキンマンB２ 3：カレーパンマンA４ A3　B３にきく駒がない

32 アンパンマン将棋の部分解析* 初手カレーパンマンA4の場合も同じ事が言える 1：カレーパンマンB４ 2：バイキンマンB２

33 アンパンマン将棋の部分解析* 初手カレーパンマンA4の場合も同じ事が言える 1：カレーパンマンA４ 2：バイキンマンB２

34 アンパンマン将棋の部分解析 1：アンパンマンB４ 2：バイキンマンA４ 3：カレーパンマンA４

35 アンパンマン将棋の部分解析 1：アンパンマンB４ 2：バイキンマンA４ 3：カレーパンマンA４ 4：ドキンちゃんB２
ドキンちゃんが前へ進むと

36 アンパンマン将棋の部分解析 1：アンパンマンB４ 2：バイキンマンA４ 3：カレーパンマンA４ 4：ドキンちゃんB２ 5：食パンマンC４

37 アンパンマン将棋の部分解析 1：アンパンマンB４ 2：バイキンマンA４ 3：カレーパンマンA４ 4：ドキンちゃんB２ 5：食パンマンC４

38 アンパンマン将棋の部分解析 1：アンパンマンB４ 2：バイキンマンA４ 3：カレーパンマンA４ 4：ドキンちゃんB２ 5：食パンマンC２

39 アンパンマン将棋の部分解析 1：アンパンマンB４ 2：バイキンマンA４ 3：カレーパンマンA４ 4：ドキンちゃんB２ 5：食パンマンC４

40 アンパンマン将棋の部分解析 1：アンパンマンB４ 2：バイキンマンA４ 3：カレーパンマンA４ 4：ドキンちゃんB２ 5：食パンマンC４

41 アンパンマン将棋の部分解析 1：アンパンマンB４ 2：バイキンマンA４ 3：カレーパンマンA４ 4：ドキンちゃんB２ 5：食パンマンC４

42 アンパンマン将棋の部分解析 1：アンパンマンB４ 2：バイキンマンA４ 3：カレーパンマンA４ 4：ドキンちゃんB２ 5：食パンマンC４

43 アンパンマン将棋の部分解析 1：アンパンマンB４ 2：バイキンマンA４ 3：カレーパンマンA４ 4：ドキンちゃんB２ 5：食パンマンC４

44 アンパンマン将棋の部分解析 1：アンパンマンC４ 2：バイキンマンB２ 3：カレーパンマンB４ 4：ドキンちゃんC２ 5：食パンマンB5
6：ホラーマンA2 7：食パンマンA５ 8：ホラーマンA３

45 アンパンマン将棋の部分解析 1：アンパンマンC４ 2：バイキンマンB２ 3：カレーパンマンB４ 4：ドキンちゃんC２ 5：食パンマンB5
6：ホラーマンA2 7：食パンマンA５ 8：ホラーマンA３

46 結論 AI同士の対戦結果から後手有利と推測する。 部分解析から両者最善手を指すと千日手と推測する。
アンパンマン将棋のプログラムを作成することができ、完全解析の骨組みを完成させることができた。

47 今後の課題 全ての局面を列挙 後退解析(retrograde analysis) により必勝法を導き出す
初期局面から到達可能な全局面を含んだソート済み配列を作る 後退解析(retrograde analysis) により必勝法を導き出す 末端局面集合から始めて、勝敗判定済みの局面集合を増やしていく アプレットを使用したアプリケーション開発

48 参考文献 [1] アンパンマンはじめてしょうぎ, セガトイズ(2012), [2] 岸本章宏, 柴原一友, 鈴木 豪, 小谷善行, ゲーム計算メカニズム-将棋･囲碁･オセロ･チェスのプログラ ムはどう動く-:pp2-20, コロナ社,(2010). [3] 池泰弘, Java 将棋のアルゴリズム:工学社(2007). [4] 池 泰弘, コンピュータ将棋のアルゴリズム―最強アルゴリズムの探求とプログラミング,工学社 (2005) [5] 田中哲郎, 「どうぶつしょうぎ」の完全解析, 情報処理学会研究報告 Vol.2009-GI-22 No.3, pp.1-8(2009), [6] Janos Wagner and Istvan Virag, Solving renju, ICGA Journal, Vol.24, No.1, pp (2001), [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 (2007).

49 参考文献 [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), [9] 清慎一, 川嶋俊, 探索プログラムによる四路盤囲碁の解, 情報処理学会研究報告, Vol GI-004, pp.69-76, (2000), [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 (2003). [11] 日本 5 五将棋連盟, [12] 「ごろごろどうぶつしょうぎ」発売開始！, お知らせ, 日本将棋連盟, 2012 年 11 月 26 日, (2012), [13] 北尾まどか, 藤田麻衣子, どうぶつしょうぎねっと, (2010), [14] IBM100 – Deep Blue, IBM, (1997), [15] Michael Khodarkovsky and Leonid Shamkvoich, 人間対機械－チェス世界チャンピオンとスーパーコ ンピューターの闘いの記録, 毎日コミュニケーションズ, (1998) [16] 伊藤英紀, A 級リーグ差し手 1 号, (2013), [17] 米長邦雄, われ敗れたり コンピュータ棋戦のすべてを語る, 中央公論社, (2012)

50 参考文献 [18] 日本囲碁規約逐条解説 第十二条 [19] 岸本章宏, 柴原一友, 鈴木 豪, 小谷善行, ゲーム計算メカニズム-将棋･囲碁･オセロ･チェスのプログラム はどう動く-:pp.21-22, コロナ社, (2010) [20] 田中哲郎,ボードゲーム「シンペイ」の完全解析情報処理学会研究報告 vol. 2006(23), pp.65-72(2006) [21] 高橋 大介, 佐藤 佳州, 2U-4 モンテカルロ法によるコンピュータ将棋の実現(ゲーム・知識ベース, 学生セッション,人工知能と認知科学) 全国大会講演論文集 第 70 回平成 20 年(2), "2-123"-"2-124", [22] オセロプログラムと人間はどっちが強いのか？ロジステロとの戦い [23] Michael Buro , LOGISTELLO, 2002,