TL;DR
This paper argues that while AI has achieved superhuman performance in many board games through brute-force search and knowledge bases, true AI advancement lies in tackling games that challenge human cognitive strengths like learning, planning, and resource allocation. It proposes three new challenges for the AI community: modeling opponents, annotating game contests, and teaching games, aiming to bridge the gap between current AI capabilities and human-like intelligence.
What Problem Does This Paper Address?
For decades, AI research has leveraged games as "toy domains" to test and advance artificial intelligence. While programs like Deep Blue have achieved superhuman performance in complex games like chess, this has largely been through immense computational power and vast, pre-compiled knowledge. However, these programs often lack the nuanced cognitive abilities that human experts exhibit, such as learning from experience, adapting to new situations, planning strategically, and understanding opponent intentions. The paper addresses the question of what "next moves" AI should make in game playing research to move beyond brute force and towards more human-like intelligence. It highlights that games where humans excel due to these cognitive skills, and where AI currently struggles, represent the true frontier for AI advancement.
Methods
The paper discusses two primary components of game playing: search and knowledge.
- Search: This involves exploring the game tree to find optimal moves. Techniques mentioned include minimax algorithms, alpha-beta pruning, and specialized hardware for deep search (like Deep Blue's). The paper notes that for games with very large branch factors, exhaustive search becomes intractable.
- Knowledge: This is incorporated in several ways:
- Opening Books: Pre-recorded sequences of moves for the start of a game.
- Heuristic Evaluation Functions: Functions that assign a score to a game position, guiding the search. These are often "human-constructed" and tuned.
- Closing Books: Pre-computed optimal moves for endgame positions.
- Learned Evaluation Functions: The paper highlights the success of programs like TD-gammon, Logistello, and Maven, which learned their evaluation functions offline using techniques like temporal difference learning and neural networks. This is presented as a significant advancement over hand-crafted functions.
The paper also introduces the concept of satisficing as a cognitive mechanism observed in human experts, where decisions are made that are "good enough" rather than exhaustively optimal, especially under time constraints. The program Hoyle is presented as an example of a system that embodies this approach, learning online and integrating multiple heuristic "Advisors."
Datasets
The paper does not explicitly list or introduce new datasets. Instead, it refers to:
- Millions of offline contests: Used for training learned evaluation functions (e.g., TD-gammon, Logistello).
- Grandmaster-level knowledge: Infused into programs like Deep Blue.
- Statistics on grandmasters' opening play: Used to inform opening books.
- Protocols and eye-movement data from expert human players: Used by cognitive scientists to understand human expertise.
- Game rules: The fundamental input for any game-playing program.
Key Insights and Ideas
- Beyond Brute Force: The paper strongly advocates for moving beyond purely computational brute force (like Deep Blue's) and focusing on games that require human-like cognitive skills.
- The Power of Learned Evaluation Functions: Programs that learn their evaluation functions (e.g., TD-gammon, Logistello, Maven) have shown significant success, suggesting that learning is a crucial component for achieving expert-level play, especially in games with high uncertainty or complexity.
- Human Expertise is Different: Human experts don't rely on massive opening/closing books. Instead, they use pattern recognition, intuitive understanding, and efficient search guided by deep knowledge and cognitive skills.
- Satisficing as a Key Human Strategy: Humans often "satisfice" – making good enough decisions quickly – rather than exhaustively searching. This is a valuable cognitive mechanism that AI could emulate.
- The Importance of "Reading" and Spatial Cognition: Human experts excel at "reading" the board, understanding spatial relationships, and integrating visual cues with strategic reasoning. This is a critical area for AI to explore.
- Three New Challenge Problems: The paper proposes three significant challenges that push AI beyond current capabilities:
- Model a Contestant: Understanding and characterizing an opponent's play style, strengths, and weaknesses.
- Annotate a Contest: Generating human-quality explanations and commentary for game moves and strategies.
- Teach a Game: Developing programs that can effectively teach their skills to others, requiring self-modeling and pedagogical understanding.
Key Results
- Superhuman Performance in Specific Games: Programs like Chinook (checkers) and Deep Blue (chess) have achieved superhuman performance, demonstrating the power of scale in search and knowledge.
- Success of Learned Evaluation Functions: TD-gammon achieved near-expert level in backgammon, Logistello defeated the human Othello champion, and Maven became a top Scrabble® program, all largely due to learned evaluation functions.
- Hoyle's Online Learning: Hoyle demonstrates the ability to learn and play a broad variety of games online, often achieving expertise in under 100 contests, and can explain its moves.
Limitations and Future Work
- Intractability of Large Branch Factors: Games like Go and Shogi have branch factors so large that even advanced search techniques become intractable.
- Inaccessible Knowledge: For some games, the requisite knowledge for heuristic evaluation functions is not well understood or agreed upon even by human experts.
- Lack of Human Cognitive Features in Champion Programs: Current champion programs often lack online learning, planning, and the ability to communicate knowledge effectively.
- Future Work: The paper strongly points towards the three challenge problems (modeling contestants, annotating contests, and teaching games) as the next frontier. It suggests that future AI research should focus on:
- Developing reactive, hierarchical satisficers.
- Improving agent interaction and modeling.
- Enabling programs to narrow options, learn from mistakes, model other agents, explain rationales, and teach.
Summary updated