AI in computer games 2

Nov 2, 11:41 PM |

Let’s see the principles of artificial intelligence in its “purest” form – in board games like chess.

The fascinating fact about chess (and checkers, too): there is the winning strategy and it can be potentially computed. But no human nor machine have yet reached that level. The number of all possible chess positions is finite. If you can see them all in one moment, you are unbeatable.

In reality, even good players usually confine themselves to foresee 2-4 only plies in advance. Best computers in the world can compute some 7-8 plies in advance. (The word ply means a move taken by one of the players, unlike turn, which means the move of the white player plus the move of the black player.)
Don’t think it’s too few. Let’s say there are 35 possible moves in average. It means 1225 for two plies, 42875 for three plies, and 1,5million on the 4th ply level, growing exponencially.
Experienced players would agree that two or even one ply is enough to make a good move if you are well oriented in the board situation. Of course it depends what means “oriented in the situation”, if it doesn’t infer foreseeing more plies in the subconscious.
Well, the Minimax algorithm defines it quite clearly.

Minimax agorithm

When the computer comes into the level which is determined as the topmost one, it analyses and evaluates the considered position, giving it a real-number value from -1 to 1 (where -1 means ‘black wins’, 0 is balanced value, and 1 means ‘white wins’). This topmost evaluation function is in fact the real alchemy of the particular artificial algorithm. It’s based on the material owned by both sides as like as on many position factors, including which squares are under control of each side, how well the king is defended, and how well the pawns are chained together.

So, you (meaning the artificial intelligence) have now evaluated all the positions possible in the topmost ply. Let’s say it’s the N-th ply. Knowing this, you are entitled to evaluate all the positions in the (n-1)-th ply. How?
If you are at least a little experienced in thinking ahead in games like chess, you know you have to take into consideration the BEST move possible for yourself, as like as the BEST move possible for your opponent. Otherwise you would be unpleasantly surprised when your opponent choses better move than you have expected. So, when it’s the white’s turn in the ply (n-1), the position will be evauated by choosing the MAXIMAL number of all the following positions values. And when it’s the black’s turn, the position will be evauated by choosing the MINIMAL number of all the following positions values.

See the picture. Here the AI is white (see ply level 0). There are three possible moves going up one level (Ply level 1). In each of these three positions a few other moves are possible, which, in their turn, go into ply level 2. Let’s make this the maximum ply level for the sake of simplicity. Now we apply our topmost evaluation function on each of them. Once the topmost level positions are evaluated, we can now evaluate the positions one level lower, using the MIN rule. Then, using the MAX rule, we can even evaluate the ply level 0 which is the actual game position. We now know which move is the best one – the rightmost one.

This way, given any maximum ply level, you will gradually evaluate all possible moves in the lower plies, down to 1. Finally, you know what move to choose: the best evaluated one for the actual position!

Beyond minimax

This algorithm can be optimalized by using so-called “alpha-beta cutoff” and other ways which I will not describe in this article. What you need to know when planning to make an AI based on minimax-like algorithm, is: This is by far not all the wisdom sufficient to make really good AI. But it will suffice for most players if you happen to make a reasonable top-level evaluation function.

As for the MINIMAX in Flash: I can tell you, not more than 2 plies are applicable for chess. And even this takes several seconds to consider a move for the AI. It’s too long for these hasty times. So, 1 ply is my best advice. Which means, you in fact don’t need minimax recursion in Flash, unless you want to use a clever filter under the possible moves, taking into consideration only “important” ones like those where a piece is removed from the board.

 

Comment

 

 

Web design (c) ThunderBird Animations, 7/2011. Powered by Textpattern.