79248584

Date: 2024-12-03 17:16:11
Score: 1
Natty:
Report link

Coming to your questions:

I don't get the sentence "until( every_capture_has_been_examined )": how would this be done for a connect four game?

Of course the example refers to chess, where captures are the moves most likely to alter the evaluation of a position. It's up to you to decide which moves to consider in Connect Four, but threats created by 3-in-a-row come to mind. But see also my reply to your last question.

How would one evaluate silent move in such a game?

There's not such a thing as "move evaluation", unless you want to give moves a score to improve move ordering and make it more likely that alpha-beta cutoffs occur, but that's a different matter. What is evaluated is the position, and is typically done only at the leaf nodes, when both the regular and the quiescent search come to an end. For Connect Four you might think of giving values to the number of 3-in-a-row and 2-in-a-row that are present for both sides, or invent a more sophisticated evaluation. Designing a static evaluation is a trade-off between precision and speed, so you might want to experiment with different solutions and see what gives the best results.

Also, there is no depth parameter, does that mean that quiescent search only applies to a single depth?

Not at all. The algorithm described in Quiescent Search is recursive, therefore will run at any depth until there are no more "hot" moves to examine. Sticking with that example, that is for chess, when there are no more capture moves so that the "until( every_capture_has_been_examined )" loop doesn't get executed. You can add a depth parameter to force a depth limit also for the quiescent search, but if you choose 3-in-a-row as your "hot" moves for the quiescent search you probably won't need it. Long sequences of such threats are rather rare, and when they do occur your engine had better examine them up to the end!

Here is an example output of my connect four AI game, where the horizon effect occurs (if I understand correctly)

Your problem has nothing to do with the horizon effect. In the first place, a quiescent search shouldn't apply to the top node, but only when the maximum depth of the regular search has been reached. I suppose your example was intended to show just the part of the tree subject to the quiescent search. The issue you have here is that the quiescent search can never ignore immediate threats like the 3-in-a-row present in the position. The equivalent in chess is when the king is under check: in such situation the quiescent search must return all legal moves that put the king out of check, and the same apply here, with one important difference: in Connect Four you can always complete your own 4-in-a-row even when the opponent is threatening to do the same. Therefore the order of moves that your quiescent search should consider are:

  1. Immediate wins. If none exists:
  2. Defences from a 3-in-a-row threat by the opponent. If no such threats exist:
  3. Your own 3-in-a-row threats
Reasons:
  • Long answer (-1):
  • No code block (0.5):
  • Contains question mark (0.5):
  • Low reputation (1):
Posted by: Marco Brenco