c# - Algoritmo de IA perfecto de Tic Tac Toe: más profundo en el paso "crear un fork"

java algorithm

Question

Ya he leído muchos temas de Tic Tac Toe en StackOverflow. Y encontré que la estrategia en Wikipedia es adecuada para mi proyecto de presentación:

Un jugador puede jugar un tic-tac-toe perfecto si elige el movimiento con la mayor prioridad en la siguiente tabla [3].

1) Ganar: si tienes dos en fila, juega el tercero para obtener tres en fila.

2) Bloque: si el oponente tiene dos en fila, juega el tercero para bloquearlos.

3) Tenedor: Crea una oportunidad donde puedes ganar de dos maneras.

4) Bloquear la horquilla del oponente:

Opción 1: Crea dos en fila para forzar al oponente a defenderse, siempre y cuando no resulte en que creen un tenedor o ganen. Por ejemplo, si "X" tiene una esquina, "O" tiene el centro y "X" también tiene la esquina opuesta, "O" no debe jugar una esquina para ganar. (Jugar una esquina en este escenario crea una bifurcación para que "X" gane).

Opción 2: Si hay una configuración donde el oponente puede bifurcar, bloquea esa bifurcación.

5) Centro: Juega el centro.

6) Esquina opuesta: si el oponente está en la esquina, juega la esquina opuesta.

7) Esquina vacía: juega una esquina vacía.

8) lado vacío: jugar un lado vacío.

He seguido estos pasos, y la computadora nunca pierde. Sin embargo, la forma en que ataca no es perfecta. Porque no tengo ni idea de cómo hacer el paso 3. Esto es lo que hago en el paso 3: escanear cada celda, verificar si el token de esa celda crea un tenedor y luego lo coloca allí.

private void step3() // Create Fork.
{
int[] dummyField = (int[])field.Clone();
// Try Level 1 Dummy
for (int i = 0; i < 9; i++)
{
if (dummyField[i] != 0) continue;
dummyField[i] = 2;
if (countFork(dummyField, 2) >= 2)
{
nextCell = i;
return;
}
dummyField[i] = 0;
}
}

Por favor, dame un consejo sobre este paso.

EDIT1: El tenedor de conteo contará cuántas bifurcaciones tiene la computadora (las fichas de la computadora son 2, las fichas del jugador son 1, porque también utilicé ese método para el paso 4, así que hay un parámetro para la ficha en la función countFork ).

EDIT2: La razón por la que digo que no es perfecto es esto (la CPU va primero y sus celdas son azules, las celdas humanas son rojas). Como puede ver, si pongo en la celda superior, la computadora gana. Pero si pongo en la celda del lado derecho, es un empate, aunque la computadora todavía puede ganar.

EDIT3: No sé por qué, pero comenté el paso 3, y la computadora funciona ... ¡perfectamente! Estoy realmente sorprendido! Aquí está mi función countFork (necesito portar este código a Alice, que no es compatible con la matriz de 2 dimensiones, así que uso getNumberFromXY para convertir la matriz de 2 dimensiones en 1 dimensión):

private int countFork(int[] field, int token)
{
int result = 0;
// Vertical
int cpuTokenCount;
int spareCell;
for (int x = 0; x < 3; x++)
{
cpuTokenCount = 0;
spareCell = -1;
for (int y = 0; y < 3; y++)
{
if (field[getNumberFromXY(x, y)] == token)
cpuTokenCount++;
else if (field[getNumberFromXY(x, y)] == 0)
spareCell = getNumberFromXY(x, y);
}
if (cpuTokenCount == 2 && spareCell != -1) result++;
}
// Horizontal
for (int y = 0; y < 3; y++)
{
cpuTokenCount = 0;
spareCell = -1;
for (int x = 0; x < 3; x++)
{
if (field[getNumberFromXY(x, y)] == token)
cpuTokenCount++;
else if (field[getNumberFromXY(x, y)] == 0)
spareCell = getNumberFromXY(x, y);
}
if (cpuTokenCount == 2 && spareCell != -1) result++;
}
// Top-Left To Lower-Right Diagonal
cpuTokenCount = 0;
spareCell = -1;
for (int i = 0; i < 3; i++)
{
if (field[getNumberFromXY(i, i)] == token)
cpuTokenCount++;
else if (field[getNumberFromXY(i, i)] == 0)
spareCell = getNumberFromXY(i, i);
}
if (cpuTokenCount == 2 && spareCell != -1) result++;
// Top-Right To Lower-Left Diagonal
cpuTokenCount = 0;
spareCell = -1;
for (int i = 0; i < 3; i++)
{
if (field[getNumberFromXY(2 - i, i)] == token)
cpuTokenCount++;
else if (field[getNumberFromXY(2 - i, i)] == 0)
spareCell = getNumberFromXY(2 - i, i);
}
if (cpuTokenCount == 2 && spareCell != -1) result++;
return result;
}

EDIT4: FIJÓ el error de acuerdo con soandos, y actualicé el código en EDIT 3, ¡ahora funciona perfectamente!

Answer 1

No estoy seguro de que sea la forma más elegante de hacerlo, pero aquí hay una forma de mirar los tenedores en dos pasos.

Si la computadora no puede ganar el próximo turno, y no es el primero o el segundo, es posible que haya un tenedor (esto no se refiere a crear la configuración para un tenedor, solo encontrar un tenedor).

Para cada una de las celdas que están vacías, llénela, luego ejecute la función del paso 1 (vea si hay dos en una fila). Si encuentra dos lugares, felicidades, tienes un tenedor. Si no, no lo haces.