Book contents
- Frontmatter
- Contents
- Preface
- Acknowledgements
- 1 Introduction
- 2 Search Spaces
- 3 Blind Search
- 4 Heuristic Search
- 5 Stochastic Local Search
- 6 Algorithm A* and Variations
- 7 Problem Decomposition
- 8 Chess and Other Games
- 9 Automated Planning
- 10 Deduction as Search
- 11 Search in Machine Learning
- 12 Constraint Satisfaction
- Appendix: Algorithm and Pseudocode Conventions
- References
- Index
8 - Chess and Other Games
Published online by Cambridge University Press: 30 April 2024
- Frontmatter
- Contents
- Preface
- Acknowledgements
- 1 Introduction
- 2 Search Spaces
- 3 Blind Search
- 4 Heuristic Search
- 5 Stochastic Local Search
- 6 Algorithm A* and Variations
- 7 Problem Decomposition
- 8 Chess and Other Games
- 9 Automated Planning
- 10 Deduction as Search
- 11 Search in Machine Learning
- 12 Constraint Satisfaction
- Appendix: Algorithm and Pseudocode Conventions
- References
- Index
Summary
Acting rationally in a multi-agent scenario has long been studied under the umbrella of games. Game theory is a study of decision making in the face of other players, usually adversaries of the given player or agent. Economists study games to understand the behaviour of governments and corporates when everyone has the goal of maximizing their own payoffs. A stark example is the choice of NATO countries refusing to act directly against the Russian invasion of Ukraine given the threat of nuclear escalation.
In this chapter we turn our attention to the simplified situation in which the agent has one adversary. Board games like chess exemplify this scenario and have received considerable attention in the world of computing. In such games each player makes a move on her turn, and the information is complete since both players can see the board, and where the outcome is a win for one and a loss for the other. We look at the most popular algorithms for playing board games.
Chess has long fascinated humankind as a game of strategy and skill. It was probably invented in India in the sixth century in the Gupta empire when it was known as chaturanga. A comprehensive account of its history was penned in 1913 by H.J.R. Murray (2015). The name refers to the four divisions an army may have. The infantry includes the pawns, the knights make up the cavalry, the rooks correspond to the chariotry, and the bishops the elephantry (though the Hindi word for the piece calls it a camel). In Persia the name was shortened to chatrang. This in turn transformed to shatranj as exemplified in the 1924 story by Munshi Premchand (2020) and the film of the same name by Satyajit Ray, Shatranj Ke Khiladi (The Chess Players). It became customary to warn the king by uttering shāh (the Persian word for king) which became check, and the word mate came from māt which means defeated. Checkmate is derived from shāh māt which says that the king has been vanquished.
Table 8.1 lists the names of the chess pieces in Sanskrit, Persian, Arabic, and English (Murray, 2015). In Hindi users often say oont (camel) for bishop and haathi (elephant) for rook.
From India the game spread to Persia, and then to Russia, Europe, and East Asia around the ninth century.
- Type
- Chapter
- Information
- Search Methods in Artificial Intelligence , pp. 221 - 262Publisher: Cambridge University PressPrint publication year: 2024