Kombinerande spel leder till flera intressanta, rena problem i algoritmer och komplexitetsteori, varav många förblir öppna. Syftet med detta dokument är att ge en översikt över området för att uppmuntra till ytterligare forskning. I synnerhet börjar vi med allmän bakgrund i Combinatorial Game Theory, som analyserar perfekt spel i perfekt information spel, och Constraint Logic, som ger en ram för att visa hårdhet. Sedan undersöker vi resultaten om komplexiteten i att bestämma idealt spel i dessa spel, och de relaterade problemen med att lösa pussel, både polynom-tid algoritmer och beräkningsmässiga intractability resultat. Vår granskning av bakgrund och kartläggning av algoritmiska resultat är på intet sätt komplett, men bör fungera som en användbar primer.
Demaine och Hearn granskningsresultat om komplexiteten i många klassiska spel i deras enkätpapper REF.
Playing Games with Algorithms: Algorithmic Combinatorial Game Theory
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}