3
$\begingroup$

I implemented the minimax algorithm with alpha-beta pruning to see how it works, with application to the connect four game.

My AI works fine, considering the AI is the MAX player (VS human player, which is the MIN), e.g. the Minimax root node of the tree.

However, since the root node is always the MAX player (AI), does this means that the leaf nodes, where pruning occurs, should be at an odd depth?

Whenever I use an odd number for depth, my algorithm works fine. But when I use an even number, the bottom node because a min node and AI looses the game.

Can anyone confirm that when using MAX as the root node, the depth should always be an odd number? AFAIK, it's never said explicitly in the algorithm's description.

Thanks

Improve this question
$\endgroup$
3
  • $\begingroup$ Do you use a transposition table and iterative deepening ? If yes, results of even depth-searches can trouble results of odd depth-searches, but shouldn't give bad moves as well. If no, there is no reason for an even search-depth to give a bad move (i used to have depths of even number). $\endgroup$
    – Vintarel
    Feb 16, 2022 at 19:03
  • $\begingroup$ @Vintarel no I don't use move ordering techniques. But when the depth is even the algorithm ends up computing a score for the min. Is this expected? $\endgroup$
    – Carmellose
    Feb 17, 2022 at 21:48
  • 1
    $\begingroup$ For even depths, the score should be a little lower (not too much though) than for odd depths, as the tree on leaves is supplied with moves favoring the MIN player. On my chess program, the scores could change of around 0.2 point when switching parity of depths, but a good move (score of 3 or more) still remained a good move. Try to see for shallow searches (depth = 1, 2) or by printing the results at every upper nodes if you can spot what happens. $\endgroup$
    – Vintarel
    Feb 19, 2022 at 17:23

1 Answer 1

Reset to default
3
$\begingroup$

Following Vintarel's advice, I reviewed my code and saw there was an error. Indeed, the evaluation function returned different values, depending on the AI or the player. So, for example, it would return -3 for the AI and 3 for the player, resulting in a wrong max/min optimization.

I modified the evaluation function, so that it returns the same value, independently of the player. After, the score is minimized or maximized, according to the current player (AI or human). In the end, odd/even depth has no impact and the algorithm works as expected! Thanks

Improve this answer
$\endgroup$

You must log in to answer this question.

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