三目並べ

三目並べ

概要

3×3のグリッド(井)のスペースに×と〇のマークを交互に書いて遊ぶゲームです。縦・横・斜めのいずれかで自分のマークを並べると勝ちとなります。二人零和有限完全確定情報ゲームに分類でき、その単純さから、ゲーム情報学の基礎で使われるゲームです。アメリカ英語ではtic-tac-toeです。次のリンクで遊べます。GODは最善の手を指し、RDMはランダムな手を指します。

Tic-Tac-Toe

ゲームの解析

このゲームはゲーム中のすべての局面の勝敗が解析されており(強解決)、初期場面は引き分け局面です。つまり、このゲームは双方が勝ちを目指して最善を尽くした場合、必ず引き分けになります。

回転や反転した結果同じになるような配置を一つに正規化した場合、総局面数は765です。しなかった場合、総局面数は26830です。

勝ち負け引き分け合計
全て390224151765
末端01353138

765の本質的な差がある局面のうち、224局面が手番の負け局面(内135局面が末端)、151局面が引き分け局面(内3局面が末端)、390局面が手番の勝ち局面です。また末端局面は138局面(先手勝ちは91局面・後手勝ちは44局面・引き分けは3局面)で引き分けかつ末端局面は下記の3パターンです。(以下すべての図で×が先手)

×が先手

他、2ライン勝ちが6パターンあります。

×が先手
アルゴリズム三目並べの決勝パターン分析

双方が最善手を打てる場合の(負け側は最も手数を伸ばせる戦略)勝ち局面から末端局面までかかる最大手数は5手です。

m,n,kゲームに一般化するなどし、派生ゲームの多くが数学的に解析されています。

戦略

初期局面は先手がどこをとっても引き分け局面です。先手の初手が真ん中の場合、後手が角をとった局面は引き分け局面ですが、辺の真ん中を取った局面は後手の負け局面になります。

×が先手

先手の初手が真ん中以外の場合、後手が真ん中を取った局面は必ず引き分け局面です。

×が先手

相手がリーチを潰す戦略がある場合、勝つためにはダブルリーチが必要です。

プログラミング的な話

ゲームをコンピューター上(bit)で表現する方法の一つとして、一つのマスは×・〇・空の3種類の状態で9つあるため、2bit×9の18bit(×の存在を表す9bit+〇の存在を表す9bitの合計18bitと同じ)で表せます。(これ以上減らすと扱いづらい)×の数と〇の数でどちらの手番かわかるため、手番情報は必要ありません。

現在のコンピューター(ノートpc等)であれば、最善手は初期局面からミニマックス法(ネガマックス法、αβ法)でも一瞬で求められます。

https://kowaragan.com/gameinformatics4minmaxalphabeta/(新しいタブで開く)

文化的な話

Chromeで検索すると実際に遊べるゲームの一つです。

アメリカでは×から始めるのが一般のようです。(ただし、イギリス英語ではnoughts and crosses)

知名度が高く、Youtube等でも関係する内容の動画の再生回数が多いです。

参考

三目並べ - Wikipedia

コメント

タイトルとURLをコピーしました