Descripción
La Teoría de Juegos Combinatorios presenta la base matemática para el desarrollo de las estrategias en estos juegos. La principal diferencia entre esta asignatura y la Teoría Clásica de Juegos es que en los juegos combinatorios hay dos jugadores que mueven alternativamente en lugar de hacerlo simultáneamente; en estos juegos además ambos jugadores disponen de perfecta información y no hay aleatoriedad en las jugadas.
Es una disciplina académica relativamente reciente. Los primeros análisis de juegos individuales aparecieron publicados en 1902, pero fue en 1930 cuando independientemente R. Sprague y P. M. Grundy desarrollaron una teoría para los juegos imparciales, que posteriormente fue ampliada por R. K. Guy y C. A. B. Smith. Desde entonces el interés por los juegos combinatorios va en aumento en una gran variedad de ramas: matemáticas, computación, inteligencia artificial etc.
El objetivo del curso es proporcionar la base matemática necesaria para el desarrollo de las estrategias en juegos combinatorios a la vez que se dan a conocer los más importantes y la forma de implementarlos en un ordenador.
Profesor
Programa
- Técnicas básicas
- Teorema fundamental
- Valores Sprague-Grundy
- Suma digital
- Suma de vértices
- Espacio vectorial de las posiciones
- Producto digital
Bibliografía
- Winning Ways for your Mathematical plays. Berlekamp. Conway. Guy. Academic Press.
- Games of No Chance. Richard J. Nowakowski Editor. Cambridge University Press.
- Relations and Graphs. Discrete Mathematics for Computer Scientists. Schmidt and Ströhlein. Springer-Verlag. EATCS Monographs on Theoretical Computer Science.
- Combinatorial Games Theory Foundations Applied to Digraph Kernels. A. Fraenkel. Electronic Journal of Combinatoric, 4, nº2, 1997.
- Multivision: An Intractable Impartial Game whith Linear Winning Strategy. A. Fraenkel. Am. Math. Monthly. 105, nº 10. Dec 1998, pag 923-928.
- The theory of gambling and statistical logic. Epstein. Accademic Press.
- On numbers and Games. J. H. Conway. A. K. Peters, Ltd. Natick, Massachusetts.
- Graphs. Claude Berge. Ed North-Holland.
- Mathematical Recreations and Essays. Rouse Ball and Coxeter. Dover Publications.
- The Master Book of Mathematical Recreations. Fred Schuh. Dover.
- Counting and Configurations. Problems in Combinatorics, Arithmetic and Geometry. Herman, Kucera, Simsa. Springer.
Enlaces de interés
- Combinatorial Games: Selected Bibliography with a Succinct Gourmet Introduction. Aviezri S. Fraenkel.
- Página de Elwyn Berlekamp. Universidad de Berkeley.
- Página de David Eppstein. Universidad de California.
- Página de David Wolf. Gustavus Adolphus College (GAC).
- Game Theory.net
Aplicaciones
- Tema 1. Lights Out
- Tema 2. Retirar cartas
- Tema 3. Wythoff
- Tema 4. Nim
- Tema 5. Kayles
- Tema 6. Twins
Normas de evaluación para la convocatoria ordinaria de Junio
A) Evaluación por curso
La evaluación será continua a través de trabajos y prácticas realizadas en clase. En el resultado final influirá:
- La asistencia y trabajo en clase.
- Las prácticas realizadas.
B) Evaluación final
Los alumnos se pondrán en contacto con la profesora para que les indique los trabajos a realizar, que se expondrán presencialmente.
Convocatoria extraordinaria de Septiembre
Los alumnos se pondrán en contacto con la profesora para que les indique los trabajos a realizar, que se expondrán presencialmente.