完全解析結果を使ったペンタゴが先手必勝であることの証明

全文

(1)Vol.2016-AL-156 No.4 2016/1/22. 情報処理学会研究報告 IPSJ SIG Technical Report. 完全解析結果を使ったペンタゴが先手必勝であることの証明神保秀司1,a). 概要：二人零和有限確定完全情報ゲームであるペンタゴの完全解析結果が 2014 年初頭に Irving により報告された．現在，石が 18 個以下置かれたすべての局面について，その局面から最適手順で対局を続けたときの勝敗の結果が約 4TB の圧縮された状態で公開されている．しかしながら，公開されている解析結果の再検証には膨大な計算資源を必要とする．現在著者は，公開されている完全解析結果を使ってペンタゴの初期局面が先手必勝であることの証明を表す有向非巡回グラフ (DAG) の構成を試みている．そのような DAG が得られればその DAG が表す証明の検証が小規模な計算機システムでも容易になるはずである．本報告では，その試みについて報告する．. A proof of the fact that Pentago is a first player win by using the perfect results Jimbo Shuji1,a). Abstract: Irving released perfect results of Pentago, an abstract strategy board game, in beginning of 2014. For each position with at most eighteen stones, the win loss result obtained by perfect moves from the position is included in the released data, now. However, enormous resources are required to verify the perfect results released. Currently, the author is attempting to construct a DAG that represent a proof of the fact that Pentago is a first player win by using the perfect results. If such a DAG is obtained, then the proof represented by the DAG will be readily verified. In this report, the author reports the attempts.. 1. はじめに. 満を使用し証明 DAG 全体を構築することを目指す．実際には，ペンタゴの完全解析結果が 2014 年初頭に Irving に. ペンタゴと呼ばれる二人零和有限確定完全情報ゲームが. より報告されている [2]．それは，巧妙なデータ構造を開. 先手必勝であることを証明する AND/OR 有向非巡回グラ. 発し，大規模なスーパーコンピュータを使った後退解析の. フを実際に計算機の主記憶上に構築することを目標とす. 手法でなされた．そこでの後退解析は，すべての解析結果. る，執筆時点で実験プログラムの完成が遅れているため，. を複数の計算機の主記憶上に保持する形で進められた．そ. 以下方針と計画について述べる．講演の際に実験結果を提. の結果既にペンタゴが先手必勝であることが証明されてい. 示する予定である．. る．しかしながら，完全解析の結果全体の検証も含めてペ. ペンタゴが先手必勝であることを証明する AND/OR 有向非巡回グラフ (証明 DAG) を新たに構成する目的は，一. ンタゴが先手必勝であることを検証する追実験は，著者が知る範囲では報告されていない．. 般的な個人で利用可能な計算機環境で検証が容易な証明を. さらに，このような簡潔な証明の構築に伴なうアルゴリ. 提示することである．単一の計算機の主記憶上に 20GB 未. ズム設計の手法，及び，ハードウェア利用法の開発は，他の離散数学上の問題の研究に有効であることが期待され. 1. a). 岡山大学 Okayama University, Okayama city, Okayama 700–8530, Japan jimbo-s@okayama-u.ac.jp. ⓒ 2016 Information Processing Society of Japan. る．著者は，グラフ理論の分野における特定の証明問題が大規模な計算によって解ける組合せ論の問題に帰着できる. 1.

(2) Vol.2016-AL-156 No.4 2016/1/22. 情報処理学会研究報告 IPSJ SIG Technical Report. ことを示した [4]．この研究において，オイラーグラフに対. 結果の内容について述べる．現在，合計約 4TB のファイ. してオイラー回帰長と呼ぶ整数値を定義し，7 以上の奇数. ル群が Irving によりパブリックドメインで公開されてい. n について n 点からなる完全グラフ Kn のオイラー回帰長. る [1]．以下，これらのファイルを公開ファイルと呼ぶ．そ. e(n) の決定を試み，n − 4 ≦ e(n) ≦ n − 3 が成り立つこと. れらには，初期局面を含めて 18 個以下の石が置かれたす. を示した．オイラー回帰長の定義も含めて詳細は参考文献. べての盤面について，そこから両対局者が最善を尽して対. に委ねる．著者は，十分大きい n に対して e(n) = n − 4. 局を継続したとき黒の勝ち，白の勝ち，引き分けのどれに. が成り立つことを予想しているが，単純なアルゴリズムを. なるかの情報 (勝敗情報) が格納されている．各ファイル. 使ったのでは計算の規模が大きくなり過ぎるため単一の小. 内のデータを利用するときは，索引部分のデータ圧縮の解. 規模なワークステーションでは n = 15 の場合の検証計算. 凍の後，さらに実質的な内容部分のデータ圧縮の解凍とい. の完了ですら不可能であることが判明している．. う二重の解凍操作が必要である．公開ファイルは，分散処. 2. 準備. 理による後退解析の効率化のために勝敗情報の格納形式に多くの工夫が施され，別の用途で利用するときに必ずしも. ペンタゴのゲームのルールを以下に述べる．ペンタゴの. 効率的だとは限らない．現在，任意の盤面を与えてその勝. 盤は， 3 × 3 のマス目の正方形の小盤 4 つからなる 6 × 6. 敗情報を公開ファイルから取り出すプログラムを C 言語で. のマス目の正方形であり，各マス目に黒か白の石を置くこ. 作成し使用している．. とができる．さらに，各小盤は，90 度の倍数の回転を施し. 石が n 個置かれた盤面の勝敗情報は，slice-n.pentago. て元の場所に置き直せるようになっている．ゲームの目的. という名前の公開ファイルに格納されている．Irving に. は，盤上に石が置かれていない状態 (初期局面) から始め，. 従って，同じ個数の石が置かれた盤面すべてからなる集合. 2 人の対局者が交互に次の操作を繰り返すことにより，自. をスライスと呼び，石が n 個置かれた盤面からなるスライ. 分の色の石が縦横斜め何れかの方向の直線上に続いて 5 個. スをスライス n と呼ぶことにする．slice-0.pentag から. 並んだ状態 (5 連) を含む盤面 (盤上の石の配置) を作るこ. slice-12.pentag までのファイルサイズの合計が約 10GB. とである．. であり，12 が多くの一般的なパソコンの主記憶に格納できる. 1. 自分の色の石を盤上の石の無いマス目に 1 つ. 公開ファイルの番号 n の上限ではないかと考えられる．さ. 置く．. らに，slice-0.pentag から slice-14.pentag までのファ. 2. 次に，任意の小盤 1 つを右か左どちらかに 90. イルサイズの合計が約 115GB であり，slice-0.pentag. 度回す．. から slice-15.pentag までのファイルサイズの合計が約. 2 人の対局者には，黒または白の互いに異なる色を割り当. 410GB である．従って，14 が主記憶装置を十分に増設し. てる．ここでは，先手に黒を割り当てることにする．上の. た単一のワークステーションの主記憶に格納できる公開. 1. の操作の直後にその操作を施した対局者の色の石の 5 連. ファイルの番号 n の現時点における上限ではないかと考え. ができていれば，その対局者の勝ちとする．従って，この. られる．. 場合 2. の操作は施さず，1. の操作の直後の盤面が終局の盤面となる. さらに，2. の操作の直後に両方の色の石の 5. 3. 方針. 連が含まれていれば，その対局は引き分けとする．どちら. この節では，証明 DAG (ペンタゴが先手必勝であること. の色の石の 5 連も含まれない 36 箇所すべてのマス目に石. を証明する AND/OR 有向非巡回グラフ) をなるべく小さ. が置いてある盤面が作られた場合も引き分けとする．. いサイズで構成するための方針と手法について述べる．. 次に，ペンタゴのゲームの特徴について述べる．上に述べたペンタゴのルールから分かるように，ペンタゴは五目並べに小盤の回転を取り入れて拡張した形になっている．. 3.1 証明の前半部分の構成公開ファイルの勝敗情報は，スライス 0 からスライス 18. ただし，先手の色 (黒) の石に対する長連，三三，四四に相. までに属する盤面を点とする有向非巡回グラフ G を構成. 当する禁じ手は存在せず，盤上に自分の色の石が多く存在. している．各枝の向きは石の個数の少ない盤面の点から多. しても不利にならないため初期局面が後手必勝であること. い盤面の点への向きとする．ペンタゴの初期局面に対応す. は有り得ない．パスが無く，石が盤の外に移動することが. る G の点 v0 の入次数は 0 である．以下，v0 を G の根. ないので盤面が局面を完全に表している．さらに，盤上に. と呼ぶことにする．各盤面の勝敗情報は，G の点ラベルと. 置かれた石の個数は，手が進むにつれて確実に増加するの. 見做す．このとき，次の条件を満たす G の部分グラフ H. で，同一の対局中に同一の局面が繰り返し出現することは. は，ペンタゴが先手必勝であることを証明する有向非巡回. 有り得ない．従って，局面の推移関係から作られる有向グ. グラフの前半部分を構成する．. ラフは，閉路をもたない有向非巡回グラフである．次に，Irving により公開されているペンタゴの完全解析. ⓒ 2016 Information Processing Society of Japan. 2.

(3) Vol.2016-AL-156 No.4 2016/1/22. 情報処理学会研究報告 IPSJ SIG Technical Report. 条件 A. 1. H の点ラベルは，すべて黒勝ちである． 2. 初期局面に対応した点 v0 が H に属している． 3. H の点 v の出次数が 0 であることは，v が黒石の 5 連を含む盤面に対応しているか，あるいは，スライス 18 に属する盤面に対応していることと同値である．. 4. H の点でスライス 18 以外の偶数スライスに属する盤面に対応するものの出次数は，1 である．. 5. H の点で奇数スライスに属する盤面に対応するものの出次数は，G における v の出次数に等しいか，あるいは，0 である．. 3.3 SSD によるランダムアクセスの高速化公開ファイル内の勝敗情報を使えば，サイズを問題にしなければ証明 DAG の前半の部分グラフを構築するのは容易である．しかしながら，その場合でもスライス 14, 15, 16, 17, 18 に属する盤面の勝敗情報は，主記憶以外の媒体から検索することになる．その媒体がハードディスクであればランダムアクセスの性能の悪さが致命的であることが予想される．これを避けるため，現在 1TB 弱の容量の SSD 5 個に公開ファイルをすべて格納することを計画している．SSD は，機械的な駆動部をもたず，かつ，データの読み出しによる劣化が原則としてないため本研究でハードディスクの代替として使用するには，極めて有利である．盤面の有利さの判定には，関数 g(P ) の値に加え. 上で定義した DAG G は，盤面の数は 6 × 6 の五目並べと同じであるが，手の操作 2. があるため枝の本数が 8 倍. て，現在の盤面 P から先読みして得られる盤面の勝敗情報も使って精度を高める工夫を取り入れたい．. 近く多くなっている．条件 A を満たす G の部分グラフ H も同様に 6 × 6 の五目並べの場合の 8 倍近くになると予想する．証明 DAG の構築の際に同一点の重複を高速に判定するために大規模なハッシュ表の導入を計画している．. 3.4 証明の後半部分の構成スライス 19 から 36 までに属する盤面の勝敗情報は，. Irving による計算機実験中には実際に収集されたが，現在入手不可能になっている．従って，証明の前半の構築で得られたスライス 18 に属する根の盤面から始めて独力でな. 3.2 証明の前半部分の評価尺度証明の前半部分を構成するグラフの良さの評価尺度は，. るべく小さいサイズの証明 DAG を構築しなければならない．このような問題については，従来から深く広範囲な研. 基本的には，スライス 18 に属する点の個数である．証明. 究が為されている [3]．特に，λ 探索とハッシュ表を使った. の後半部分がこれらの点を根とする証明 DAG の集合にな. df-pn を組合せる手法の導入を目指している．. るからである．ただし，H の点のうちスライス 18 に属するもの v を根とする証明 DAG のサイズは，v の点に対応する盤面の黒にとっての有利さに大きく依存することを予想する．. 3.5 GPU 計算による高速化証明の後半部分では，多数の異なる根をもつ証明 DAG を構築する．それらは，根以外の点に対応する盤面が多数. 証明 DAG の前半部分の部分グラフ H の構築の際にも. 共通していることがあり得るが，そのような重複の除去の. 黒の手番の局面 (偶数スライスに属する点に対応する局面). 操作を含めても GPU の活用により大幅な速度の向上が期. で黒勝ちの手から 1 つを得らぶとき，黒にとって最も有利. 待できる．近年 GPU によるゲーム木探索の高速化の試み. な手を選ぶことが H のサイズの削減に有効であると考え. が報告されている [5]．. る．次に定義する関数 g(P ) は，与えられた盤面 P の有利さの尺度の有力な候補と期待している．. 4. おわりに. 6 × 6 の盤上には，一方の色について 32 種類の 5 連が存. ペンタゴと呼ばれる二人零和有限確定完全情報ゲームが. 在する．そのような 5 連から幾つかの石を取り除いて石が. 先手必勝であることを証明する AND/OR 有向非巡回グラ. k 個残ったものを元の 5 連の石の色の k 占有と呼ぶ．従っ. フ (証明 DAG) を計算機の主記憶上に構築する計画につい. て，石が置かれていない直線上に続いて 5 個並んでいるマ. て，その方針と手法に重点を置いて説明した，講演時には，. ス目は，黒の 0 占有でもあり，白の 0 占有でもある．盤. 実行された一部の計算機実験の結果について報告したい．. 面 P に含まれる黒の k 占有の個数を bk で，白の k 占有. 特に，完成した際の証明 DAG 全体の規模の予想ができる. の個数を wk で表す．適当な非負実数の定数 a1 , a2 , a3 , a4. ことを最優先の目標にしている．. を定めて，関数 g(P ) を. 本研究で得られた知識や技術は，他の離散数学上の問題の解決に有用であることを期待している．例えば，SSD と. g(P ) = a4 (b4 −w4 )+a3 (b3 −w3 )+a2 (b2 −w2 )+a1 (b1 −w1 ). GPU という比較的安価なハードウェアの導入による高速化の技術がそれに該当すると予想している．. により定義する．この場合，g(P ) は，その値が大きいほど黒が有利であることを表す．. ⓒ 2016 Information Processing Society of Japan. 謝辞本研究は JSPS 科研費 15K00018 の助成を受けたものです．. 3.

(4) 情報処理学会研究報告 IPSJ SIG Technical Report. Vol.2016-AL-156 No.4 2016/1/22. 参考文献 [1] [2]. [3]. [4]. [5]. Geoﬀrey Irving. Pentago is a first player win. https: //perfect-pentago.net/. Geoﬀrey Irving. Pentago is a first player win: Strongly solving a game using parallel in-core retrograde analysis. arXiv preprint arXiv:1404.0743, 2014. 岸本章宏. 完全情報ゲームと and/or 木探索 (⟨ 特集 ⟩ ゲームとコンピュータ). オペレーションズ・リサーチ: 経営の科学, Vol. 52, No. 1, pp. 22–26, 2007. 神保秀司, 丸岡章. 完全グラフのオイラー回帰長の上界と下界の改良. 情報処理学会研究報告. AL, アルゴリズム研究会報告, Vol. 2014, No. 3, pp. 1–7, 2014. 木村健, 小谷善行ほか. Cuda 将棋: Gpgpu による並列ゲーム木探索. 第 53 回プログラミングシンポジウム予稿集, Vol. 2012, pp. 91–96, 2012.. ⓒ 2016 Information Processing Society of Japan. 4.

(5)