The AI

Min-Max:

The AI of the chess engine is actually the min-max algorithm along with some optimizations.I will give certain links for a detailed explanation at the end of this blog but for now i will try to explain it for anyone who does not have even the basic knowledge of graph theory.However recursion is a prerequisite.(Of course, someone with no graph theory knowledge will find it a little difficult, so i suggest that you read the basics , and DFS and BFS. Really, nothing more is required.)

Let's say we have a position where white has certain moves(assuming it is white two play).Now, here I should mention that 1 move is actually divided into two ply ,one of white and one for black. Now what min-max does is that we play every move that is possible for white!And then, for every one of the arising positions,we play every move for black!And this goes on as a cycle.I know, this may sound time consuming and dumb as every chess player knows(myself included,being a tournament player for last 6 years), that we only look for a couple of moves and are heavily dependent on pattern-recognition.Well, as it turns out,not much time is required for evaluating each position and most ordinary chess programs do not have pattern recognition and mine certainly does not.

Each time we evaluate all the possible moves, we look ahead by a further level.For example, if we evaluate all of whites moves , we are looking 1 level ahead.If further we evaluate all of blacks moves, we are looking ahead 2 levels.What this basically means is that we are looking for all combinations of 2 ply s that each player can play.This is what we humans do when we look for combinations.But here,instead of looking for specific moves, we look for all moves.This depth that we look at is controlled by a variable which terminates the recursion after a fixed number of levels and runs a static evaluation method.(This I will discuss in some future blog.)

Now comes the actual algorithm --- how to get the result of a position.This is how :-
After evaluating a position, we return to the previous position the evaluation result.Say the engine is playing white.Now what the min max algorithm says is this that if in the node or position the opponents color has to move, he will choose the best move as the move that has the smallest evaluation rating(obviously after making the move and getting the eval rating) and if it is a position where the engine's color has to move,it will choose the max eval result to be the best move.It is to be kept in mind that the static evaluation function will give a absolute result.For example,if the engine's position is better, result is a +ve value else, a -ve value. Now th magic is since it is recursive in nature, we do not have to worry about how we get the evaluation value after execution the next move and getting the result.In the base case, the static eval is ran and that gives the absolute value.After that when we backtrack to the previous node or position, this value is utilized again and again.Thus ,this forms a position tree where in alternating layers, we alternately find max and min of the child nodes.

Here , we search for a depth of three.At the end, we get 8 positions.(Here , from every position we get only 2 possible moves, but in actuality, average is 25.)At these positions, we could again search and execute possible moves, but at some point we have to stop as otherwise,there might very well be infinite recursion(Chess is complicated, even for a computer).I this example, you can clearly see taking alternating max and min .Thus, the best move from the original position is the second one.Of course, the opponent might not play optimally so you will seldom follow the whole purple path before searching again, but you will usually execute this algorithm at every move.

Hope I have been able to clearly explain to you the min-max algorithm.You can also study it from wikipedia , but it is a bit tough there.This website is the best for chess programming learning , but not many explanations are given.You can refer to this as a good explanation.Also , it is a pretty well established game algorithm.In the next blog,I will talk about a very important minimax part-- pruning techniques.Especially alfa-beta pruning.