[EDIT2:] However, I was viewing this thread again and it seems to me that there is one further distinction that is worth making (and shows how many distinctions can be made even in this simplest case). Suppose we run the algorithm for the above mentioned game and the algorithm tells us that the start state is $WL$ (but not $W$). Hence we will know from that we have no definitive way of winning (with 100% chance). So is there something else we can add? I think there is atleast one point that can be added.
Suppose the player hates to lose (and if there is any risk of losing, the player would want the game to go on forever). Now the player would want to know whether the game could be made to go on forever with some strategy. It seems that this can be handled too. However, notice there is one further slightly subtle aspect still. We know that the start state is marked $WL$. However, this doesn't tell us (by itself) that we might have few "chances" of being promoted to a state marked $W$ at some points! But once again we would want to know that in case those "chances" all go against the player (player isn't promoted), whether after that the player would still be able to force the game to go on forever! Because ideally, if the game could be made to go on forever after taking all the chances (of being promoted), that's what the player should be doing.
This probably needs to be worked a bit further to make it more rigorous, but I am reasonably confident that the basic idea in above paragraphs is correct. [END]
(1) First lets come back [EDIT2] My example w.r.t. to board games like "chess" orand "go". We might wish to generalise our notion for two was described rather badly (or moreand hence this re-wording) players. Basically the "Win" state for one player will become "Lose" stateLet's first think of entirely different examples first. A reasonable analogy for generalisation of the other above single player game could perhaps be written as "simultaneous non-determinisitic game of two players". One might think of a computer game like "Frozen Synapse"(and viceversahttps://en.wikipedia.org/wiki/Frozen_Synapse). More generallyThe details are not too important. Another example, the number of markings of states will also increase I thinkcould be suppose a board-like game (I haven't looked at this variation in detail before so I can't comment on specificsnot too different from checkers or chess) being played online by two different players from different locations.
I have not described that generalisation here None of the players can see the other's board, but it shouldn't be difficult to seeboth move there pieces in the same turn and click the finalise button after decision. The game turn proceeds after both players have clicked on finalise. The "non-deterministic" qualification means that it can be made withwe are allowing for some effortpossible "roll of dice" (even for a specific combination of both players' action).
Now let's think a bit about how we can modify the above scheme for a game like chess for example (which is "turn-based" as opposed to "simultaneous" .... and well involves no roll of dice either). We can just colour all the game states as either "white" or "black" (the start state would be coloured "white" indicating that it makes the first move). Let's think about a bit for the set $A_1$ or $A_2$ (actions for player-1 or player-2"white" and "black" respectively) for a game like Go. For an $n \times n$ boardexample, the set of actions (for any player)$A_1$ can be thought of as a set consistingmade to correspond to all possible moves of $n^2$ elementsindividual pieces (as the board is getting filled some of the actions no longer change the game stateand hence .... meaning they become redundant$A_1$ will be finite). A similar case can be madeSimilarly for chessthe set $A_2$.
If a state is coloured white (each piece has finite numbermeaning white's turn) then any action from that state is an element of possible moves $A_1 \times A_2$. Let $a_1 \in A_1$ and similarly let $a_2, \, b_2 \in A_2$. Observe that on a state coloured white both $(a_1,a_2)$ and $(a_1,b_2)$ will lead to the same state. Furthermore, after an action is selected the next state will be one coloured black.
Finally we do need to account for the fact that once a piece (say a "white piece") is thrown out of the board, all the actionselements corresponding to it no longer changein $A_1$ lost their "meaning" (and perhaps can be put equivalent as default to some other action). But I guess that's really an artifact of the game stateway "domain" of "transition function" is defined. Maybe that can be handled in a more natural way?
The summary of that simply is that for two or more players, the "simulaneous" version is general enough that it can "include" the "turn-based" somewhat naturally (though with some artifacts). [END]
