Tell me more ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.
up vote 3 down vote favorite

I am thinking of making a chess game, and I read up on minimax trees. How many moves should the AI think ahead so that the player doesn't have to wait a long time?

If there are 25 possible moves (probably an underestimation):

2 moves = 625 boards 3 moves = 15625 boards (huge jump)

I'll be making the game in flash / actionscript 3 (not really a fast language), and I want to keep the turn times acceptable.

Thanks

share|improve this question
Perhaps from the original 625 boards, just choose some of the best scoring outcomes, then perform an extra calculation on just those boards, that way minimizing calculations. Allows for simple difficulty scaling too. – Daniel Oct 23 '11 at 8:46
Hmm, I thought about reducing the 625 boards before, but this makes the AI weak against a move that doesn't immediately kill a piece, but rather sets it up for later. IF I reduce the 25, the AI will not use this tactic. If I reduce 625, the AI will not defend against the tactic. Regarding difficulty: It's not a normal chess game but the number/amount of pieces is different for each side (Chess with RPG elements! :) – gladoscc Oct 23 '11 at 9:25
I guess the hardest part of a chess engine is the simple position evaluation, you need a scoring criterion in order to be able to make the min-max part work, and simply counting pieces does not at all cut it. – eBusiness Oct 23 '11 at 14:09
This is why the best chess engines are supercomputers. You need to calculate every single possible move, otherwise it is beatable (d'oh...). If you do use the 625 into optimal moves solution, you leave the game able to be beaten. Also very few players are able to think ahead more than 3-4 moves if they had to do so for every possible current move on the board... – Tor Valamo Oct 23 '11 at 17:55

1 Answer

up vote 5 down vote accepted

The real answer is: enough to give your player a smart opponent, and as many as you can get away with whilst giving your player a high quality experience.

But that's probably not going to help yet since you can't really calculate moves in any decent amount of time.

What it's going to take to make a smart AI

You can't afford to evaluate every possible result of every possible move. Only seeing two moves ahead makes for a slightly unintelligent AI in a game where it's often said the player who can see the farthest ahead will win. Former world chess champion Garry Kasparov is quoted here:

Asked how many moves ahead he can think, Kasparov replied that it depended on the positions of the pieces. "Normally, I would calculate three to five moves," he said. "You don't need more.... But I can go much deeper if it is required." For example, in a position involving forced moves, it's possible to look ahead as many as 12 or 14 moves, he noted.

So 3 ahead is the minimum, and it's clear you can barely calculate farther than that before you reach insane wait times between turns, thanks to the exponential nature of the calculations.

You need to optimise.

Alpha-beta pruning works to reduce the amount of possible paths you evaluate in a min-max tree. It cuts out paths that lose in the long term and identifies paths where wins are possible so you don't waste time on fruitless searches.

Even with AB pruning your AI will never be able to evaluate all possible games in a timely manner for any significant number of moves. You need to set it a time limit - say 5-10 seconds, maybe more in situations where the computer is really having trouble finding a good move. Once the time limit is up (if not sooner) your computer must stop and make the most appropriate choice based on what it worked out.

Note that the most appropriate choice isn't necessarily the best one (for its winning), since sometimes you might want your AI to stuff up a bit. Note also that in its limited available time, your computer may not actually find an optimum move, or even necessarily a very good one.

share|improve this answer
Thanks! One question: I fear that if I use alpha-beta pruning the AI will not think for the future since it will value moves that gives score now, rather than later. (Like missing out on a combo because for the first move it will not yield any points) Is this true? – gladoscc Oct 23 '11 at 11:49
@gladoscc Well... no, not even a little. The entire point of Alpha-Beta pruning is to optimise your search so you can afford to calculate many moves ahead and move right now based on what will benefit the AI much later. It exists so your AI can make moves that are beneficial in the long-term. You clearly have misunderstood what AB pruning does. – Jonathan Hobbs Oct 23 '11 at 11:56
@gladoscc That is a very common problem, it does however occur without pruning as well. In your position evaluation it is important that you identify volatile positions and either give those further calculations or simply assume that they are disadvantageous. – eBusiness Oct 23 '11 at 13:05

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.