三目並べ

三目並べ

完成した三目並べゲーム
その他の名前	ゼロとクロス XとO
ジャンル	紙と鉛筆を使ったゲーム
プレイヤー	2
セットアップ時間	最小限
プレイ時間	約1分
チャンス	なし
スキル	戦略、戦術、観察

三目並べ(アメリカ英語)、十字(イギリス連邦英語)、またはXs and Os (カナダまたはアイルランド英語) は、2 人のプレーヤーが交互に 3 x 3 のマス目にXまたはO をマークする紙と鉛筆のゲームです。マークした 3 つを水平、垂直、または斜めの列に配置することに成功したプレーヤーが勝者となります。これは解かれたゲームであり、両方のプレーヤーがベストプレイをすると強制的に引き分けになります。

アメリカ英語では、このゲームは「tic-tac-toe」として知られています。また、「tick-tack-toe」、「tick-tat-toe」、「tit-tat-toe」と綴られることもあります。^{[1] [2]}

英連邦英語（特にイギリス英語、南アフリカ英語、インド英語、オーストラリア英語、ニュージーランド英語）では、このゲームは「noughts and crosses」と呼ばれ、「naughts and crosses」と綴られることもある。この名前は、ゲーム内のマークの形（XとO）に由来している。「nought」は数字のゼロの古い呼び方で、「cross」はXの形を指す。「nought」という用語は現在ではあまり使われていないが、これらの国では「noughts and crosses」という名前が依然としてアメリカの名前「tic-tac-toe」よりも好まれている。

時々、三目並べ（プレイヤーが「ピース」を追加し続ける）とスリーメンズモリス（一定数のピースが置かれた後にピースが動き始める）が混同されることがあります。

三目並べは、2 人のプレイヤーが 3 x 3 のグリッド上でプレイします。プレイヤーは、グリッド内の 9 つのスペースの 1 つに X と O のマークを交互に配置します。

次の例では、最初のプレイヤー ( X ) が 7 つのステップでゲームに勝利します。

誰が最初にプレイするかについては普遍的に合意されたルールはありませんが、この記事では、X が最初にプレイするという慣例が使用されています。

プレイヤーはすぐに、両者の最善のプレイが引き分けにつながることに気づきます。そのため、三目並べは最適な戦略を発見していない可能性のある幼い子供たちによってプレイされることが多いのです。

三目並べは単純なため、スポーツマンシップの概念やゲームツリーの探索を扱う人工知能の分野を教える教育ツールとしてよく使われます。三目並べを完璧にプレイするコンピュータプログラムや、この空間上で本質的に異なる765の位置（状態空間の複雑さ）や、回転や反射まで含めた26,830通りのゲーム（ゲームツリーの複雑さ）を列挙するコンピュータプログラムを書くのは簡単です。^[3]両方のプレイヤーが最適にプレイした場合、ゲームは常に引き分けに終わり、三目並べは無駄なゲームになります。^[4]

このゲームはm、n、kゲームに一般化することができ、2 人のプレーヤーがm × nの盤上に自分の色の石を交互に置き、自分の色のk 個を一列に並べることを目標とする。三目並べは 3,3,3 ゲームである。^[5] Harary の一般化された三目並べは、三目並べをさらに広く一般化したものである。これはn ^dゲーム、具体的にはn = 3 かつd = 2のゲームとして一般化することもできる^{。[6]任意の}発生構造でプレイすることでさらに一般化することができ、ここで行は線、セルは点である。三目並べの発生構造は 9 つの点、3 つの水平線、3 つの垂直線、および 2 つの対角線で構成され、各線は少なくとも 3 つの点で構成される。

3つ並んだボードで遊ぶゲームは古代エジプトにまで遡ることができ、^[7]紀元前1300年頃の屋根瓦の上にそのようなゲームボードが発見されています。^[8]

三目並べの初期のバリエーションは、紀元前1世紀頃のローマ帝国でプレイされていました。それは「テルニ・ラピリ（一度に3つの小石）」と呼ばれ、駒の数は無制限ではなく、各プレーヤーが3つしか持たなかったため、ゲームを続けるには空きスペースに駒を移動しなければなりませんでした。^[9]ローマのいたるところで、このゲームのグリッドのマークがチョークで書かれていました。これとよく似た古代のゲームには、やはり単純なグリッド上でプレイされ、終了するには3つの駒を一列に並べる必要があるスリーメンズモリスがあります。 ^[10]また、プエブロ人のゲームであるピカリアもあります。

このゲームのさまざまな名前は、比較的最近のものである。イギリス名である「ゼロとクロス」（ゼロは「ゼロ」の別名）が初めて印刷物に登場したのは、1858年のNotes and Queries誌である。^[11]「ティックタックトー」というゲームが初めて印刷物に登場したのは1884年だが、これは「石板の上で遊ぶ子供のゲームで、目を閉じて鉛筆を数字の1つに落とそうとし、当たった数字が得点となる」ことを指していた。^{[この引用には出典が必要]}「ティックタックトー」は、 1558年に初めて記述されたバックギャモンの古いバージョンの名前である「ティックタック」に由来している可能性もある。米国で「ゼロとクロス」が「ティックタックトー」に改名されたのは、20世紀になってからである。^[12]

1952年、イギリスのコンピュータ科学者サンディ・ダグラスがケンブリッジ大学のEDSACコンピュータ用に開発したOXO（またはNoughts and Crosses ）は、世界初のビデオゲームの一つとなった。^{[13] [14]}コンピュータプレイヤーは、人間の相手と三目並べの完璧なゲームをプレイすることができた。^[13]

1975年には、 MITの学生たちがティンカートイの計算能力を実証するために三目並べを使った。ティンカートイのコンピューターは（ほぼ）ティンカートイだけで作られており、三目並べを完璧にプレイできる。^{[15]現在、}コンピューター歴史博物館に展示されている。^[16]

盤面の状態だけを考え、盤面の対称性（回転や反射）を考慮すると、盤面の終端位置は138個しかない。ゲームの組み合わせ論的研究によると、毎回「X」が先手を取ると、ゲームの結果は次のようになる。^[17]

• 91の異なるポジションは（X）によって獲得される
• 44の異なるポジションは（O）によって獲得される。
• 3つの異なるポジションが描かれる（「猫のゲーム」と呼ばれることが多い^[18]）

プレイヤーは、ニューウェルとサイモンの1972年の三目並べプログラムで使用されているように、自分の番になるたびに次のリストから最初の利用可能な動きを選択すれば、三目並べの完璧なゲームをプレイすることができます（勝つか少なくとも引き分け）。[ ^19]

1. 勝利: プレイヤーが 2 つ連続している場合、3 つ目を配置して 3 つ連続にすることができます。
2. ブロック: 相手が 2 回連続でブロックした場合、プレイヤーは相手をブロックするために 3 回目を自分でプレイする必要があります。
3. フォーク: プレイヤーが勝つ方法が 2 つあるシナリオ (ブロックされていない 2 つのライン) を発生させます。
4. 相手のフォークをブロックする: 相手がフォークを 1 つしか出せない場合、プレーヤーはそれをブロックする必要があります。そうでない場合、プレーヤーは、同時に 2 つ連続でフォークを行えるように、すべてのフォークをブロックする必要があります。そうでない場合、プレーヤーは、フォークが出ない限り、2 つ連続でフォークを出して、相手を守備に追い込む必要があります。たとえば、「X」が 2 つの反対側のコーナーを持ち、「O」がセンターを持っている場合、「O」はコーナー ムーブで勝ってはいけません。(このシナリオでコーナー ムーブをすると、「X」が勝つフォークが生成されます。)
5. センター: プレーヤーはセンターをマークします。(ゲームの最初の動きの場合、コーナーの動きをすると、2 番目のプレーヤーがミスを犯す機会が増えるため、より良い選択になる可能性があります。ただし、完璧なプレーヤーの間では違いはありません。)
6. 反対のコーナー: 相手がコーナーにいる場合、プレーヤーは反対のコーナーでプレーします。
7. 空のコーナー: プレイヤーはコーナーのマス目でプレイします。
8. 空いている側: プレイヤーは 4 つの側のいずれかの中央のマス目でプレイします。

最初のプレーヤー（「X」と表記）は、最初のターンにマークできる戦略的に異なる 3 つの位置があります。表面的には、グリッドの 9 つのマス目に対応する 9 つの位置があるように見えるかもしれません。しかし、ボードを回転させると、最初のターンでは、すべてのコーナー マークが他のすべてのコーナー マークと戦略的に同等であることがわかります。同じことは、すべてのエッジ (サイド ミドル) マークにも当てはまります。したがって、戦略的な観点からは、最初のマークはコーナー、エッジ、またはセンターの 3 つしかありません。プレーヤー X は、これらの開始マークのいずれかから勝つか、引き分けを強制することができます。ただし、コーナーをプレイすると、相手は負けを避けるためにプレイしなければならないマス目の選択肢が最小限になります。^[20]これは、コーナーが X にとって最良の開始手であることを示唆している可能性がありますが、別の研究^[21]では、プレーヤーが完璧でない場合は、センターでの開始手が X にとって最善であることが示されています。

2 番目のプレーヤー (「O」と指定) は、X のオープニング マークに対して、強制勝利を回避する方法で応答する必要があります。プレーヤー O は、コーナー オープニングには常にセンター マークで応答し、センター オープニングにはコーナー マークで応答する必要があります。エッジ オープニングには、センター マーク、X の隣のコーナー マーク、または X の反対側のエッジ マークのいずれかで応答する必要があります。その他の応答は、X が強制勝利を可能にします。オープニングが完了すると、O のタスクは、上記の優先順位リストに従ってドローを強制するか、X が弱いプレイをした場合に勝利を得ることです。

より詳しく言うと、引き分けを保証するために、O は以下の戦略を採用する必要があります。

• X がコーナーオープニングムーブをした場合、O はセンターを取り、次にエッジを取り、X に次のムーブでブロックを強いる必要があります。これにより、フォークが起こらなくなります。X と O の両方がパーフェクトプレイヤーであり、X がコーナーをマークして開始することを選択した場合、O はセンターを取り、X は元のコーナーの反対側のコーナーを取ります。その場合、O は 2 番目のムーブとして任意のエッジを自由に選択できます。ただし、X がパーフェクトプレイヤーではなく、コーナーをプレイしてからエッジをプレイした場合、O は 2 番目のムーブとして反対側のエッジをプレイするべきではありません。そうすると、X は次のムーブでブロックを強いられることがなくなり、フォークできます。
• X がエッジオープニングムーブをプレイする場合、O はセンターまたは X に隣接するコーナーの 1 つを取り、主にブロックフォークに注意しながら上記の優先順位リストに従う必要があります。完璧なプレイであれば、O は X の反対のエッジを取ることでドローを強制することもできます。
• X がセンターオープニングムーブをプレイする場合、O はコーナーを取り、主にブロックフォークに注意しながら上記の優先順位リストに従います。

X が最初にコーナーをプレーし、O が完璧なプレーヤーでない場合は、次のことが起こる可能性があります。

• O がセンターマークで応答した場合 (彼らにとって最善の動き)、完璧な X プレーヤーは元のコーナーの反対側のコーナーを取ります。次に、O はエッジをプレイする必要があります。ただし、O が 2 番目の動きとしてコーナーをプレイした場合、完璧な X プレーヤーは残りのコーナーをマークし、O の 3 連続をブロックして、独自のフォークを作成します。
• O がコーナーマークで応答した場合、X が勝つことが保証されます。他の 2 つのコーナーのいずれかを取ることで、O は 2 つの X の間の位置しか取れなくなり、残りのコーナーを取ってフォークを作成することで、次の動きで X が勝ちます。
• O がエッジマークで応答した場合、X が勝つことが保証されます。センターを取ることで、O は X が最初にプレイしたコーナーの反対側のコーナーしか取ることができません。その後、コーナーを取ってフォークを作成することで、次の動きで X が勝ちます。

次のように番号が付けられた 9 つの位置を持つボードを考えてみましょう。

X が最初の動きとして 1 をプレイした場合、O は 5 を取る必要があります。その後、X は 9 を取ります (この状況では、O は 3 または 7 を取るべきではなく、2、4、6、または 8 を取る必要があります)。

• X1 → O5 → X9 → O2 → X8 → O7 → X3 → O6 → X4、このゲームは引き分けになります。

または 6 (この状況では、O は 4 や 7 を取るべきではなく、2、3、8、または 9 を取る必要があります。実際、9 を取るのが最善の動きです。これは、完璧でないプレーヤー X が 4 を取った場合、O が 7 を取って勝つことができるためです)。

• X1 → O5 → X6 → O2 → X8 の場合、O は 3 を取ってはならず、X は 7 を取って勝つことができ、O は 4 を取ってはならず、X は 9 を取って勝つことができ、O は 7 または 9 を取る必要があります。
  • X1 → O5 → X6 → O2 → X8 → O7 → X3 → O9 → X4、このゲームは引き分けになります。
  • X1 → O5 → X6 → O2 → X8 → O9 → X4 (7) → O7 (4) → X3、このゲームは引き分けになります。
• X1 → O5 → X6 → O3 → X7 → O4 → X8 (9) → O9 (8) → X2、このゲームは引き分けになります。
• X1 → O5 → X6 → O8 → X2 → O3 → X7 → O4 → X9、このゲームは引き分けになります。
• X1 → O5 → X6 → O9 の場合、X は 4 を取ってはならず、O は 7 を取って勝つことができます。X は 2、3、7、または 8 を取る必要があります。
  • X1 → O5 → X6 → O9 → X2 → O3 → X7 → O4 → X8、このゲームは引き分けになります。
  • X1 → O5 → X6 → O9 → X3 → O2 → X8 → O4 (7) → X7 (4)、このゲームは引き分けになります。
  • X1 → O5 → X6 → O9 → X7 → O4 → X2 (3) → O3 (2) → X8、このゲームは引き分けになります。
  • X1 → O5 → X6 → O9 → X8 → O2 (3, 4, 7) → X4/7 (4/7, 2/3, 2/3) → O7/4 (7/4, 3/2, 3/2) → X3 (2, 7, 4)、このゲームは引き分けになります。

どちらの状況でも（Xが2手目に9か6を取る）、Xは⁠1/3⁠勝つための財産。

X が完璧なプレイヤーでない場合、X は 2 手目または 3 手目を取る可能性があります。その場合、このゲームは引き分けとなり、X は勝つことができません。

• X1 → O5 → X2 → O3 → X7 → O4 → X6 → O8 (9) → X9 (8)、このゲームは引き分けになります。
• X1 → O5 → X3 → O2 → X8 → O4 (6) → X6 (4) → O9 (7) → X7 (9)、このゲームは引き分けになります。

X が 1 回目のオープニング ムーブを行い、O が完璧なプレーヤーでない場合は、次のことが起こる可能性があります。

Oは最初の動きとして唯一の良い位置（5）を取りますが、Oは2番目の動きとして悪い位置を取ります。

• X1 → O5 → X9 → O3 → X7 とすると、X は 4 または 8 を取って勝利できます。
• X1 → O5 → X6 → O4 → X3 の順で進み、X は 7 または 9 を取れば勝利します。
• X1 → O5 → X6 → O7 → X3 の順で進み、X は 2 または 9 を取って勝利します。

O は最初の 2 手で良いポジションを取りますが、3 手目で悪いポジションを取ります。

• X1 → O5 → X6 → O2 → X8 → O3 → X7 の順で進み、X は 4 または 9 を取って勝利します。
• X1 → O5 → X6 → O2 → X8 → O4 → X9 の順で進み、X は 3 または 7 を取れば勝利します。

O は最初の動きとして悪い位置を取ります (5 を除いて、他のすべての位置は悪いです):

• X1 → O3 → X7 → O4 → X9 とすると、X は 5 または 8 を取って勝利できます。
• X1 → O9 → X3 → O2 → X7 とすると、X は 4 または 5 で勝利できます。
• X1 → O2 → X5 → O9 → X7 とすると、X は 3 または 4 を取って勝利できます。
• X1 → O6 → X5 → O9 → X3 の順で進み、X は 2 または 7 を取れば勝ちます。

多くのボードゲームには、最初にn を一列に並べるという共通の要素があり、これにはスリー・メンズ・モリス、ナイン・メンズ・モリス、ペンテ、五目並べ、キュービック、コネクト・フォー、クアルト、ゴブレット、オーダー・アンド・カオス、トス・アクロス、モジョが含まれます。三目並べはm,n,k ゲームの一例であり、2 人のプレーヤーがm × n のボード上で交互にプレイし、どちらかがk を一列に並べるまでプレイします。Hararyの一般化された三目並べは、さらに広く一般化されています。このゲームは、行がハイパーエッジでセルが頂点である任意のハイパーグラフでプレイすることで、さらに一般化できます。

三目並べの他のバリエーションには以下のものがあります。

• 3×3×3 のボード上での 3 次元の三目並べ。このゲームでは、2 人でプレイする場合、最初のプレイヤーが中央でプレイすると簡単に勝ちます。

4x4 のマス目があるボードでプレイし、勝つ方法はいくつかあります。勝つ方法は、4 を直線に並べる、4 を斜めに並べる、4 をダイヤモンド形に並べる、または 4 を正方形に並べる、などです。

もう一つのバリエーションであるQubicは4×4×4のボードでプレイされ、 1980年にOren Patashnikによって解決されました（最初のプレーヤーが勝利を強制することができます）。^[22]より高次元のバリエーションも可能です。^[6]

• ミゼール三目並べでは、相手がnを連続で出せば勝ちです。^[23] 3×3のゲームは引き分けです。より一般的には、最初のプレイヤーは、最初に中央のセルにプレイし、次に相手の動きをミラーリングすることで、辺の長さが奇数である任意のボード（任意の寸法）で引き分けまたは勝つことができます。^[6]

• 「ワイルド」な三目並べでは、プレイヤーは各移動ごとにXかOのどちらかを置くことを選択できます。^{[24] [25] [26]}
• ナンバースクラブルまたはピック15 ^{[27] は}三目並べと同型だが、表面的には全く違うように見える。 ^[28] 2人のプレイヤーが順番に1から9までの数字を言う。特定の数字が重複してはならない。合計が15になる3つの数字を言ったプレイヤーがゲームに勝つ。^{[27] [29]}すべての数字が使われ、誰も合計が15になる3つの数字を言わなかった場合、ゲームは引き分けとなる。^[27]これらの数字を3×3の魔方陣にプロットすると、3つの数字が直線に並ぶのは合計が15になる場合のみであるため、このゲームは三目並べと正確に一致することがわかる。^[30]

• 別の同型ゲームでは、慎重に選ばれた9つの単語のリストを使用します。たとえば、「try」、「be」、「on」、「any」、「boat」、「by」、「ten」、「or」、「fear」などです。各プレーヤーは順番に1つの単語を選択し、勝つためには、同じ文字を含む3つの単語を選択する必要があります。単語は、3つ並んだ線が勝つように、三目並べのグリッド上にプロットできます。^[31]
• 数字三目並べは、数学者ロナルド・グラハムが考案したゲームの一種です。このゲームでは 1 から 9 までの数字を使用します。最初のプレイヤーは奇数でプレイし、2 番目のプレイヤーは偶数でプレイします。すべての数字は 1 回のみ使用できます。15 ポイントを一列に並べたプレイヤーが勝ちます (3 つの数字の合計)。
• 1970年代に、トライアング・トイズ＆ゲームズ社が作った2人用ゲーム「チェックラインズ」があった。このゲームでは、ボードには11個の穴があり、 12本の直線の幾何学的パターンに沿って各直線に3つの穴がある。各プレイヤーはちょうど5個のトークンを持ち、順番にいずれかの穴にトークンを1個ずつ置いていく。トークンが3個ずつ2列に並んだプレイヤーが勝者となる（定義上、交差する線）。10ターン目までにどちらのプレイヤーも勝てなかった場合、次のターンでは自分のトークンを残りの空いている穴に1つ移動させるが、この移動は隣接する穴からのみ行えるという制約があった。^[32]
• 古典的な3×3フィールドを使ったゲームのバリエーションもあり、勝つためには2列を作る必要があるが、反対のアルゴリズムでは1列だけでよい。^[33]
• 量子三目並べでは、プレイヤーはボード上に数字の量子的な重ね合わせを置くことができる。つまり、プレイヤーの動きは元の古典的なゲームでのプレイの「重ね合わせ」である。このバリエーションは、Novatia LabsのAllan Goffによって発明された。^[34]

• 1876年にジョージ・クーパーが歌詞を書き、ジョン・ロジャース・トーマスが曲「Tit, Tac, Toe」を書いた。^[35]
• 『ディス・アメリカン・ライフ』第452話^[36]は、フロリダ州が精神障害のある殺人犯を死刑に処す決定を覆そうと、証拠として三目並べをするニワトリを引き出しようとした弁護団の実話を描いている。三目並べをするニワトリのアーケードゲームは1970年代半ばに人気があった。動物はオペラント条件付けを用いて訓練され、^[37]動きはコンピュータによって選択され、人間のプレイヤーには見えない光でニワトリに示された。^[38]
• 1983年のSF映画『ウォー・ゲーム』では、世界的熱核戦争は三目並べに似ていると描写されており、すべての陣営が可能な限り最も効果的な戦略で兵器を全面的に使用した場合、実際にはどちらの陣営も勝利することはない。

様々なゲーム番組が三目並べとその派生ゲームに基づいている: ^[要出典]

• ハリウッド スクエアでは、9 人の有名人が三目並べのマス目を埋め、プレーヤーは有名人の質問に対する答えに正しく同意するか反対するかでボードに記号を配置します。このショーのバリエーションには、ストーリーブック スクエアやヒップホップ スクエアなどがあります。英国版はセレブリティ スクエアでした。オーストラリアには、セレブリティ スクエア、パーソナリティ スクエア、オール スター スクエアという名前でさまざまなバージョンがありました。
• Tic-Tac-Doughでは、プレイヤーはさまざまなカテゴリの質問に答えることでボード上にシンボルを配置し、両方のプレイヤーが両方のターンを終えるとシンボルがシャッフルされます。
• Beat the Teacherでは、出場者は質問に答えて、三目並べのグリッドに影響を与える順番を勝ち取ります。
• 『ザ・プライス・イズ・ライト』では、いくつかの国別バージョンで「シークレットX」と呼ばれる価格ゲームが登場します。このゲームでは、プレイヤーは2つの小さな賞品の価格を推測して、X（無料のX1つに加えて）を獲得し、それを空白のボードに配置する必要があります。プレイヤーは、ボードの中央の列に隠された「シークレットX」の位置を推測して、Xを所定の位置に配置して、水平（横）または斜め（垂直線は許可されません）に三目並べの線を形成する必要があります。このバージョンのゲームにはOはありません。
• Minute to Win It のPing Tac Toe ゲームでは、1 人の出場者が 9 つの水を入れたグラスと白とオレンジ色のピンポン玉を使って、どちらかの色を 3 つ一列に並べることを競います。着地が成功するたびに色を交互に変え、邪魔にならないように注意する必要があります。

• ヘイルズ・ジューエット定理
• m、n、kゲーム
• ナンバースクラブル

• Wiktionary の tic-tac-toe の辞書定義
• ウィキメディア・コモンズの「三目並べ」に関連するメディア
• 「三目並べ」。Wolfram MathWorld。 2002 年 3 月 11 日。
• 「語源 – 三目並べで同点になった場合、なぜ「猫のゲーム」と呼ばれるのか？」。英語言語と使用法の Stack Exchange。2014年 3 月 5 日。– 三目並べの絵札ゲームを「猫のゲーム」と呼ぶことについての議論