2
$\begingroup$

Certain games, like checkers, have compulsory moves. In checkers, for instance, if there's a jump available a player must take it over any non-jumping move.

If jumps are compulsory, will there still be a need for a quiescence search?

My thinking is that I can develop an implementation of a quiescence search that first checks whether jumps are available. If there are then it can skip all non-jumping moves. If there's only one jumping move available, then I won't need to run a search at all.

Therefore, I will only use a quiescence search if I initially don't have to make a jump on my first move. I will only active quiescence search in my alpha-beta pruning becomes active. (The alpha-beta will only be active if my first algorithm which first checks if there are jumps available returns a 0, which means there are no jumps available.)

Is my thinking of implementing a quiescence search correct?


My options are slim when it comes to optimizations due to serious memory constraints, hence I won't be using PVS or other algorithm like that as they require additional memory.

$\endgroup$

1 Answer 1

4
$\begingroup$

I understand your question to be:

If some moves are compulsory, and my agent has no choice about which move to make next, do I need to perform a search, or can I just return the compulsory move?

The answer depends on what your goal is.

If your goal is to make an interactive agent that will play the game against you, then you are correct: there's no need to perform a search. Just return the compulsory move, and then run the search next time your agent has a choice about what to do.

If your goal is to determine the optimal way to play a game, or the expected payoff from a certain game position (another common use of search techniques), then you should run the search as normal, since the forced move won't necessarily lead to a particular end state.

Tangentially, if you're interested in ways to speed up search for checkers, check out the Chinook papers. There's a popularized account here, and more technical ones here and here by Schaeffer et al.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .