From Tic-tac-toe to AlphaGo: a survey of algorithms used in various games

<p>We examine various techniques for finding strategies in various games such as rock paper scissors, tic-tac-toe and go by turning a game’s qualitative aspects into quantitative aspects to talk about them mathematically. Game theory and the concept of a Nash equilibrium and subgame perfect equilibrium are introduced, as well as methods for computing each. We then discuss associative decision making, which encompasses concepts such as Markov decision processes, the Bellman equations, rollouts and the Monte Carlo tree search. Finally, we introduct neural networks and provide the theory on how they can assist decision making both in general and in games. A simulation of the techniques neural networks used is provided. Particular attention is given to the program AlphaGo, which was used to defeat former go world champion Lee Sedol four games to one in 2016.</p>

Name thesis:degree_name

Master of Science (MS) in Computer Science

Level thesis:degree_level

Thesis: EWU Only

Discipline thesis:degree_discipline

Computer Science and Electrical Engineering

Year

2023

Author dc:creator

• Godon, Mathew T.

• Artificial Intelligence and Robotics
• Theory and Algorithms

Statement dc:rights

• Access perpetually restricted to EWU users with an active EWU NetID

Repository record dc:identifier

https://dc.ewu.edu/theses/843

OAI identifier oai:identifier

oai:dc.ewu.edu:theses-1847