algoritmo para verificar un campo de conexión de cuatro

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

Me interesa lo que ustedes piensan y si existe algún algoritmo “conocido” para este tipo de problemas.

Solución:

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

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

Cada celda solo puede atribuir 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 precomstackr estas combinaciones y almacenar un hash de hash de celdas relacionadas que pueden hacer que una sola jugada sea ganadora. De esta forma, después de que cada célula sea jugador, simplemente extraiga las combinaciones / celdas relacionadas para verificar si es un ganador.

El código fuente de Fhourstones Benchmark de John Tromp usa un algoritmo fascinante para probar un juego connect four para ganar. El algoritmo usa 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 de 64 bits sin signo. Los bits 6, 13, 20, 27, 34, 41,> = 48 tienen que 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; } 

Debes llamar a la función del 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?” .

Esto está relacionado con esta pregunta: ¿Cómo encontrar al ganador de un juego de tres en raya de cualquier tamaño?

El giro es el tablero 7×6 con 4 triunfos consecutivos 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.

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

Almacene un conteo para cada jugador por cada fila, columna, diagonal y diagonal que pueda tener 4 piezas seguidas. Cuando ese conteo scope 4 o más para cualquiera de los jugadores, verifique si esa fila / columna / diagonal / anti-diagonal tiene las cuatro piezas en una fila. ¡Si lo hace, ese jugador gana!