Los juegos combinatorios son juegos de dos personas con información perfecta.y no hay movimientos aleatorios (no se trata de aleatorización como el lanzamiento de una moneda que puede afectar el juego). Estos juegos tienen un resultado de ganar o perder o empate y están determinados por un conjunto de posiciones, incluida una posición inicial y el jugador al que le toca moverse. El juego se mueve de una posición a otra, y los jugadores generalmente alternan movimientos, hasta que se alcanza una posición terminal. Una posición terminal es aquella desde la que no es posible ningún movimiento. Entonces uno de los jugadores es declarado ganador y el otro perdedor. O hay un empate (Dependiendo de las reglas del juego combinatorio, el juego podría terminar en un empate. Lo único que se puede afirmar sobre el juego combinatorio es que el juego debe terminar en algún punto y no debe quedarse atrapado en un bucle. Para evitar tales situaciones de bucle en juegos como el ajedrez (considere el caso de que ambos jugadores muevan sus reinas de un lugar a otro), en realidad existe una «regla de 50 movimientos» según la cual el el juego se considera empatado si los últimos 50 movimientos de cada jugador se han completado sin el movimiento de ningún peón y sin ninguna captura. [Fuente :intercambio de pila ]
Por otro lado, la teoría de juegos en general incluye juegos de azar, juegos de conocimiento imperfecto y juegos en los que los jugadores pueden moverse simultáneamente.
La especialidad de la teoría de juegos combinatorios (CGT) es que la parte de codificación es relativamente muy pequeña y fácil. La clave de los problemas de la teoría de juegos es esa observación oculta, que a veces puede ser muy difícil de encontrar.
Ajedrez, Juego de Nim, Tic-Tac-Toe, todos entran en la categoría de Teoría de Juegos Combinatorios.
Podemos dividir estos juegos en dos categorías como se muestra a continuación:
La diferencia entre ellos es que en Imparcial Games todos los movimientos posibles desde cualquier posición del juego son los mismos para los jugadores, mientras que en Partisan Games los movimientos para todos los jugadores no son los mismos .
Considere un juego como el siguiente:
Dada una cantidad de pilas en las que cada pila contiene una cierta cantidad de piedras/monedas. En cada turno, el jugador elige una pila y retira cualquier cantidad de piedras (al menos una) de esa pila. Se considera que el jugador que no puede moverse pierde el juego (es decir, el que toma la última piedra es el ganador).
Como puede verse claramente a partir de las reglas del juego anterior, los movimientos son los mismos para ambos jugadores. No hay restricción de un jugador sobre el otro. Tal juego se considera imparcial.
El juego mencionado anteriormente es famoso por el nombre: Juego de Nim , que se discutirá en las próximas secciones.
En contraste con el juego anterior, tomemos un ejemplo de ajedrez . En este juego, un jugador solo puede mover las piezas negras y el otro solo puede mover las blancas. Por lo tanto, hay una restricción para ambos jugadores. Su conjunto de movimientos es diferente y, por lo tanto, dicho juego se clasifica en la categoría de Juegos Partisanos .
Los juegos partidistas son mucho más difíciles de analizar que los juegos imparciales, ya que en tales juegos falla el teorema de Sprague-Grundy .
En las siguientes secciones, veremos principalmente juegos imparciales, como el juego de Nim y sus variaciones, el teorema de Sprague-Grundy y muchos más.
Ejercicio: Los lectores pueden intentar resolver los siguientes problemas simples de teoría de juegos combinatorios.
Fuentes:
http://www.cs.cmu.edu/afs/cs/academic/class/15859-f01/www/notes/comb.pdf
https://en.wikipedia.org/wiki/Combinatorial_game_theory
https://en.wikipedia.org/wiki/Impartial_game
https://en.wikipedia.org/wiki/Partisan_game
Este artículo es una contribución de Rachit Belwariar . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo y enviarlo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA