Loading article…
組合せゲーム理論では、2 人のプレイヤーによる決定論的完全情報 ターン制ゲームは、完璧なプレイにより、最初に手番を取ったプレイヤーが常に勝利を強制できる場合、先手プレイヤーの勝利となります。同様に、完璧なプレイにより、2 番目に手番を取ったプレイヤーが常に勝利を強制できる場合、ゲームは 2 番目プレイヤーの勝利となります。完璧なプレイでは、どちらの側も勝利を強制できない場合、ゲームは引き分けとなります。
ゲームツリーが比較的小さいゲームの中には、1 番目または 2 番目のプレイヤーが勝つことが証明されているものもあります。たとえば、古典的な 3-4-5 の開始位置を持つNimゲームは、最初のプレイヤーが勝つゲームです。ただし、1-3-5-7 の開始位置を持つ Nim は、2 番目のプレイヤーが勝ちます。古典的なConnect Fourゲームは、数学的に最初のプレイヤーが勝つことが証明されています。
完璧なプレイでは、チェッカーは引き分けと判定され、どちらのプレイヤーも勝利を強制することはできません。[1]完璧なプレイで引き分けになるゲームのもう1つの例は、三目並べで、これには最初の動きからのプレイが含まれます。
チェスを解くための重要な理論が完成しました。ゲームが不完全な状態でプレイされた場合（すべての人間や現在のすべてのチェスエンジンなど）、先手優位性が検出される可能性があると推測されています。しかし、完璧なプレイでは、ゲームが先手（白）の勝利か、後手（黒）の勝利か、それとも強制引き分けかは未解決のままです。[2] [3] [4]
参照
参考文献
- ^ Schaeffer, J.; Burch, N.; Bjornsson, Y.; Kishimoto, A.; Muller, M.; Lake, R.; Lu, P.; Sutphen, S. (2007). 「チェッカーの謎が解ける」. Science . 317 (5844): 1518–1522. Bibcode :2007Sci...317.1518S. doi : 10.1126/science.1144079. PMID 17641166. S2CID 10274228 .
- ^ JWHM Uiterwijk、HJ van den Herik。 「イニシアチブの利点」。 （1999年8月）。
- ^ Shannon, C. (1950 年 3 月). 「チェスをプレイするためのコンピュータプログラミング」(PDF) . Philosophical Magazine . 7. 41 (314). 2010 年 7 月 6 日のオリジナル(PDF)からアーカイブ。2008年 6 月 27 日閲覧。
- ^ Victor Allis (1994). 「博士論文：ゲームと人工知能における解決策の探求」（PDF）。コンピューターサイエンス学部。リンブルフ大学。 2020年11月22日時点のオリジナル（PDF）からアーカイブ。 2012年7月14日閲覧。