Games with large branching factor

[michalsustr]

In games with large branching factor (such as stratego): std::vector<Action> LegalActions will simply run out of memory, even on a smaller 6x6 variant (12!^2).

Do you think it would make sense to support them, and if yes, how?
I suggest implementing methods such as unsigned long LegalActionsCount and LegalActionAt(unsigned long index)

[michalsustr]

I've noticed ActionsAndProbs is fortunately prepared for this (it's possible to omit some pairs of Action and probability). If an action is not listed, does it mean that it's probability is assumed to be zero?

[lanctot]

Sorry I don't quite understand. The legal actions vector will only contain legal actions, upper bounded by the branching factor, which is still fine even in Stratego.

Same for ActionsAndProbs.. I guess you mean at chance nodes? Yes, if something is missing then it cannot happen. We support a chance mode called kSampledStochastic for games where this chance braching factor would be too large to enumerate.

[lanctot]

Do you think it would make sense to support them, and if yes, how?
I suggest implementing methods such as unsigned long LegalActionsCount and LegalActionAt(unsigned long index)

I've thought we might need it eventually but so far haven't required it (even for games as large as Stratego). If we did want to support some kind of game where using an explicit list is prohibitive, it'd probably be better to return an iterator (or a lambda) so that the state doesn't need to track any information for generating/indexing moves.

But this would be games much larger than Stratego. I still don't understand why you'd need it for Stratego; seems to me like the branching factor might even be smaller than Chess.

[michalsustr]

Before the start of the game, players arrange their 40 pieces in a 4×10 configuration at either end of the board. The ranks are printed on one side only and placed so that the players cannot identify the opponent's pieces
https://en.wikipedia.org/wiki/Stratego#Setup

So in the setup phase, players can choose something like 40! actions (it's less, because some ranks occur multiple times).

game where using an explicit list is prohibitive, it'd probably be better to return an iterator

I guess you'd rather want to sample those actions then going through them one by one, for which the indexing seems better.

[elkhrt]

You can (and should) factorize the actions - first action is placing the flag, next action is placing a bomb, etc. etc.

[michalsustr]

Ah, yes! :) seems obvious now.

I suppose other games can be done similarly (i.e. large range of bets in poker for example).

[rhalbersma]

You can (and should) factorize the actions - first action is placing the flag, next action is placing a bomb, etc. etc.

This is indeed part of the approach taken in Chapter 4 of http://www.kbs.twi.tudelft.nl/docs/MSc/2007/deBoer/thesis.pdf (author is 3 times world champion Vincent de Boer).

[rhalbersma]

Do you think it would make sense to support them, and if yes, how?
I suggest implementing methods such as unsigned long LegalActionsCount and LegalActionAt(unsigned long index)

I've thought we might need it eventually but so far haven't required it (even for games as large as Stratego). If we did want to support some kind of game where using an explicit list is prohibitive, it'd probably be better to return an iterator (or a lambda) so that the state doesn't need to track any information for generating/indexing moves.

But this would be games much larger than Stratego. I still don't understand why you'd need it for Stratego; seems to me like the branching factor might even be smaller than Chess.

Excluding the simultaneous setup phase (for which there are 10^33 information sets per player), the alternating move phase has a branching factor less than 25 (see Chapter 3 of https://project.dke.maastrichtuniversity.nl/games/files/msc/Arts_thesis.pdf)