algorithm - tic - Juego en el árbol, rama de corte

minimax algorithm

Question

Tenemos un bosque de árboles enraizados. Dos jugadores hacen movimientos alternativos de acuerdo con la siguiente regla: un movimiento es cortar el vértice y todos sus hijos. El jugador que hace el último movimiento (no quedan vértices) gana.

¿Cómo podemos calcular la función de Grundy para las posiciones en el juego?

Supongamos que tenemos un árbol y tenemos que decir si la posición actual está ganando o perdiendo.

Answer 1

Este es el juego de Hackenbush . Recomiendo encarecidamente este artículo , que cubre los números de Grundy con gran claridad y analiza a fondo hackenbush hacia el final.