Can negamax use an asymmetric evaluation function?

Question

TLDR: I have an asymmetric evaluation function for an implementation of negamax - is that acceptable? Or do I need to make it symmetric?

Longer: I'm writing a game AI (for the chess-like board game "Hive") that was using minimax with alpha-beta pruning and an asymmetric evaluation function.

But I was having trouble adding transposition tables correctly, and was losing confidence in my minimax implementation, so I decided to switch to negamax using the pseudo-code here: https://en.wikipedia.org/wiki/Negamax#Negamax_with_alpha_beta_pruning_and_transposition_tables

I've got everything "working" and AFAIK accurately following the pseudo-code, but my AI is now making some wildly different moves than before and games that usually ended after 10-15 turns now take 30+, and I'm not convinced the AI is actually playing better than it was before. I'm worried that having an asymmetric evaluation function means I'm scoring nodes differently than before (because of the negamax flip-flopping).

I don't want to change to a symmetric function unless I really have to - I've been trying to produce an optimal function experimentally (AI vs AI battles) and have put in hundreds if not thousands of compute hours into producing a strong evaluation function.

Answer 1

Negamax support asymmetric evaluation functions but it does not lead to optimal play (assuming you have no knowlege about your opponent).

I don't know enough about Hive, but in computer chess it is, in general, a bug to have an asymmetric evaluation function. The reasons behind it should be the same for chess and Hive.

For instance, take the starting position (in chess). White is next to move and let us assume your evaluation function gives the position a score of +0.08.

Now change the position, so black is first to move. Everything is the same, only that the roles of white and black has been changed. Under the assumption, that +0.08 was the optimal score for the white position, why should the position for black not also be evaluated as +0.08?

The same argument goes for any position. If you reverse everything, there is no good reason for playing the position differently.

There is only one exception to this rule. If one opponent is clearly stronger than the other, there are arguments for an asymmetric evaluation. For instance, take a completely drawn position like this:

FEN: 4k3/8/8/p1p1p1p1/PpPpPpPp/1P1P1P1P/8/4K3 b - - 0 1

This position could safely be evaluated as 0. Now imaging the starting position but white starts without one knight. This should be a strong advantage for black.

Let us assume you are Magnus Carlsen and you are playing against on opponent who does not even know the chess rules. Which position would you prefer? Here, I would argue that an asymmetric evaluation could make sense (e.g., evaluate a likely draw similar to a loss). Carlsen should avoid the drawn position, while the beginner should prefer it.

The chances that the beginner can hold its own against the world champion, even at one knight odds, are practically zero. On the other hand, in the drawn position, the skill advantage does not matter, as no order of moves can result in a win or loss.

In computer chess, Rebel had a function to prefer tactical positions when playing against humans (see ANTI GRANDMASTER PLAY). There is also the common concept of "contempt", which is the score that engines give for a remis.

But note that in both my examples, this is not optimal play. Magnus Carlsen would not choose the position without the knight when playing a strong (or unknown) opponent. Also Rebel would not use the anti-human strategy against other machines, which also excel in tactical battles. (Even though, depending on the position, Rebel 10 did use ANTI GRANDMASTER PLAY against computers.)