Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

Developing an alpha-beta search for "Colorito", which has the characteristic that sometimes simple hill-climbing is impossible; so a sequence of 2 or 3 moves is the only way to make progress.

I came up with an endgame position where, with a 6 ply search, it's possible to make good progress in 2 moves but the third move must be the "bad" move of a new sequence. It's also possible to make the same 2-move sequence take 3 moves, avoiding the "bad" move on the horizon. This 3-moves which could be 2-moves becomes the principle variation.

The problem is that this same analysis applies to the next move, too; so the AI becomes stuck, making no progress.

The search framework serves a lot of different games, so I'm most interested in generic approaches to detecting/avoiding this problem, but also game-specific ideas that might avoid this particular problem.

Edit: After some thought, a reasonable and somewhat general approach is to allow "pass" moves at the terminal level of the search, even if the game does not. These artificial passes can be valued at zero, or slightly positive, so instead of finding a "bad" move at the search depth limit, the search will find a pass.

share|improve this question
1  
This might be a better fit on gamedev.stackexchange.com –  Robert Harvey Apr 30 at 22:02
    
gamedev seems more oriented to video-game type questions. –  ddyer Apr 30 at 22:16
    
If your reasoning is that the front page has several such video game questions, I would counter with "I've never seen a question of your type on the front page of Programmers." You could get an answer here, but it might take awhile, whereas I'm pretty sure that the gamers already know what you are talking about. –  Robert Harvey Apr 30 at 22:19
    
@ddyer you might want to look at the ai tag on gamedev - it gets a couple questions per week. –  MichaelT May 3 at 0:15

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.