私はTic-Tac-Toeゲームの実装戦略を設計しています。これは私の最初のゲーム実装なので、少し混乱していて、いくつかの一般的なポインタが必要です。
現在、Tic-Tac-Toeの勝ちの組み合わせの総数は8です。現在、これらの勝ちの組み合わせを配列に格納する予定です。エンドユーザーが少なくとも3回移動したら、プレーヤーが使用している現在の位置をこの配列と比較して、プレーヤーがゲームに勝ったかどうかを確認し始めます。ただし、これは、プレーヤーが勝ちの組み合わせを持っているかどうかを確認するための効率的な方法ではないと確信しています。
ゲームのロジックを設計する方法について誰かに提案してもらえますか？
効率について心配する必要はありません。バックトラッキング ソリューションを作成しましたが、考えられるゲーム ステートは 549,945 しかありません。私のラップトップでこれらを実行するのに 0.25 秒もかかりません。ゲームが終了したかどうかを確認するための私のロジックは次のとおりです。明らかにあまり効率的ではありませんが、問題ではありません。
private boolean isWinningMove(int row, int col) {
int piece = board[row][col];
// check current row
boolean w = true;
for (int x = 0; x < 3; x++) { w = w && (board[row][x] == piece); }
if (w) { return true; }
// check current column
w = true;
for (int x = 0; x < 3; x++) { w = w && (board[x][col] == piece); }
if (w) { return true; }
// check 0,0 diagonal
w = true;
for (int x = 0; x < 3; x++) { w = w && (board[x][x] == piece); }
if (w) { return true; }
// check 0,2 diagonal
w = true;
for (int x = 0; x < 3; x++) { w = w && (board[x][2 - x] == piece); }
return w;
}
これが、三目並べのウィキペディア ページのデータと一致する私の結果です。
Moves Simulated: 549945
Draws=46080 Player1-Wins=131184 Player2-Wins=77904
Perfect Strategy Implies: Always a tie.
Games won in 0 moves? 0
Games won in 1 moves? 0
Games won in 2 moves? 0
Games won in 3 moves? 0
Games won in 4 moves? 0
Games won in 5 moves? 1440
Games won in 6 moves? 5328
Games won in 7 moves? 47952
Games won in 8 moves? 72576
Games won in 9 moves? 81792
tic-tac-toe の状態空間は非常に小さいため、可能なすべてのエンド ゲーム ポジションを格納し、ローテーションを使用できますが、少し考えすぎていると思います。
ゲーム ボードの 3x3 配列を格納する代わりに、ゲーム ボードの最も内側の 3x3 で 7x7 配列を使用します。各正方形が表すことができる少なくとも 3 つの値PLAYER_1( 、 、PLAYER_2など) が必要NONEです。最初は、すべての値を に設定する必要がありますNONE。次に、すべてのプレーヤーが移動した後、3 列に並んでいるために選択された正方形の周りをすべてチェックします。上に 2 つ、下に 2 つ、左に 2 つ、右に 2 つ、左上に 2 つ、右下に 2 つ、右上に 2 つ、左下に 2 つ。
なぜ 7x7 アレイなのか? 7x7 配列を使用すると、3x3 エリア内の任意の正方形から全方向を安全に検索できifます。配列の端から離れているかどうかを確認するステートメントは必要ありません。ボードは次のようになります。
0 1 2 3 4 5 6 0 * * * * * * * 1 * * * * * * * 2 * * * * * * * 3 * * * * * * * 4 * * * * * * * 5 * * * * * * * 6 * * * * * * *
たとえば、最初のプレイヤーが三目並べボードで 0,0 に移動する場合、7x7 ボードで 2,2 に移動するのと同じです。移動が行われると、同じ値を持つ 3 つの正方形が連続して存在するかどうかを確認するために、2,2 の正方形全体をチェックします。
3x3 ボードの周りの正方形の帯は常に の値を持つためNONE、勝利条件をトリガーすることはできません。
それらのいずれかが同じプレーヤー値 (たとえば、最初のプレーヤーの PLAYER_1) と一致する場合、ゲームは勝利で終了します。それ以外の場合、すべてのマスが取られた場合、ゲームは引き分けになります。
過去に他の同様のゲームでこれを使用しましたが、非常にうまく機能します。
ボードを整数で表すことを検討してください。
-1 = X
0 = empty
1 = O
ここで、8 つの可能性 (上下に 3 つ、左右に 3 つ、斜めに 2 つ) のそれぞれの正方形の値を合計します。
合計が 3 の場合、O が勝ち、合計が -3 の場合、X が勝ちます。
合計が 2 の場合、O はそれらの位置の 1 つで勝ちの動きをします。合計 i -2 の場合、X はそれらの位置の 1 つで勝ちの動きをします。
AI はそれを意思決定の基礎として使用できます。決して負けないためには、一手先を見るだけで十分です。
AIがゲームを開始した場合、最良の動きはコーナーです。対戦相手がセンターを取ることができなかった場合、AI が勝ちます。彼がセンターを取った場合、AI が勝つか引き分けます。
何かを反復する代わりに、8 つの組み合わせを書きました。
私の評価関数は次のことを行います: A が移動する側である場合、およびすべての組み合わせの 1 つに 2 つの A 要素と 0 (空) がある場合、それは勝利です:
boolean player_can_win(int value) { //value is side's element*2
return board[0] + board[1] + board[2] == value
|| board[3] + board[4] + board[5] == value
|| board[6] + board[7] + board[8] == value
|| board[0] + board[3] + board[6] == value
|| board[1] + board[4] + board[7] == value
|| board[2] + board[5] + board[8] == value
|| board[0] + board[4] + board[8] == value
|| board[2] + board[4] + board[6] == value;
}
一般化された NXN tic-tac-toe をプレイしている場合、ソリューションを明示的に保存して比較することは最も効率的ではありませんが、小さなボードのようなものであり、そのようなコンボは 8 つしかないため、このようにソリューションを明示的に保存しても問題はありません。
より大きな問題は、ストレージ スタイルによっては、ソリューションに関係のないスペースが問題になる可能性があることです。
O - - - O -
X X X vs. X X X
O - O O - O
3x3 状態配列を比較すると、これらは異なります。そのため、この方法では 8 つをはるかに超える終了状態が必要になります。
blank=0, X=1, O=2 の gameState 3x3 配列のようなものを保持していると思いますか?
これらの明示的な比較に加えて、次のようなことができます
win = false
// rows/columns
for i in 0,1,2
if (state[i][0] != BLANK && state[i][0] == state[i][1] == state[i][2]) win = true
#extensible to NxN - all(j == state[i][0] for j in state[i])
if (state[0][i] != BLANK && state[0][i] == state[1][i] == state[2][i]) win = true
#extensible to NxN - all(j == state[0][i] for j in zip(*state)[i])
//diagonals
if (state[0][0] != BLANK && state[0][0] == state[1][1] == state[2][2]) win = true
#extensible to NxN - all(state[j][j] == state[0][0] for j in range(len(state))
if (state [2][0] != BLANK && state[2][0] == state[1][1] == state[0][2]) win = true
win がフラグではなく勝者を格納するようにしたい場合は、win = BLANK を一番上にして、関連する正方形のいずれかの値に設定します。必ずしも必要ではありませんが、勝者は明らかに最新の動きです!
三目並べを書く上で、最もやりがいがあると思うかもしれないが、それほど難しくないと思う部分は、AI だと思います。負けない AI を作成することは、それほど難しくはありませんが、まったく簡単なことではありません (常に少なくとも引き分けを強制することができます)。ときどき負ける可能性のある比較的優れた AI が必要な場合は、ランダム性などを追加する必要があります。