Thursday, February 24, 2005

Intermediate goals

When programming a strategy game, you basically combine two elements: A deep search and an evaluation function. The search will look at lots of positions (millions) that might arise from the current board position, while the evaluation has to tell the program whether this line is any good or not. Most of the time, the evaluation is not that difficult, at least not in checkers. The reason is simple, checkers is a very materialistic game. Most of the time, being a man ahead will win the game. In other games this is different, e.g. in chess the goal is to mate the enemy king, and you can sacrifice a lot of material for a violent attack on the king. In checkers, the situations where you can sacrifice a man are rather rare, allowing even pretty dumb programs to play well. Dumb in this context means that they have a rather weak evaluation function, but paired with a deep search it will do the job most of the time. Such intermediate goals, like winning a man or getting the first king which you can code into your evaluation, are necessary for the program to know what to do; only knowing the ultimate goal of the game alone will not get you anywhere unless the game is so simple that you can calculate right to the end.
Two weeks ago, I wrote a program that plays suicide checkers. In suicide checkers, the ultimate goal is to lose, i.e. not to be able to make a move any more (either by losing all men or by getting smothered). Now, if the final goal there is to lose all your men, instead of winning all your opponent's men, what would a good intermediate goal in suicide checkers be? To win material like in normal checkers, or the other way round? And are there any positional goals that one might want to achieve? Can you guess some answers to these questions?

2 comments:

Nelson Castillo said...

>And are there any positional goals that one might want to achieve?

- To stay far from the 8th row?
- To stay away from the center?
- To move away from the first row fast.

Kestutis said...

Maybe instead of function
TestCapture()as is done in Simple
Checkers better is to create
function TestGiveAway(),which
tests - can current color on move
to make suicidal move and if so
then extend the search.In another
words if we have some kind of
quiescence search then this quies-
cence search must go on while
there is a suicidal move on board.
And to evaluate only positions
where are no suicidal moves.