不偏ゲーム

ウィキペディア

不偏ゲーム

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2024/05/12 01:43 UTC 版)

不偏(impartial)ゲームとは、二人零和有限確定完全情報ゲームのうち、各状態でどちらのプレーヤが手を打つにしても、動かす選択肢の集合が常に等しいゲームのことを指す。そうでない二人零和有限確定完全情報ゲームは、非不偏ゲーム（英語: Partisan game）と呼ばれる。ゲームは、二人零和有限確定完全情報ゲームであるため、これ以上の移動が不可能な局面(terminal position)まで進められ、その結果、勝者、敗者が定まる。また、お互いに全ての情報を知り合っていて、偶然性に左右されることがない。

不偏ゲームには、ニム、スプラウト（ゲーム）（英語: Sprouts (game)）、クアルト (ボードゲーム)、クラム（ゲーム）（英語: Cram (game)）、チョンプ（英語: Chomp）、ノタクト（英語: Notakto）などがある。チェスや囲碁は、黒と白でお互いが動かす色が異なるので、不偏ゲームではない。また、ポーカーなどはお互いの手札が分からないので、不偏ゲームではない。

不偏ゲームは、スプレイグ・グランディの定理を用いて解析することができて、先にterminal positionに動かしたプレーヤーの勝ちとなる正規型のゲームでは常にニム数（英語: nimber）と等価であることが示されている。

条件

• 2人のプレーヤーは、terminal positionに達するまで交互に交代しなければならない。
• 1人のプレイヤーがterminal positionに達したとき、勝者が決まる。
• 有限回の操作でterminal positionに達する。
• 各状態でどちらのプレーヤが手を打つにしても、動かす選択肢の集合が常に等しい。
• 常にお互い全ての情報を持っていて、偶然性に決して左右されない。

参考文献

• Michael H. Albert, Richard J. Nowakowski, David Wolfe, 川辺治之(2010). 組合せゲーム理論入門
• https://www.math.s.chiba-u.ac.jp/~yasuda/open2all/game_Main.pdf

関連項目

• ゲーム理論
• ニム
• スプレイグ・グランディの定理