Implement `GetAllHistories`

[finbarrtimbers]

See discussion in #399.

Basically, we would like it if someone copied the implementation of GetAllStates but made two changes:

1. Use State::FullHistory to check for equality, rather than State::ToString
2. Return a std::vector<std::unique_ptr<State>> rather than a std::map<std::string, std::unique_ptr<State>>.

[lanctot]

Just a quick follow-up, this came up because currently the example in count_all_states.cc will not return the right set of information states for perfect information games.

Specifically, here: https://github.com/deepmind/open_spiel/blob/de2c9ef57038829c2709becb0104e3b2d76725cc/open_spiel/examples/count_all_states.cc#L42

This iterates over the states returned by GetAllStates which currently uses the ToString keys as uniqueness for states, whereas the information states are generally a function of the states' histories.

[jhtschultz]

Took a quick crack at this and got it working. I have to be out for the next few hours but I can have a PR ready later tonight.

[lanctot]

Took a quick crack at this and got it working. I have to be out for the next few hours but I can have a PR ready later tonight.

Awesome! Thanks, @jhtschultz !

[gabrfarina]

Should we consider moving the implementation of the tests for #376 to use GetAllHistories instead?

[lanctot]

Should we consider moving the implementation of the tests for #376 to use GetAllHistories instead?

Depends on what you did in those tests, I didn't have a close look. @finbarrtimbers ?

In any case, if so please wait until next week because I've imported it already and it's going in Monday morning.

[gabrfarina]

Ah, I was just counting infosets and sequences for each players. But it seems that "semantically" in order to do that you want to iterate over all histories (i.e., tree nodes), instead of all the states.

I imagine that the code that counts infosets under open_spiel/examples/ will move to GetAllHistories as well, so changing the tests for Battleship would align the implementations.

[lanctot]

Oh yes that makes perfect sense! If John submits the PR before Monday I will import it and include in the update too.

[finbarrtimbers]

I imagine that the code that counts infosets under open_spiel/examples/ will move to GetAllHistories as well

@gabrfarina: That is the plan!

[michalsustr]

What is a history for simultaneous move games? Is it the new state after jointly applying actions, or a new "partial" state that maintains a buffer of supplied actions, until all players submit some? I think for the purposes of generating all game tree nodes, joint actions are preferrable and the implementation in PR

https://github.com/deepmind/open_spiel/pull/402/files#diff-c5953e96f0b0c0985fde0b80eed26db0R26

actually already supports simultaneous move states (inherited from SimMoveState). However, then either State::History or GetAllHistories name is unfortunately slightly misleading.

[gabrfarina]

I think for the purposes of generating all game tree nodes, joint actions are preferrable and the implementation in PR

I think it's the opposite.

I think the standard extensive-form formalism would require that simultaneous moves be broken into individual non-simultaneous moves that are not observed by the opponent until after the round is over.

That is what happens when normal-form games are converted to extensive-form.

The problem with joint actions is that it's not clear what player the tree node that generates the joint action belongs too. That would also break algorithms that deal with the sequence form.

[lanctot]

For simultaneous games, we store the history as each player's action, taken in sequence: https://github.com/deepmind/open_spiel/blob/a228aa1a5f395c95d67c28d4534d6a33b0880535/open_spiel/spiel.cc#L320

This is now in via a228aa1. Thanks @jhtschultz. I added a TODO to count_all_states.cc that infosets are currently not correct for perfect info games.