ガイスターの初期盤面における相手駒推定の有効性

(1)

ガイスターの初期盤面における相手駒推定の有効性

栃川純平

1

_竹内聖悟

2 概要：ガイスターは，相手の駒の色がわからない二人不完全情報ゲームである．ガイスターにおいて推定を行うプレイヤーの開発がされてきたが推定に関する基本的なデータが知られていなかった．データから推定の方針を示すことができれば，ガイスタープレイヤー開発に役立てることができる．本研究ではその方針を得るため，推定する駒の数や色，配置，推定精度に着目し，重視すべき特徴について調査を行った．重視すべき特徴を得るために，実験では初期盤面から対戦を行った．片方のプレイヤーは相手の駒色を知っており，もう片方のプレイヤーはそうでない状況で対戦させ，勝率の変化などを調べた．実験の結果，推定する駒数が多いほど勝率が良く，推定精度が高いほど勝率が良いことが確認できた．MCでは推定精度が60%でも効果があることが確認できた．また，重視すべき特徴として青駒よりも赤駒を推定する方が有効であることが得られた．

Eﬀectiveness of estimating opponent piece color

on initial position in Geister

JUNPEI TOCHIKAWA

1

SHOGO TAKEUCHI

2

Abstract: Geister is a two-player imperfect information game in which the colors of the opponent’s pieces

are unknown. Although players have been developed to perform estimations in Geister, the basic data on estimation were not known. If we can show a policy of estimation from the data, it can be useful for Geister player development. In this study, we focused on the number and color of estimation pieces, their placement, and estimation accuracy. In order to obtain the important features, we performed tournaments between a guessing player and a non-guessing player. Experimental results showed that the higher the number of pieces estimated, the better the win rate, and the higher the estimation accuracy, the better the win rate. The MC was found to be eﬀective even with an estimation accuracy of 60 percent. We also found that it was more eﬀective to estimate red pieces than blue pieces as an important feature.

1. はじめに

ガイスターは，相手の駒の色がわからない二人不完全情報ゲームである．このゲームは，6× 6の盤面で各プレイヤーが青と赤の駒を各4個ずつ使用して勝利を目指すゲームである．ガイスターは，コンピュータプレイヤに関する研究や詰めガイスター問題に関する研究が行われるなど，新たな研究対象として注目を集めている．これまで，ゲームAIを強くするために様々な研究が行われてきた．完全情報ゲームであるチェス，将棋，囲碁ではすでに人間のトッププレイヤーの実力を上回っている． 1 _{高知工科大学大学院工学研究} 2 _{高知工科大学情報学群} また，不完全情報ゲームにおいてもバックギャモン，ポーカーでトッププレイヤーに相当する実力を持つAIが研究されている[1]．不完全情報ゲームは，ゲームの状態に不明な部分が存在するため，例えば可能な状態集合からランダムに状態を仮定し，モンテカルロ木探索を行う[2]などしている．Long らは，不完全情報ゲームをゲームが進行するにしたがって情報が増えるトリック型ゲームとポーカーのように最後まで明らかな情報が増えないゲームに分類した[3]．トリック型ゲームでは着手決定において，未知の状態の推定を用いることで有効な意思決定が可能になるとされている．しかし，実験的には大貧民が必ずしも有効ではない[4]とされている．

(2)

ガイスターにおいても様々な研究やAIが開発されている．これまで推定を行うガイスタープレイヤーの開発はされてきたが，推定に関する基本的なデータが知られていなかった．そのため，データから「赤を重視して推定すべき」など推定の方針を示すことができれば，ガイスタープレイヤー開発に役立てることができる．本研究ではその方針を得るため，推定する駒の数や色，配置，推定精度に着目し，重視すべき特徴について調査を行う．本研究では，初期盤面から推定用いる実験を行う．途中局面から開始することは，適切な局面の選択が難しいため，初期盤面から実験を行う．また，出口の横に赤駒と青駒を置くキーパー戦略は一定の有効性が示されている[5]．そのため，キーパーの初期配置や初期配置毎の勝率の違いから初期配置の推定ができる可能性がある．推定において重視すべき特徴を得るために実験では初期盤面から相手の駒色の推定するプレイヤーとそうでないプレイヤーの対戦を行い，それぞれについて勝率などの違いを調べていく．

2. ガイスター

ガイスターは，互いのプレイヤーが青駒と赤駒を各4個ずつ計8個の駒を用いて行う二人不完全情報ゲームである．このゲームは，各プレイヤーは自身の駒の色は確認することができるが相手の駒の色は確認することができないという特性を持っている．ゲームは，6× 6の盤面で行い，以下の勝利条件を目指す． • 自分の青駒を脱出させる • 相手の青駒を全て取る • 自分の赤駒を全て取らせる脱出は自陣の反対側にある脱出口(図1の黒いマス)である．ゲーム開始時に各プレイヤーは決められた場所に8個の駒を自由に配置し，交互に駒を動かしていく．自身のターンでは，自身の駒1つを上下左右に1マス動かすことができる．移動先に相手の駒がある場合はその駒を取ることができ，取った駒の色を確認することができる．ゲームを進めていきどちらかのプレイヤーが勝利条件のいずれかを満たしたらゲーム終了である．図1 ガイスターの盤面

3.

4. 提案する内容

ガイスターでは推定を行うプレイヤーの開発がされてきている[8][9][10]が．推定に関する基本的なデータが知られていなかった．そのため，データから「赤を重視して推定すべき」などの方針を示すことができれば，ガイスタープレイヤー開発に役立てることができる．本研究では，推定する駒の数や駒色の色など，推定する内容によってプレイヤーの勝率に変化があるかなどを調べ，推定において重要となる特徴を得る．ガイスターにおける相手駒の推定の特徴を調べるため，

(3)

初期盤面から相手の駒色を推定するプレイヤーとそうでないプレイヤーの対戦を行う．今回は，推定する相手の駒数を変化させることによる勝率の変化，推定した駒色の内訳による勝率の変化と推定した場所による勝率の変化について調査を行う．また，実際に推定を行う場合，全ての駒に対して推定を行うこともある．その場合100%推定が正しいことはほとんどないため，推定精度の変化による推定の効果も調査する．推定の精度の効果について調べるため，相手の駒色の推定精度を変化させ，精度による勝率の変化についても調査する．駒色は，推定精度の確率に従って推定し配置を行っていく．さらに，推定する駒数を変化させる場合と推定の精度を変化させる場合の両方に対してどのような勝利・敗北条件を満たしたかについて調査する．これは状態が完全情報に近づくにつれて，また推定した駒色によってプレイヤーの行動が変化するかどうかを調べることを目的としている．推定する駒が．赤駒の時赤駒を4個取って敗北する割合が減少する，青駒が4個分かっていると青駒を4個取って勝利する割合が増加するという結果が期待される．

5. 実験

本実験では，初期盤面から相手の駒の推定するプレイヤーと通常のプレイヤーの対戦を行う．実験は，CPUはIntel Xeon CPU E5-2650 v3，10コア，2CPU，メモリは64GB

のマシンで行い，実験プログラムには，geister server*1を使用した．本実験は，棋譜が多く存在せず適切な途中盤面の用意が難しいので，まずは単純な条件として初期盤面を対象とする．相手駒の情報は，対戦サーバーログから取得している．一つ目の実験は，情報を取得した駒の数と勝率の関係を調べるため，推定する駒数を変化させ対戦を行う．推定する駒の数は，0∼7個の8種類とする．駒の数が8個で推定する数が7個まであるのは，7個のときと8個のときに得ることができる駒の情報の量が同じであるからである．さらに，推定した駒色の内訳と勝率の関係とどのような勝利・敗北条件を満たしたかを調べる．また，推定した場所と勝率の関係も調べる．二つ目の実験は，精度と勝率の関係を調べるため，情報の取得する駒数は8個と固定し，推定の精度を変化させ対戦を行う．精度は，50∼100%を10%刻みで変化させる．ここでは，プレイアウトの度に精度の確率に応じて駒色の設定を行う．さらに，どのような勝利・敗北条件を満たしたかを調べる．対戦は，先手後手500試合の計1,000試合行い，勝率で強さを評価する．今回は引き分けを0.5勝とする．引き分 *1 _{https://github.com/miyo/geister_server.java}，最終アクセス日2020年10月12日けは，大会*2_の合計₂₀₀_{手というルールに従う．相手の駒} の推定するプレイヤーについては，モンテカルロ法を用いたMC gとモンテカルロ木探索を用いたMCTS gの二つを用意する．これらのプレイヤーのプレイアウトは以下の手順で行われる． ( 1 )プレイアウトを行うルート局面で相手の駒色を仮定する．駒数を変える場合は，取得した駒色情報を基に駒色を確定し，残りの駒はランダムで駒色を仮定する．推定精度の場合は，精度に従って駒色を仮定する． ( 2 )プレイアウトを行う． ( 3 ) (1)と(2)を繰り返す．プレイアウトを行うたびに駒色の仮定を行っているため，プレイアウト毎に駒色の配置は変わっている．また，取得してきた駒色情報は，(1)の時にだけ使用しており，知識として「青なら取る」などはしていない．対戦相手はモンテカルロ法を用いたMCである．全てのプレイヤーの探索時間は5秒とする．

6. 結果と考察

本研究で行った推定する駒数を変えた場合と推定精度を変えた場合の実験結果と考察を記述する． 6.1 駒数を変えた場合の実験結果と考察推定する駒数を変えた場合の勝率の変化は表1，図2の通りである．括弧の中の数値は青駒および赤駒のどちらかが4個分かっている状態(以後これを完全情報状態と呼ぶ) を排除した場合の勝率を表している．推定を行った両プレイヤーとも推定駒数が増えるにしたがって勝率も増加した．最終的に勝率は，MC gは約65%程度まで増加し，MCTS g は約60%程度まで増加した．MC gとMCTS gを比較するとMC gの方がわずかに勝率が良かった．本実験では探索時間を一定としていたため実装の関係上MCTS gの方のプレイアウト回数が少なくなり，良い指手選択ができなかったと考えられる．また，推定した駒はプレイアウトのルート局面での駒色の設定のみに使用したため，勝率が伸びなかったと考えられる．完全情報状態を削除した場合の勝率は削除しなかった場合と比べてあまり変化しなかったが，推定駒数6のときは少し減少した．推定駒数が6の場合，完全情報状態の試合数が約500試合あり，勝率がMC g は約66%，MCTS gは約62%となっている．推定駒数6全体の勝率よりも高いことから勝率を上げていたと考えられる．推定駒数4，5の場合は完全情報状態の試合数が約30 試合，約130試合と少なかったため負けによる勝率の変化が大きく，それぞれの全体の勝率程度となり勝率への影響が小さかったと考えられる． *2 _{http://www2.matsue-ct.ac.jp/home/hashimoto/geister/} GAT/,最終アクセス日2020年10月13日

(4)

表1 駒色を推定したプレイヤーとしていないプレイヤーの対戦結果(勝率) 推定駒数 0 1 2 3 4 5 6 7 MC g 0.489 0.553 0.550 0.600 0.627 0.636 0.626 0.647 完全情報状態を削除した場合 (-) (-) (-) (-) (0.627) (0.634) (0.589) (-) MCTS g 0.432 0.516 0.500 0.586 0.573 0.590 0.596 0.607 完全情報状態を削除した場合 (-) (-) (-) (-) (0.576) (0.592) (0.573) (-) 表2 推定した色の内訳毎の勝率推定駒数1 推定駒数2 推定駒数3 B1R0 B0R1 B2R0 B1R1 B0R2 B3R0 B2R1 B1R2 B0R3 MC g 0.544 0.562 0.576 0.525 0.589 0.547 0.587 0.602 0.725 試合数 498 502 224 562 214 75 431 425 69 MCTS g 0.520 0.512 0.486 0.502 0.510 0.521 0.593 0.581 0.662 試合数 508 492 214 578 208 94 427 408 71 勝率推定駒数図2 対MCにおける推定個数毎の勝率推定駒数は同数だた駒色が異なる場合のそれぞれ勝率を表2にまとめた．表中のBnRmは，nが青駒の推定駒数， mが赤駒の推定駒数を表している．表2から青駒を推定するよりも赤駒を推定しているときの方の勝率が高かった．また，より多くの赤駒が推定した方が勝率が高かった．これより青駒を推定するよりも赤駒を推定した方が有効であると考えられる．その理由は，相手の赤駒を4個取ると負けるが，1個でも分かっていることでその敗北条件を避けられることが考えられる．また，推定した赤駒以外を取れば勝利でき，より多くの赤駒が分かっていれば取る駒数が減ることから勝ちやすくなったことも考えられる．一方で青駒は4個取らないと勝利とはならないので1，2個分かっていてもそれが勝利に結びつきにくいと考えられる．また，推定駒数が3個のB0R3におけるMC g，MCTS gの勝率は約73%，約66%と，全ての駒を推定した場合(表1 の推定駒数7個)の勝率65%，61%よりも高くなった．しかし，試合数が70試合前後と少なく結果は信用できないと考えられる．次に，表2と同じ分け方で満たした勝利条件について表 3，満たした敗北条件について表4にまとめた．数値はそれぞれの内訳の試合数の中で満たした割合であり，条件の対応は以下の通りである． • ES：青駒を脱出させる • BC：青駒を全て取る • RC：赤駒を全て取らせる勝利条件の割合は，MC gとMCTS gのどちらにおいても BCが少なく，ESが多かった．しかし，推定駒数の変化や推定の内訳によるそれぞれ勝利条件を満たす割合に大きな変化はみられなかった．敗北条件は，MC gとMCTS gのどちらにおいてもBCとRCが少なく，ESが多かった．推定の内訳によるESとBCの変化はあまりみられなかったが，RCは分かっている赤駒が多いほど満たす割合が減少する傾向がみられた．この傾向は，MC gよりもMCTS g に強くみられた．このことからも赤駒の推定が重要であると考えられる．また，推定枚数毎のBCを満たした回数の変化が図3である．MC gは推定駒数の増加による BCを満たす回数の増加の傾向はみられなかった．しかし， MCTS gは，推定駒数5の時に落ちているが推定駒数が増えることによるBCの増加傾向がみられた．回数推定駒数図3 対MCにおける推定個数毎の青駒を全て取るで勝利した回数

(5)

表3 推定した色の内訳毎の満たした勝利条件の割合推定駒数1 推定駒数2 推定駒数3 B1R0 B0R1 B2R0 B1R1 B0R2 B3R0 B2R1 B1R2 B0R3 MC g ES 0.464 0.476 0.487 0.393 0.407 0.400 0.441 0.445 0.391 BC 0.012 0.002 0.000 0.012 0.019 0.000 0.002 0.005 0.000 RC 0.068 0.083 0.089 0.119 0.164 0.147 0.144 0.153 0.333 MCTS g ES 0.451 0.413 0.388 0.425 0.383 0.547 0.471 0.428 0.563 BC 0.008 0.022 0.005 0.016 0.038 0.011 0.021 0.017 0.000 RC 0.061 0.077 0.075 0.073 0.077 0.074 0.096 0.118 0.099 表4 推定した色の内訳毎の満たした敗北条件の割合推定駒数1 推定駒数2 推定駒数3 B1R0 B0R1 B2R0 B1R1 B0R2 B3R0 B2R1 B1R2 B0R3 MC g ES 0.390 0.378 0.384 0.418 0.369 0.440 0.378 0.376 0.261 BC 0.016 0.012 0.027 0.025 0.037 0.000 0.023 0.021 0.014 RC 0.050 0.048 0.013 0.032 0.005 0.013 0.012 0.000 0.000 MCTS g ES 0.447 0.453 0.481 0.469 0.428 0.436 0.389 0.397 0.281 BC 0.010 0.022 0.014 0.019 0.048 0.032 0.016 0.020 0.042 RC 0.024 0.012 0.019 0.010 0.014 0.011 0.002 0.002 0.014 推定駒数1の時の異なる場所による勝率の違いを表5，満たした勝利条件を表6，満たした敗北条件を表7にまとめた．表における数字1∼4は図4における番号が示す場所を表している．また，駒が配置されている場所は左右対象とみることができるため，図4での同じ色で塗られた場所は同じ場所として扱うものとした．例えば，赤で塗られた場所はどちらとも1番の場所としている．表6，表7の数値は，それぞれの場所における各色の試合数の中で満たした割合である．図4 数字が示す場所表5では，場所2，3において赤を推定する方が勝率が高く，今までの傾向と一致していた．一方で，場所1，4では青を推定した方が赤を推定するよりも高くなっていた．場所1は，脱出口に1番近いということから青駒を進めやすい位置である．表6のBCが青を推定した方が多く，表7 のESが青を推定した方が少なくなっている．推定した駒が脱出口を目指して進んできたのを序盤で取ることによって青駒3，赤駒4という状況で有利に試合を進めることができるからであると考えられる．しかし，場所4のとき青を推定した方が勝率が良かったのかは不明である．推定駒数1の場合，場所によっては赤駒よりも青駒を推定した方が良いと考えられる．表5 推定駒数1時の場所毎の勝率場所 1 2 3 4 B R B R B R B R MC g 0.551 0.533 0.554 0.619 0.520 0.563 0.551 0.522 試合数 118 120 121 139 123 128 136 115 表6 推定駒数1時の場所毎の満たされた勝利条件の割合場所 1 2 3 4 B R B R B R B R ES 0.492 0.433 0.454 0.511 0.439 0.508 0.471 0.443 BC 0.017 0.000 0.033 0.007 0.000 0.000 0.000 0.000 RC 0.042 0.100 0.066 0.101 0.081 0.055 0.081 0.078 表7 推定駒数1時の場所毎の満たされた敗北条件の割合場所 1 2 3 4 B R B R B R B R ES 0.356 0.416 0.388 0.294 0.390 0.383 0.419 0.434 BC 0.034 0.008 0.008 0.029 0.244 0.008 0.000 0.000 RC 0.059 0.042 0.050 0.0576 0.065 0.047 0.029 0.043 推定駒数2の時の推定場所毎の勝率について表8にまとめた．場所を表すA∼Hは図4に書かれているものと同じ場所を指し，括弧の場所は括弧内の場所と同じことを表している．また，場所1では配置場所を左右対象としてみているため，図4の1=A，2=B，3=E，4=Fに対応している．表8からE，Hを含む推定を行った場合(E-Hを除く)勝率が高くなっている傾向がある．また，B-C，F-Gや B-Fのような真ん中の隣接するマスを推定するときに勝率が高くなっていた．勝率が高かった組みは後列の駒を推定

(6)

している場合が多く，後列の駒は相手から取られ難く試合の終盤まで残ることにより終盤を有利に進められたと考えられる．しかし，全ての場合において試合数が約40∼80 試合と少ないため，参考程度に記す．表8 推定駒数2時の場所毎の勝率場所 2 A B E F C D G H 場所 1 A - 0.545 0.582 0.570 0.493 0.545 0.521 0.548 B - - 0.544 0.600 0.595 (A-C) 0.541 0.655 E - - - 0.500 (B-H) (A-H) 0.522 0.436 F - - - - (B-G) (A-G) 0.615 (E-G) 6.2 精度を変えた場合の実験結果と考察推定の精度を変えた場合の勝率の変化は表9の通りである．精度が上がるほど勝率が増加した．推定精度が50%から60%に変化するだけでも，勝率が約8%上昇した．今回の実験はランダムシミュレーションを使用するMC gを用いており，精度が上がることによって本当の色の配置と一致する確率が上がり，勝率が良くなったと考えられる．勝利条件と敗北条件について，表10と表11にまとめた．条件は前節で述べたものと同じであり，数値は全試合の中で満たした割合を表している．勝利条件は，ESが減少していき，RCが増加する傾向がみられた．敗北条件は，ES とRCが減少する傾向がみられた．推定精度が上がると本来の盤面に近いシミュレーションを行うことができるため，敗北条件のESとRCを防ぐように行動したと考えられる．また，最も大きな差がみられるのは推定精度が50% から60%に変化する時である．このことから全駒推定するとき推定精度は60%でも十分効果があると考えられる．表9 全駒推定時の推定精度毎の勝率推定精度(%) 50 60 70 80 90 100 MC g 0.489 0.563 0.560 0.596 0.628 0.647 表10 全駒推定時の推定精度毎の満たした勝利条件の割合推定精度(%) 50 60 70 80 90 100 ES 0.420 0.451 0.431 0.408 0.373 0.362 BC 0.005 0.010 0.005 0.014 0.012 0.005 RC 0.064 0.102 0.124 0.174 0.243 0.280 表11 全駒推定時の推定精度毎の満たした敗北条件の割合推定精度(%) 50 60 70 80 90 100 ES 0.453 0.408 0.410 0.380 0.350 0.322 BC 0.06 0.011 0.024 0.021 0.022 0.020 RC 0.052 0.018 0.006 0.003 0.000 0.001

7. まとめ

ガイスターにおいて推定に関する基本的なデータが知られていなかった．そのため，データからを示すことができれば，ガイスタープレイヤー開発に役立てることができる．本研究では推定の方針を得るために推定において重視すべき特徴について調査を行った．実験の結果，推定する駒数が多いほど勝率が良く，推定精度が高いほど勝率が良いことが確認できた．MCでは推定精度が60%でも効果があることが確認できた．また，重視すべき特徴として青駒よりも赤駒を推定する方が有効であることが得られた．本研究では推定した駒色をプレイアウトのルート局面での駒色の設定にしか使用していなかったが，プレイアウト時の指手選択などに推定した駒色を使用したプレイヤーについて調査したいと思う．推定精度において推定する駒数が全駒ではなく，1∼6個のときにどのような変化があるかについても調査を行いたい．参考文献 [1] 伊藤毅志，保木邦仁，三宅陽一郎：ゲーム情報学概論-ゲームを切り開く人工知能-，コロナ社(2018).

[2] Sch¨afer, J., Buro, M. and Hartmann, K.: The UCT algorithm applied to games with imperfect informa-tion, Diploma, Otto-Von-Guericke Univ. Magdeburg,

Magdeburg, Germany, Vol. 11 (2008).

[3] Long, J. R., Sturtevant, N. R., Buro, M. and Furtak, T.: Understanding the success of perfect information monte carlo sampling in game tree search, Twenty-Fourth

AAAI Conference on Artificial Intelligence (2010).

[4] 西野順二，西野哲朗：大貧民における相手手札推定，研

究報告数理モデル化と問題解決, 2011-MPS-85 (2011).

[5] 伊藤雅士，大久保壮浩，木谷裕紀，小野廣隆：ガイスター

AIのキーパー戦略の有効性，ゲーム情報学研究報告，

Vol. 2019-GI-42, No. 3, pp. 1–7 (2019).

[6] 西野順二，西野哲朗：多人数不完全情報ゲームのモンテカルロ木探索における推定の効果，Vol. 2011-BIO-27, No. 31, pp. 1–4 (2011). [7] 川上直人，橋本剛：ガイスターAIの研究，技術報告6，情報処理学会,情報処理学会(2018). [8] 末續鴻輝，織田祐輔：機械学習を用いないガイスターの行動アルゴリズム開発，GAT2018論文集，Vol. 2018, pp. 13–16 (2018). [9] 三塩武徳，小谷善行：ゲームの不完全情報推定アルゴリズムUPPとそのガイスターへの応用，ゲーム情報学研究

報告，Vol. 2014-GI-31, No. 4, pp. 1–6 (2014).

[10] 鴛淵隆斗，佐藤直之：ガイスターゲームにおけるモンテ

カルロ法を利用した駒推定およびブラフ手の生成可能性の検証，ゲーム情報学研究報告，Vol. 2020-GI-43, No. 20, pp. 1–7 (2020).

ガイスターの初期盤面における相手駒推定の有効性