state.player_return()

[tonirm2077]

I'm trying to do some implementations using negamax in openspiel. However, I was having some problems with my terminal node heuristics. state.player_return(id_player_max). To return 1 if there is a victory or -1 if there is a defeat. But, apparently there is an exception, which only allows values greater than or equal to 0. Is there any way to solve this problem?

[lanctot]

Hi @tonirm2077,

It is a bit difficult to help without seeing the error. I don't really understand. Can you point us to a stack trace?

Values are not constrained and can be in any range, though the ranges need to be specified by the MinUtility and MaxUtility functions.

I'm not sure which exception you're talking about .. we have many games with values below 0.

[tonirm2077]

According to: https://en.wikipedia.org/wiki/Negamax# when the depth is equal to 0 or the node is a terminal node, the function returns the node's heuristic value multiplied by the player's color. That is, it should return the evaluated value of the final position from the perspective of the maximizing player. So if the state is terminal, return state.player_return(max_player). However, the following exception occurs:
-> line 206, in negaMax
return state.player_return(max_player)
pyspiel.SpielError: /project/open_spiel/../open_spiel/spiel.h:363 player >= 0
player = -1, 0 = 0

If I am making a mistake, please point out my mistake, I will be grateful for that: Thank you :)

[lanctot]

Yes, ok, you are hitting this case:

open_spiel/open_spiel/spiel.h

Line 363 in 520fe93

SPIEL_CHECK_GE(player, 0);

In OpenSpiel valid player ids are >= 0 except for a few special cases. state.player_return(player) returns the return (accumulated reward) to that player so far in this state. Note that many (most?) games in OpenSpiel return 0 until you hit a terminal state.

So, what's happening here is that max_player = -1 and you're asking for the player return of an invalid player. Player ids should not be negative unless in special cases (and player_return is never used for those special cases).

I think you might be confusing terminal state in the game (state.is_terminal()) with the bottom-most nodes of your tree. In the bottom-most nodes of your tree might be terminal states or non-terminal states, depending on where the search starts. I think you would benefit by going through the minimax implementation. Negamax is essentially the same thing but simplified (under the assumption that the game is strictly-alternating). Take a look at this file:.

Hope this helps!

[tonirm2077]

Essentially, my professor suggested the challenge of taking some existing algorithm in the framework to make a change or a variant. I chose negamax because it is an easy option to start:

def negaMax(state, depth, value_function, max_player):

 if depth == 0 and value_function is None:
     raise NotImplementedError(
           "We assume we can walk the full depth of the tree."
           "Try increasing the maximum_depth or provide a value_function.")

 if depth == 0:
     return max_player * value_function(state)

 if state.is_terminal():
    return state.player_return(max_player)

 value = -float("inf")
 for action in state.legal_actions():
     child_state = state.clone()
     child_state.apply_action(action)
     child_value = -negaMax(child_state, depth-1, value_function,-max_player)
     value = max(value, child_value)

 return value

-> I was using the absltest module to test whether a player would win.

[lanctot]

Can you explain why you're negating max_player in this line?

child_value = -negaMax(child_state, depth-1, value_function,-max_player)

Also: can you give an example top-level call to negaMax and which game you're testing it on?

[lanctot]

Are you implementing a game and hence you wrote State::player_return for the game that you're trying?

If so: would it be possible to try your negamax implementation first on existing game (i.e. Tic-Tac-Toe)?