第5回 社内プログラミングコンテスト『ライフゲームGO』

皆さん、こんにちは! 社内プログラミングコンテスト担当の二木です。

前回の『コラッツリス』に引き続き、第5回社内プログラミングコンテスト(以下、社内プロコン)『ライフゲームGO』について紹介します。

• 第5回 Fixstars社内プログラミングコンテスト2016 『ライフゲームGO』

ライフゲームGO

ライフゲームGOとは、コンウェイのライフゲーム(Conway’s Game of Life)と囲碁(Go)のような陣取りゲームを合わせた二人用ゲームです。

ライフゲームGOでは、10×10マスで構成されたフィールド上のセル(細胞)に対し、「生」と「死」の2つの状態が存在します。最初は10×10=100個のセルがすべて「死」の状態になっていて、プレイヤーは交互に一つのセルを選んで「生」の状態とし、それを20回ずつ繰り返します。最終的に100個のセルのうち、「生」の状態のセルが40個、「死」の状態のセルが60個、存在することになります。

すべてのセルの「生」と「死」の状態が決定したら、ライフゲームのルールに従って、そこから3ステップ(世代)分だけ状態を進めます。最終的なセルの支配率(陣地数)により勝敗を決定します。

ゲームの準備

最初にプレイヤーの先攻・後攻を決定し、10×10マスの100個の死セルに対し、交互にセルの状態を「死」から「生」に変更し、そのセルは変更したプレイヤーの陣地となります。相手のプレイヤーの生セルに対しては、再度「生」に変更して陣地とすることはできません。

ゲームの進め方

ゲームの準備でプレイヤー同士がそれぞれ20個の生セルを選び終わった状態では、10×10のフィールドに生セル40個、死セル60個が存在します。次に、コンウェイのライフゲームのルールに従って、3ステップ(世代)だけ状態を進めます。この時に陣地(支配しているセル)数の多いプレイヤーが勝利します。同数の場合は引き分けになります。

ライフゲームのルールで適用される生セルはどのプレイヤーのセルであるかは考慮されません。例えば、ある死セルの周りにプレイヤー1の生セルが2個、プレイヤー2の生セルが1個あった場合、その死セルの周りに生セルが3個存在することになるので、状態は「誕生」ということになり、その死セルは生セルに変化します。そして、周りに生セルを2個持っているプレイヤー1が支配するセルとなります。

10×10のフィールドは上下左右が繋がっている周期境界条件(トーラス体)になっています。例えば、フィールドの右上、左上、右下、左下の4隅に生セルが存在する場合、それぞれのセルの周りには3つの生セルが隣接していることになり、4つのセルのすべてが「生存」の状態となります。

対戦の流れ

対戦プログラムはコンテスト参加者が作成し、制御プログラムと標準入出力により情報の授受を行います。

図中の赤で示した文字列は、制御プログラムと対戦プログラムとの間で標準出力を介して通知するコマンドになっています。制御プログラム側からのコマンドは、スペース区切りで先頭にコマンドのタイプが記述され、それ以降に必要な情報が書かれています。

制御プログラムと対戦プログラムのコマンドの授受はすべて標準入出力を介して行われます。また、制御プログラムからコマンドが渡された場合、必ず標準出力で返さなくてはなりません。

対戦プログラム

二人用対戦プログラムということで、優勝者および準優勝者ともにモンテカルロ木探索(MCTS)とプレイアウト(playout)を採用していました。以下に、それぞれのアルゴリズムの簡単な解説スライドを載せておきます。

優勝者の解説スライド

準優勝者の解説スライド

結果発表会の資料

結果発表会の資料を匿名化して上げておきます。

最後に

今回の『ライフゲームGO』は2人対戦型ゲームの思考ルーチンを考える問題でしたが、対戦型だと相手がいるので、より競っている雰囲気がありました。

今年も第6回となる社内プロコンを開催する予定です。社内とありますが社外の方のエントリーも受け付けていますので、興味のある方は是非参加してみてください!

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください。