今回は The Simple Game (AtCoder Beginner Contest 427)をネタにしてパズルゲームをつくります。

The Simple Gameを解いてみる

The Simple Game

問題の趣旨は以下のとおりです。

各頂点の出次数が 1 以上である有向グラフがあり、各頂点には’A’または’B’が書かれている。

初期状態で駒は頂点 1 に置かれていて、これを先手後手交互に移動させる。最終的に駒が置かれている頂点に書かれている文字が’A’なら先手の勝ち、’B’なら後手の勝ちである。

両者が最適に行動したときのゲームの勝者は?

このようなゲームの問題では、後ろから勝敗の状態を解析するとうまくいく場合が多いです。

最終ターンの後手の手番で’B’に移動できる頂点(後手必勝点)に駒があるなら後手の勝ちです。そうではない位置(先手必勝点)に駒があるなら先手の勝ちです。最終ターンの先手の手番で先手必勝点に移動できる位置に駒がある(先手必勝点)なら先手の勝ちで、できない(後手必勝点)のであれば後手の勝ちです。

このような操作をK回繰り返したときに頂点 1 が先手必勝点か後手必勝点かで解を得ることができます。

HTML部分

HTML部分を示します。

style.css

グローバル変数

Cellクラスの定義

マスを描画等で必要になるのでCellクラスを定義します。

ページが読み込まれたときの処理

ページが読み込まれたときにおこなわれる処理を示します。

マスの生成

マスを生成する処理を示します。

25個のCellオブジェクトを生成して移動可能なマス同士を連結させます。このとき隅や端にあるものを除いて入次数と出次数が 2 になるようにします。

イベントリスナの追加

イベントリスナを追加する処理を示します。呼び出される関数に関しては後述します。

問題を生成する処理

問題を生成する処理を示します。マスのなかから約半数に’A’を、それ以外のものに’B’を選択します。indexと乱数を結びつけてソートして約半数をランダムに選んでいます。

更新処理の開始

更新処理を開始するための処理を示します。

その前提として、ゲーム開始ボタンと先手後手選択ボタンの表示非表示を切り替える関数を示します。

ボリュームを調整できるようにする

ゲーム開始以降の処理は次回とします。