3
$\begingroup$

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).

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

1 Answer 1

Reset to default
1
$\begingroup$

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
$\endgroup$
3
  • $\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, 2020 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, 2020 at 19:39
  • $\begingroup$ @DennisSoemers Ok, thanks for the clarification :) $\endgroup$
    – Tom Dwan
    Apr 29, 2020 at 19:52

You must log in to answer this question.

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