`GetAllStates` relies on the the unreliable state string instead of the history

[gabrfarina]

Hit as part of #376 .

+@lanctot +@michalsustr +@finbarrtimbers

The implementation of GetAllStates expects that state->ToString() be unique for states, which is not true. For example, in the Battleship game, ToString() returns an ascii art representation of the player boards. In Go, my understanding is that ToString() renders the Go board (edit see also this discussion). Neither of these mappings are injective: different orders of moves can result in the same boards, and therefore the same ToString().

https://github.com/deepmind/open_spiel/blob/de2c9ef57038829c2709becb0104e3b2d76725cc/open_spiel/algorithms/get_all_states.cc#L47-L53

This results in the method failing to explore the full game tree. Since the method is performing a DFS on a tree, it is impossible to hit the same state twice, so I am not sure what the comment add only if not already present was supposed to catch. I suggest the following:

• If we want to keep the map, we should have histories as key.
• There is no need to keep an expensive map: a vector of (unique) pointers to states would be more efficient and simplify the code even further. I'm not sure how breaking a change that would be though?

[lanctot]

That depends how you define state. :)

The ToString representation is actually unique across states. If the order of moves is important for determining the state, it should also be in the ToString.

I don't see how the quoted code is problematic? The traversal of the game tree still happens further below it.

If you want a similar method based on histories, we can have another one called GetAllHistories but I think in your case of battleship we should just add all the shot info to the ToString (see e.g. GoofspielState::ToString).

The ToString needs to be the complete description of the state. Having a display of the board is good: please keep it! Just add the other information necessary to describe the full state alongside it.

[finbarrtimbers]

I do think that adding a GetAllHistories that uses the optimization you describe would be great, and changing count_all_states to use it would be a good change.

[finbarrtimbers]

However, I think Marc's correct.

[gabrfarina]

The ToString representation is actually unique across states. If the order of moves is important for determining the state, it should also be in the ToString.

OK that was also my worry when writing the generator. However, because of this discussion I ended up throwing away ToPrettyString and replacing ToString with that implementation.

@lanctot Does this mean that I should go back to having two methods? Also, @michalsustr was suggesting that in Go ToString only prints the board?

EDIT So, if that was the case, it would mean that GetAllStates is silently broken in Go for example. I think if anything a low hanging fruit is to check that the insertion into the map was successful, and if not throw instead of silently stopping the traversal? I don't mind adding filing a quick PR that does that. That seems the backwards-compatible way of making sure nobody else gets cut by this.

If you want a similar method based on histories, we can have another one called GetAllHistories but I think in your case of battleship we should just add all the shot info to the ToString (see e.g. GoofspielState::ToString).

@finbarrtimbers I think this is problematic for the code that uses GetAllStates to count then number of infostates etc (for example inside of open_spiel/examples).

[lanctot]

I say just have it all in ToString (easier), but it's a matter of preference ;-)

Why do you think it would cause a problem counting info states? The recursion doesn't stop just because there's a duplicate; it just does not add it to the hash set.

[gabrfarina]

Why do you think it would cause a problem counting info states? The recursion doesn't stop just because there's a duplicate; it just does not add it to the hash set.

You are right, this does not actually stop iterating, my bad. But because of the fact that keys collide, the map contains less states than it should. Entire infosets get skipped. I hit this while writing the test that was checking the number of infosets & sequences of the generated Battleship games. Because of the key collisions we end up significantly underreporting the number of infosets and sequences.

EDIT here is the example that counts infosets. It does not compute the correct values when ToString is not unique.

https://github.com/deepmind/open_spiel/blob/de2c9ef57038829c2709becb0104e3b2d76725cc/open_spiel/examples/count_all_states.cc#L42-L48

[gabrfarina]

Also, I took a quick look at the implementation of Go, and it seems that indeed ToString only prints the board like Michal was saying?

https://github.com/deepmind/open_spiel/blob/de2c9ef57038829c2709becb0104e3b2d76725cc/open_spiel/games/go.cc#L147-L153

[gabrfarina]

I can see three ways forward:

• Reverting the implementation of ToString() for Battleship to what it was before basically, and opening an issue for other games (like Go, it seems) that might not be conforming to the fact that ToString be a bijection between strings and states. In the meantime I can also add a noisy check that the call to map.insert results in a new entry as it should do. If we detect a collision we can abort with a SpielFatalError.
• Changing the implementation of GetAllStates so that it returns a map history -> State* and decide it's fine for some generators to not guarantee uniqueness of ToString, and only guarantee that History is a unique representation, while the string is for pretty printing purposes.
• Have GetAllStates return a vector of pointers instead of a map, bypassing the ToState vs History decision altogether

In the meantime I can change my implementation of ToString to include the order of shots. That should unblock the Battleship PR.

[lanctot]

We can't change GetAllStates at this point, too much code depends on it and it'd be a severely breaking change.

Edit: It will work perfectly with a fixed ToString. I have no problem adding another function that returns the extra information with the different signatures, but I think once you read my message below you'll likely agree that the ToString fix is the way to go.

[lanctot]

Most of the perfect information games have the current board state as the ToString, and it makes sense there because they are uniquely identified by their board representations (the history is irrelevant, due to i.e. the Markov property). Those are used as keys for the value iteration methods, where you definitely don't want to use histories.

It's only important for the ToString to have this additional information in the imperfect information games due to the use cases. Changing to ToString in Battleship to contain both the pretty board and all other information seems like the simplest solution to this and makes it more consistent with the other games.

[gabrfarina]

Most of the perfect information games have the current board state as the ToString, and it makes sense there because they are uniquely identified by their board representations (the history is irrelevant, due to i.e. the Markov property). Those are used as keys for the value iteration methods, where you definitely don't want to use histories.

@lanctot Ah, this is very useful. I think I finally understand. So State is not the same as "node in the game tree" in the OpenSpiel model. I had completely missed that, and my worry was that there were games not conforming to the standard that "ToString() fully capture the state", so that if we went with the "easy solution", we would still have wrong results when using GetAllStates on games like Go.

Instead, it turns out that it was intended for ToString() to not uniquely represent the node tree, but only in some cases. This is a bit surprising though, it basically means that GetAllStates cannot be used to reliably compute the dimensions of the game tree?

[lanctot]

Ah yes perfect, I was just about to reply:

Instead, it turns out that it was intended for ToString() to not uniquely represent the node tree. This is a bit surprising though, it basically means that GetAllStates cannot be used to reliably compute the dimensions of the game tree?

Correct. If you want to compute something that is a function of the game tree, you need to traverse said tree. :)

So, it is indeed this code here: https://github.com/deepmind/open_spiel/blob/de2c9ef57038829c2709becb0104e3b2d76725cc/open_spiel/examples/count_all_states.cc#L42-L48

that is currently broken in perfect information games because the info states are not retrieved for all ways that they could have been reached. So let's leave this issue open, we should basically just collect all this info with a custom DFS.

[lanctot]

And, apologies: I admit that this is not necessarily well-documented, and have noted to fix this. Where do you suggest would be the best place to put this? What would have prevented this?

[gabrfarina]

that is currently broken in perfect information games because the info states are not retrieved for all ways that they could have been reached.

Yes, exactly, that code is broken whenever ToString is not a one to one mapping with a node.

And, apologies: I admit that this is not necessarily well-documented, and have noted to fix this. Where do you suggest would be the best place to put this? What would have prevented this?

No problem, glad we could get to the bottom of this :-)

I think the biggest pain point is this:

• A State object clearly represents a node in the game tree.
• However, a state string (that is, state.ToString()) does not need to match that, but only in some cases. This distinction was not clear to me, and since nobody objected to the discussion about the implementation of ToString in Battleship, I think it is easy to overlook that detail.
• This also means that just saying "state" is ambiguous: the state object is a tree node, the corresponding "state" string might not be. So code that uses "states" might want to be very explicit about what is meant with that. For instance, when the example code counts "terminal states", it should perhaps clarified that that means "terminal state strings". (Note that for that to make sense, it is required that all nodes with the same ToString() be either all terminal or all non-terminal, and that property should also somehow be enforced to avoid returning wrong results.)

Based on the previous discussion with Michal, and given that Go implements ToString as just the current board, I used to believe that ToString actually was just a pretty-printing convenience method that was never actually used as a key. That's also why the title of this issue says "unreliable state string" --- I just thought it was a convenience function for printing.