全く公平な二人零和有限確定完全情報ゲームは永遠の引き分け
一昨年のネタの蒸し返し、およびウィキの「ゲーム木」の項に書いてあることをなぞっただけの話になるが、もうちょっときちんと書き直してみるテスト。
全く公平な二人零和有限確定完全情報ゲームすわなち先手と後手どちらにも必勝手順が存在しない二人零和有限確定完全情報ゲームは永遠の引き分け。つまりそのゲームの神様同士が対局したとして、勝敗が5割づつ生起するような波乱とかはなく、何回やっても引き分け。
これは、ゲーム木の高さが有限かつ勝敗が確定的に与えられることからゲーム木の葉の集合Lが定まることと、先手後手をそれぞれ黒白として、Lの元が
- 黒手番かつ白必勝
- 白手番かつ黒必勝
- 引き分け
の3種類しかないことと、この事実を根の方向に伝搬させる6つの規則:
- 子に黒手番かつ白必勝が1つでもあれば親は白必勝
- 子が黒手番かつ白必勝ばかりなら親は白必勝
- 子が黒手番かつ上記以外なら親は引き分け
- 子に白手番かつ黒必勝が1つでもあれば親は黒必勝
- 子が白手番かつ黒必勝ばかりなら親は黒必勝
- 子が白手番かつ上記以外なら親は引き分け
がゲーム木のノード全てを黒必勝、白必勝、引き分けに塗り分ける上で完全*1かつ無矛盾*2であることから言える*3
すわなちゲーム木の根もまた黒必勝、白必勝、引き分けのどれかでしか有り得ないことが結論され、このうち公平なのは引き分けのみ。
なおパスも1手とみなす
プレイヤーが交互に複数手をまとめて適用するとなぜ公平に近づくのか
ようわからんが、いま白と黒で不公平さが目立つゲームがあったとすると、ここでは仮に黒にめがっさ有利だとすると、そいつは次のどちらかを満たしている
- ゲーム木の葉の集合Lの中で、白手番かつ黒必勝ノードの割合がその裏ケースの割合より有意に大きい
- 黒必勝ノードの祖父が黒必勝、という率がその裏ケースの率より有意に大きい*4
そこで勝敗のルールを変えずにプレイヤーが複数手をまとめて適用できるようにすると*5、もしもとのゲームの開始からゲーム終局までの手順の長さがまちまちかつその長さが共通因子を持たないか、持っていたとしてもそれとは素な手数だけまとめるなら、手番毎に複数手をまとめて適用することで1.が緩和される傾向に逝くんではないかいななぜなら黒手番の葉が白手番に変わったりするわけだし
しかし、2.が極端に成立しているようなゲームだったら複数手まとめてもこれはもうだめかもわからんね
追記 2011/7/17 AM10時ごろ
ぎょわーこのエントリの重要なポイントである6規則にミスがあったノデスorz→修正した。
あと勝敗のルールを変えずにプレイヤーが複数手をまとめて適用できるようすること自体は必ずしも合法手の定義を変更せずに成立する可能性がある。ただ変更前に白(黒)手番局面で「白(黒)の合法手がない」であった終局局面の手番が変わる結果、実際のゲーム中に生起しなくなったりその先に続くだけ、
とか色々(オイ
あと、多分ゲームの公平さの追求は、次の2目標の追求と同義
- ゲーム木の根が引き分けであること
- 少なくとも現実の対局で生起し得る範囲内の任意の親局面について、子の中に占めるそれぞれのプレイヤーの必勝局面が同数であること
1.だけ満たしつつ、ぱっと見全然公平に見えないゲームとか容易にいくらでも思いつくわけだし
*1:任意の親ノードについて、上記6規則で子の組み合わせの全てを尽くしている。
*2:6規則それぞれの前段条件が互いに背反であり、任意の親についてただ一つの規則のみ適用される。
*3:あるいは、利得行列の鞍点を想像しても良いわけだし、
*4:例えば、白手番かつ黒必勝の親は無条件に黒必勝である(兄弟の中身によらない)。つまり子から親へは必勝側の交代や引き分けへの変化を伴わずに世代を遡れるケースが多分半々ぐらいあるが、子から祖父のケースは無差別にそれが簡単でなくなる方向だから注目に値する。
*5:合法手の定義が変わるから、必然的に元のゲームは「合法手が無くなったら負け」タイプではなく、「ゴール条件を満たした方が勝ち」なものに限定される。