The Chess AI – Model Base or Machine Learning

In my previous post: I wrote a Chinese Chess Program

I talked about a chess AI program I made 12 years ago, some ask me the algorithms that I use to implement this program. IMHO, there are two ways to implement the chess AI: the model based and the machine learning based.

Model Based Chess AI

In chess playing, there are normally two players, each take turns to play. And each player knows exactly everything on the chess (full information disclosed). On turns, one player tries to maximize the score (according to the chess evaluation function) and the other tries to minimize the score.

alpha-beta-pruning

This can be virtually visualized as the min-max tree. However, suppose the average move for Chinese chess is 10, then the branch of the search tree is 10, the complexity will be O(10^N) if the tree depth is N.

We will definitely need to improve the computational efficiency. Luckily, we can do this via the well-known Alpha-beta pruning, which cuts of quite many sub-trees at early stages (when the depth is small) in advance so we don’t need to explore them.

There are other methods which are based on the human chess gaming experience, e.g. some patterns, that may aid cutting the search branches.

A typical model-base Chess program consists of: chess evaluation module that gives how good the current state regarding to one player, the search move generators, and the search tree algorithm.

Machine Learning Chess AI

Machine learning is a hot topic thanks to more and more powerful CPUs and cheaper and cheaper hard disks (storage). With more storage, we can store millions even trillions of games (previous human experiences), with more powerful CPUs, we can employ machine learning (e.g. pattern recognizing, KNN algorithms) to predict the next ‘optimal’ moves so that the winning probability is higher.

You may also like: 浅谈棋类博弃的两种实现方式: 模式化和机器学习

–EOF (The Ultimate Computing & Technology Blog) —