アンパンマン将棋 の 完全解析 近畿大学理工学部情報学科 情報論理工学研究室 08-1-037-0094 滝口 直 目次-1（発表の流れ） • アンパンマン将棋とは o o o o 盤と駒 初期配置 進行とゲーム目標 初期配置 • ゲーム理論研究 o o o o 一般的なゲームの総局面数 本研究の目的 どうぶつしょうぎの完全解析手法 アンパンマン将棋の総局面数 目次-2（発表の流れ） • アンパンマン将棋のプログラム o コンピューターAIの手法 o 評価値計算 o クラス説明 • • • • • AI対戦の結果 部分解析 結論 今後の課題 参考文献 「アンパンマンはじめて しょうぎ」とは • 2012年6月28日発売 • 女流棋士の北尾まどか初段 が考案 • 子供向けの将棋 • アンパンマンというキャラ クター性により、人気商品 • イベント開催 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 o o o o アンパン将棋、囲碁、五目並べ、オセロなど 零和＝ゲーム終了時プレイヤー全員の利得合計が一定（０） 有限＝各プレイヤーの可能な手の組み合わせが有限 確定＝不確定要素がない 完全情報＝非公開領域がない • 理論上完全な先読み可能 一般的なゲームの 総局面数 • • • • リバーシ チェス 将棋 囲碁 1028通り、 1050通り、 1069通り、 10170通り • 現在のコンピュータでは解析は不可能 簡略化したゲーム • サイズ 6x6 のリバーシ 16 対 20 で後手勝ち o Joel Feinstein, Amenor Wins World 6x6 Championships!, Forty billion noted under the tree (July 1993), • サイズ 4x4 の囲碁 持碁(引き分け) o 清慎一, 川嶋俊, 探索プログラムによる四路盤囲碁の解, 情報処理学会研究報告, Vol. 2000-GI-004, • サイズ 5x5 の囲碁 黒の 25 目勝ち 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 より どうぶつしょうぎの 完全解析の手法 • 田中哲郎氏, 「どうぶつしょうぎ」の完全解析, 情報処 理学会研究報告 Vol.2009-GI-22 No.3, • 後手78目で勝利 手法 • 全ての局面を列挙 o 初期局面から到達可能な全局面を含んだソート済み配列を作る • 後退解析(retrograde analysis) により必勝法を導き出す o 末端局面集合から始めて、勝敗判定済みの局面集合を増やしていく 総局面数の見積もり • • • • • • アンパンマン バイキンマン 食パンマン ホラーマン カレーパンマン ドキンちゃん 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通り アンパンマン将棋の プログラム • 着手可能手の発見 o 各自駒が各升へいけるか o リーダーの自殺手を除く • 王手の発見 o リーダーが相手のリーダー以外の駒に次の手番で捕られる状況か o 王手をかけられているなら王手から抜け出す手を探す • 勝敗の判定 o 相手リーダーが盤上にいない場合 o リーダーが相手ゴールにいる場合 • 千日手の判定 o 盤上の駒の位置を覚え、前から順番に比較、3回現れたら引き分け • 局面の評価値計算 コンピューターAIの手法 • • • • • 局面の評価値計算 定跡データベース（将棋） 一定手数の先読み 終盤での必勝読み、完全読み モンテカルロ法（オセロ）など 局面の評価値計算 • • • • • • リーダーは前にいるほうが評価は高い 盤面上の駒の数が多いほど高い 着手可能手が多いほど評価は高い 勝利条件を満たすと評価値を無限大 敗北条件を満たすと評価値を無限小 引き分け条件を満たすと評価値を０ クラス説明 • クラスAnpanman o 実行クラス o 将譜の出力 • クラスBoard o 盤を管理 • 駒を実際に移動、駒を取り除くなど • クラスPiece o 駒ためのクラス • 移動方向、初期位置、移動可能な座標など • クラスNextMove o データクラス • 駒の種類、座標位置、評価をセットし返す。 実験の結果 • ＡＩ同士の対戦を 100 回行った • 先手の 33 勝 53 負 14 引き分け アンパンマン将棋の部分 解析 • 1：アンパンマンB４ • 2：バイキンマンB２ • 3：カレーパンマンA４ • A3 B３にきく駒がない アンパンマン将棋の部分 解析* • 初手カレーパンマンA4の 場合も同じ事が言える • 1：カレーパンマンB４ • 2：バイキンマンB２ • 3：アンパンマンA４ アンパンマン将棋の部分 解析* • 初手カレーパンマンA4の 場合も同じ事が言える • 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：食パンマンB5 6：ホラーマンA2 7：食パンマンA５ 8：ホラーマンA３ アンパンマン将棋の部分 解析 • • • • • • • • 1：アンパンマンC４ 2：バイキンマンB２ 3：カレーパンマンB４ 4：ドキンちゃんC２ 5：食パンマンB5 6：ホラーマンA2 7：食パンマンA５ 8：ホラーマンA３ 結論 • AI同士の対戦結果から後手有利と推測する。 • 部分解析から両者最善手を指すと千日手と推測する。 • アンパンマン将棋のプログラムを作成することができ、 完全解析の骨組みを完成させることができた。 今後の課題 • 全ての局面を列挙 o 初期局面から到達可能な全局面を含んだソート済み配列を作る • 後退解析(retrograde analysis) により必勝法を導き出す 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://www03.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] 岸本章宏, 柴原一友, 鈴木 豪, 小谷善行, ゲーム計算メカニズム-将棋･囲碁･オ セロ･チェスのプログラム はどう動く-:pp.21-22, コロナ社, (2010) [20] 田中哲郎,ボードゲーム「シンペイ」の完全解析情報処理学会研究報告 vol. 2006(23), pp.65-72(2006) http://ci.nii.ac.jp/naid/110004683809 [21] 高橋 大介, 佐藤 佳州, 2U-4 モンテカルロ法によるコンピュータ将棋の実現 (ゲーム・知識ベース, 学生セッション,人工知能と認知科学) 全国大会講演論文集 第 70 回平成 20 年(2), "2-123"-"2-124", 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
© Copyright 2024 ExpyDoc
