java - チックタックトーゲームの勝者を見るための最適アルゴリズム

Question

完成した三目並べゲームボードがあります。それは 3 x 3 です。私は実際にはコードを求めているわけではありません (それは役に立ちますが)。別の言い方をすれば、誰が勝ったかを知るのに役立つアルゴリズムを調査する必要がありますか?

本当に頭に浮かぶのは、ブルートフォースだけです。すべての可能性をテストするだけですが、もっと良い方法があるはずです。

Answer 1

私が最近（再）学んだ重要な教訓：検索スペースが十分に小さい場合は、ブルートフォースを使用するだけです。

3x3ボードには、8つの勝ちシーケンス（行、列、対角線）があります。これにより、24の比較が可能になり、すべてのセルに同じプレーヤーのマークが付いているかどうかを確認できます。非常に遅いコンピューターでも、24回の比較に時間がかかりません。

Answer 2

これが最高の、巧妙で最適なアルゴリズムです: (これはよく知られたトリックなので、自慢するのではなく、アルゴリズムを賞賛するだけです)

定義: セルの名前は次のとおりです。

A31  A32  A33
A21  A22  A23
A11  A12  A13

ピースはW（ハイト）またはB（欠如）です。[A11,A12,A13]、[A11,A21,A31]、[A13,A22,A31] などの 8 つの勝ちの組み合わせがあります。各組み合わせに名前を付けます: C1..C8.:

C1 =def= [A11,A12,A13]
C2 =def= [A21,A22,A23]
C3 =def= [A31,A32,A33]
C4 =def= [A11,A21,A31]
C5 =def= [A12,A22,A32]
C6 =def= [A13,A23,A33]
C7 =def= [A11,A22,A33]
C8 =def= [A13,A22,A31]

セルから一連の勝利の組み合わせへのマッピングを定義します。

A11 --> C1,C4,C7
A12 --> C1, C5
A22 --> C2, C5, C7, C8

等

したがって、すべてのセル A は、A を含む組み合わせを指します。

両方のプレーヤーの可能な勝利の組み合わせのセットを保持します。最初は、両方のプレイヤーが 8 つの組み合わせすべてを持っています。

Poss_W = C1, C2, C3, C4, C5, C6, C7, C8
Poss_B = C1, C2, C3, C4, C5, C6, C7, C8

W がセル A でプレイする場合、対応するウィニング コンビネーションを B から削除します。たとえば、ホワイトが A12 をプレイする場合、ブラックの可能なウィニング コンビネーション リストから C1、C5 を削除します。

ゲームが終了した後、空でない可能性のある勝ちの組み合わせセットを持つプレーヤーが勝ちます。Poss_W と Poss_B の両方が空の場合、ゲームは引き分けです。

Answer 3

マップを使用するだけdiagonal -> number of checks in that diagonalです。

エントリの 1 つが 3 つに等しい場合、勝者がいます。

Answer 4

各ステップの後にゲームが終了したかどうかを確認する必要がある場合は、一時的な結果をキャッシュできます。

行、列、および対角線ごとに、各プレーヤーのマーク数を格納します。各ステップの後、適切な値を増やします。数字が 3 の場合、勝者がいます。

Answer 5

ボード全体の状態をチェックせずに勝者を決定する方法はありません。各ターンの最後にチェックを実行する場合は、各行、列、および両方の対角線を繰り返し、等しいかどうかをチェックします (例:board[0][0] == board[1][0] == board[2][0]など)。三目並べゲームのプレイ中にボードの状態を追跡したい場合は、動的計画法を使用できますが、これは非常にやり過ぎです。動的なアプローチは、勝者を見つけるために膨大な数のステップを必要とする異常に大きなボードを使用している場合に役立ちます。また、標準的な三目並べは十分に小さいため、効率的なアルゴリズムがパフォーマンスにまったく影響を与えないことにも注意してください。