3

I implemented a negamax with alpha beta and aspiration windows. Now, it also has iterative deepening. When I let the engine run for 15 seconds in the below position, it finds a move at depth 2 with very good value (135/ d8-d7). But when it goes one depth deeper, the movie is bad because it loses the queen (980). Looking at the best move at the deepest depth, when it fully searches, I get f7-f6 with an evaluation of 200 and it is a way better move.

Do I just throw away the best move of a previously searched depth, and only look at the deepest fully searched depth? My brain somehow can't find the solution.

[FEN "rnbqkbnr/5ppp/4p3/2PN2B1/1P2P3/p4N2/P1P1BPPP/1R1QK2R b Kkq - 0 1"]
2

In alpha/beta pruning, the order that moves are searched in matters a great deal. You always want the best move(s) to be searched first--this creates more beta cutoffs. The basic idea is that before searching each level of the tree, we will sort the moves based on how good they are, then search the moves in that order.

Of course, this is quasi-paradoxical ("how to find the best move: step 1, find the best move...") and one of the ways we get around that is using iterative deepening. Search the position at a smaller depth, then put that move at the very top of the list for the next iteration. This is the point of iterative deepening.


Because you are just starting out, (and are searching depth 2 in 15 sec), I'd really recommend

  1. making sure your alpha/beta is bug free (for the love of god, use negamax)
  2. implementing other move ordering techniques before iterative deepening.
  3. implementing null move pruning

These last two are (relatively) easy to do, and give essentially free speedups.

1
  • Thank you for your answer, i understand now. The search to depth2 is fast, 15 seconds was the entire time i let him search where he gets to depth 5.
    – philipp
    Dec 25 '20 at 9:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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