Let us design A Chess Engine (ACE)
Chess is a strategy game played between two players, and in this article, we are going to try to design A Chess Engine (ACE).
Note: If you are unfamiliar with Chess and want to know more about the game, please try this website.
ACE will be a computer program that could potentially unseat Magnus Carlsen.
Playing Chess is the Task and Percentage of Winning Games will be our choice of performance metric. Now how do we teach ACE to play Chess?
We could either Program it explicitly OR Let it learn by itself (ML)
Let us review both approaches in detail.
Explicit Programming:
Programming rules for chess engine is a close to impossible task. The number of total moves in Chess is estimated to be somewhere in the range of 10⁰¹²⁰ (Wiki).
Learn By Itself:
We can make ACE learn by itself using the three different methods as mentioned below:
A. Teach ACE some basic rules of Chess and hire a tutor to play with it
B. Provide ACE with recorded moves from thousands of actual games played by FIDE ranked Chess players
C. Teach ACE some basic rules of Chess and let it play against another version of itself
Let us review the pros and cons of each choice of learning in detail.
A. Hiring a Tutor:
With a complexity of more than googol moves, ACE will never beat Magnus, or even an entry ranked player just by learning to play with a tutor. Of course, ACE will determine how a qualified human plays Chess and ACE’s learning stops with just that. Hiring a tutor would never work for ACE.
B. Learn from recorded Human Games:
As Chess game moves are recorded and analysed by many fans around the world, we could try this approach. There exist three scenarios with this dataset that require three different types of Machine Learning approaches:
B.1. Supervised Learning:
Since all the moves are labelled, the job of ACE is to select the best move from the set of possible legal moves. Classification algorithms like Random Forests and Boosted Decision Trees are our potential candidates.
B.2. Semi-Supervised Learning:
Use Supervised Learning to learn the labels of the moves and then predict the ranking of un-labelled moves. Finally, we predict the next move based on Supervised Learning. The method we applied here is call Self-Learning method of semi-supervised learning.
B.3. Unsupervised Learning:
Identify similar moves and rank the moves from best to worst. The particular problem of assigning labels to individual moves is difficult because even when a player is winning, there is a high chance that there we some bad set of moves played. Clustering algorithms like k-means clustering and SVM help us achieve the same.
Recorded human games give ACE the possibility to mimic human players, but it does not allow ACE to create moves of its own. In any strategy game, it is always better to invent new moves or modify standard move sets to surprise your opponents.
C. Learn by playing against itself:
In this method, ACE is free to select any number of moves and play against any version of itself. This method is called Reinforcement Learning. Though computationally intensive, this method offers flexibility that none of the other two ways offers. The program itself generates the data. For constrained environments like Games with a proper set of rules, Reinforcement Learning beats all the other different types of Machine Learning algorithms by a long shot. Alpha Go Zero was trained entirely by Reinforcement Learning. It won against the highest-ranked player Alpha Go which is another Model trained with a mix of games against humans and itself.
TL;DR
Any strategic game involves a lot of complicated moves, and if we are to design computer programs that play, we need to let them learn on their own. With more than 10¹²⁰ steps, Chess is a right candidate for an ML algorithm to compete against humans. Training the algorithm on datasets employing any of Supervised or Unsupervised or even Semi-supervised learning would be a naive approach that would never achieve the result of defeating human players. The best possible method for the ML algorithm to learn would be by playing against itself, also known as Reinforcement Learning.
