Teoría de los juegos combinatorios
La teoría de los juegos combinatorios, también conocida como CGT, es una rama de la matemática aplicada y la informática teórica que estudia los juegos combinatorios, y se distingue de la teoría de los juegos "tradicional" o "económica". La CGT surgió en relación con la teoría de los juegos imparciales, el juego de dos jugadores del Nim en particular, haciendo hincapié en la "resolución" de ciertos tipos de juegos combinatorios.
Un juego debe cumplir varias condiciones para ser un juego combinatorio. Estas son:
- El juego debe tener al menos dos jugadores.
- El juego debe ser secuencial (es decir, los jugadores se alternan los turnos).
- El juego debe tener información perfecta (es decir, no se oculta ninguna información, como en el póker).
- El juego debe ser determinista (es decir, sin azar). La suerte no forma parte del juego.
- El juego debe tener una cantidad definida de movimientos posibles.
- El juego debe terminar eventualmente.
- El juego debe terminar cuando uno de los jugadores ya no pueda moverse.
La teoría de los juegos combinatorios se limita en gran medida al estudio de un subconjunto de juegos combinatorios de dos jugadores, finitos y con un ganador y un perdedor (es decir, que no terminan en empate).
Estos juegos combinatorios pueden representarse mediante árboles, cada uno de cuyos vértices es el juego resultante de una determinada jugada del juego situado directamente debajo de él en el árbol. A estos juegos se les pueden asignar valores de juego. Encontrar estos valores de juego es de gran interés para los teóricos del CG, al igual que el concepto teórico de suma de juegos. La suma de dos juegos es el juego en el que cada jugador, en su turno, debe mover sólo en uno de los dos juegos, dejando el otro como estaba.
Elwyn Berlekamp, John Conway y Richard Guy son los fundadores de la teoría. Trabajaron juntos en la década de 1960. Su obra publicada se llamó Winning Ways for Your Mathematical Plays.
Definiciones
En la teoría, hay dos jugadores llamados izquierda y derecha. Un juego es algo que permite a la izquierda y a la derecha hacer movimientos a otros juegos. Por ejemplo, en el juego del ajedrez, hay una configuración inicial habitual. Sin embargo, también se puede pensar en una partida de ajedrez después del primer movimiento como un juego diferente, con una configuración diferente. Por lo tanto, cada posición también se denomina partida.
Las partidas tienen la notación {L|R}. L {estilo de visualización L}
son las partidas a las que se puede mover el jugador de la izquierda. R {\displaystyle R}
son las partidas a las que puede moverse el jugador de la derecha. Si conoce la notación del ajedrez, la configuración habitual del ajedrez es el juego
| { a 3 , a 4 , N a 3 , b 3 , b 4 , c 3 , c 4 , N c 3 , ... | a 6 , a 5 , N a 6 , b 6 , b 5 , c 6 , c 5 , N c 6 , ... } {\displaystyle \ {a3,a4,Na3,b3,b4,c3,c4,Nc3,\dots |a6,a5,Na6,b6,b5,c6,c5,Nc6,\dots \} |
Los puntos "..." significan que hay muchos movimientos, por lo que no se muestran todos.
El ajedrez es muy complejo. Es mejor pensar en juegos más fáciles. El Nim, por ejemplo, es mucho más sencillo de pensar. El Nim se juega así:
- Hay cero o más montones de fichas.
- En un turno, un jugador puede coger tantas fichas de un montón como quiera.
- El jugador que no pueda hacer un movimiento pierde.
La partida más fácil de Nim comienza sin fichas. En este caso, ninguno de los dos jugadores puede moverse. Esto se muestra como {|}. Ambos lados están vacíos, porque ninguno de los dos jugadores puede moverse. El primer jugador que se vaya no puede mover, y por lo tanto perderá. En CGT, la gente suele escribir {|} como el símbolo 0 (cero).
El siguiente juego más fácil tiene una sola pila, con una sola ficha. Si el jugador de la izquierda va primero, ese jugador debe tomar la ficha, dejando a la derecha sin movimientos ({|}, o 0). Si, por el contrario, la derecha mueve primero, no habrá más movimientos para la izquierda. Así que tanto la izquierda como la derecha pueden hacer un movimiento a 0. Eso se muestra como {{|}|{|}}, o {0|0}. El primer jugador que mueva ganará. Las partidas iguales a {0|0} son muy importantes. Se escriben con el símbolo, * (estrella).
Preguntas y respuestas
P: ¿Qué es la Teoría Combinatoria de Juegos?
R: La Teoría Combinatoria de Juegos (CGT) es una rama de las matemáticas aplicadas y la informática teórica que estudia los juegos combinatorios, y es distinta de la teoría de juegos "tradicional" o "económica".
P: ¿Qué condiciones debe cumplir un juego para ser considerado un juego combinatorio?
R: Para que un juego se considere un juego combinatorio, debe tener al menos dos jugadores, debe ser secuencial (es decir, los jugadores alternan turnos), debe tener información perfecta (es decir, no hay información oculta), debe ser determinista (es decir, no azaroso), la suerte no puede formar parte del juego, debe haber una cantidad definida de movimientos posibles, el juego debe terminar eventualmente y el juego debe terminar cuando uno de los jugadores ya no pueda mover más.
P: ¿En qué tipo de juegos se centra la Teoría Combinatoria de Juegos?
R: La Teoría Combinatoria de Juegos se centra principalmente en juegos finitos de dos jugadores que tienen ganadores y perdedores (es decir, que no terminan en tablas).
P: ¿Cómo se representan este tipo de juegos?
R: Estos tipos de juegos pueden representarse mediante árboles en los que cada vértice representa el juego resultante de un movimiento concreto del situado directamente debajo de él en el árbol.
P: ¿Cuáles son algunos objetivos para los teóricos del CG?
R: Algunos objetivos para los teóricos del CG incluyen encontrar valores para este tipo de juegos, así como comprender el concepto de "adición de juegos", que implica que cada jugador haga sólo un movimiento en dos juegos diferentes dejando el otro sin cambios durante su turno.
P: ¿Quién fundó la CGT?
R: Se atribuye a Elwyn Berlekamp, John Conway y Richard Guy la fundación de la CGT en su obra publicada titulada Winning Ways for Your Mathematical Plays en la década de 1960.
