We are building an AI to play a board game. Leaving aside the implementation, we noticed that it plays worse when we set an even (2,4,6,...) level of depth. We use a minimax depth-first strategy. Do you have any ideas why it behaves like that?

Edit: for example if we set a game between an AI with 5 levels of depth and an AI with 6 levels of depth, the first one usually wins (and this is weird).

  • $\begingroup$ Have you tried checking for quiescense and going one layer deeper in that case? $\endgroup$ – Thomas W Apr 29 at 18:47
  • $\begingroup$ Nope, we will check it out, thanks :) $\endgroup$ – Tom Dwan Apr 29 at 19:52

When the number of levels is odd, it means the first player can do one more extra movement on the board. As it is an extensive form game, when decide using backward induction, as the last and the first move are for the first player, so the first player can act better than the situation that the second player will make the last move.

| improve this answer | |
  • $\begingroup$ But if the AI evaluates up to level x + 1 (suppose x is odd), it means that it has evaluated all moves up to x and it is now evaluating the second player's next move. How can this degrade performance? At the most it should play about the same $\endgroup$ – Tom Dwan Apr 29 at 18:56
  • $\begingroup$ @TomDwan Suppose you're playing chess. If you search to depth 1, you only consider your own moves, and don't consider possible responses by the opponent. This will probably often lead to very aggressive play (you can capture pieces and don't search deep enough to see your opponent replying). Increasing to depth 2 would often switch this around completely and lead to much more defensive play, since you no longer consider your own replies to your opponent's reply to your first move. Etc. In some games even may tend to be better, and in some games odd may tend to be better. $\endgroup$ – Dennis Soemers Apr 29 at 19:39
  • $\begingroup$ @DennisSoemers Ok, thanks for the clarification :) $\endgroup$ – Tom Dwan Apr 29 at 19:52

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.