algorithm - muse - algoritmo para comprobar un campo de conexión de cuatro

characteristics of an algorithm

Question

Me pregunto cuál es la mejor manera de buscar un ganador en un campo de cuatro conectados.

¿Me interesa lo que piensan y si existe algún algoritmo "bien conocido" para este tipo de problemas?

Solución:

Implementé la solución de tabla hash de Ardavan en Python.

Dejé que el algoritmo pasara por todos los campos una vez. El mejor tiempo de verificación con mi implementación fue de 0.047 ms, el peor de 0.154 ms y el promedio de 0.114 ms en mi CPU Intel (R) Core (TM) 2 Duo T9600 @ 2.80GHz. Esto es lo suficientemente rápido para mis necesidades, y el algoritmo me parece limpio.

Answer 1

Cada celda solo puede atribuirse a un número máximo de 12 combinaciones ganadoras. (4 horizontales, 4 verticales y 4 diagonales). Cada combinación tendría 4 celdas, incluida la que se considera. Y estos números serán mucho más bajos para las celdas más cercanas a los lados. Por lo tanto, tendría sentido compilar previamente estas combinaciones y almacenar un hash de hash de celdas relacionadas que pueden hacer que una sola jugada sea ganadora. De esta manera, después de que cada celda sea jugador, simplemente saque las combinaciones / celdas relacionadas para comprobar si es un ganador.

Answer 2

El código fuente de Fhourstones Benchmark de John Tromp utiliza un algoritmo fascinante para probar una conexión de cuatro juegos para ganar. El algoritmo utiliza la siguiente representación de bitboard del juego:

. . . . . . . TOP
5 12 19 26 33 40 47
4 11 18 25 32 39 46
3 10 17 24 31 38 45
2 9 16 23 30 37 44
1 8 15 22 29 36 43
0 7 14 21 28 35 42 BOTTOM

Hay un bitboard para el jugador rojo y otro para el jugador amarillo. 0 representa una celda vacía, 1 representa una celda llena. El bitboard se almacena en una variable entera sin firmar de 64 bits. Los bits 6, 13, 20, 27, 34, 41,> = 48 deben ser 0 .

El algoritmo es:

// return whether ''board'' includes a win
bool haswon(unsigned __int64 board)
{
unsigned __int64 y = board & (board >> 6);
if (y & (y >> 2 * 6)) // check / diagonal
return true;
y = board & (board >> 7);
if (y & (y >> 2 * 7)) // check horizontal
return true;
y = board & (board >> 8);
if (y & (y >> 2 * 8)) // check / diagonal
return true;
y = board & (board >> 1);
if (y & (y >> 2)) // check vertical
return true;
return false;
}

Tienes que llamar a la función para el bitboard del jugador que hizo el último movimiento. Intento explicar el algoritmo en mi respuesta a la pregunta "¿Cómo determinar el final del juego, en tic-tac-toe?" .

Answer 3

Esto se relaciona con esta pregunta: ¿Cómo encontrar al ganador de un juego de tres en tres en tic-tac-toe?

El giro es el tablero de 7x6 con 4 en una fila ganando en lugar de un tablero NxN con N en una fila ganadora. Pero es trivial adaptar la solución a NxN tic tac toe para conectar 4.

EDIT: En realidad, no es del todo trivial adaptar la otra solución a esta. Pero puedes llegar con un poco de trabajo extra.

Almacene una cuenta para cada jugador por cada fila, columna, diagonal y anti-diagonal que pueda tener 4 piezas seguidas. Cuando ese conteo llegue a 4 o más para cada jugador, verifica si esa fila / columna / diagonal / anti-diagonal tiene las cuatro piezas en una fila. Si lo hace, ese jugador gana!