ゲーム理論の基礎と応用：ニムゲームからスプラグ-グリニー定理まで
ニムゲームの基本構造
ニムゲームは組合せゲーム（Combinatorial Game）の代表例であり、両者交互に行動し、最終的に移動できない者が敗れるというルールを持つ。各ターンで、プレイヤーは任意の山から1個以上の石を取り除くことができる。
重要な性質として、ある状態 (a₁, a₂, ..., aₙ) がP-ポジション（後手必勝）であるための条件は、すべての山の石の数のビット単位 ...
9月22日 07:43 投稿
グリッド迷路での最適経路探索
問題概要
n×m のグリッドからなる迷路を考えます。各セル (i, j) には方向指示 di,j と重み vi,j が設定されています。プレイヤーは初期位置 (sx, sy) から左足で踏み込み、その時点で vsx,sy を加算し、セルの重みを -vsx,sy に反転させます。
その後、各ステップで以下の選択肢があります：
ゲームを終了し、現在のスコアを最終スコアとする
現在のセルの方向指示に従 ...
8月31日 20:47 投稿
P3210 [HNOI2010] 石取りゲーム
ゲーム理論に関する興味深い問題です！
しかし、まだ完全には理解できていません...
主なアイデアは「上三角」のケースを除外することです。このケースは見た目に劣っているように見えるため、プレイヤーは最後に選ぶ可能性が高く、**必ず連続して選択されます。つまり、先手が最初と三番目を、後手が二番目を選択します**。（理性的な理解は失敗し、感覚的に理解するし ...
7月15日 16:01 投稿