Types of games - Printable Version

Types of games - Printable Version

+- Ludii Forum (https://ludii.games/forums)
+-- Forum: Suggestions (https://ludii.games/forums/forumdisplay.php?fid=10)
+--- Forum: Ludii Features / Services (https://ludii.games/forums/forumdisplay.php?fid=11)
+--- Thread: Types of games (/showthread.php?tid=20)

Types of games - Quentin Cohen-Solal - 01-29-2020

Hello,

It would be nice to have a method to know if :

a player can play several times in a row : game.requiresReplay()
the legal moves of a state do not depend on the previous states i.e. only depend on the current state (i.e. on current properties of pieces (position, state, ...) and the current player) : isMarkov()
the captured pieces are only removed at the end of each player moves sequence (games with remove(apply:false)) : hasDelayedRemoval()
the game uses hands : requiresHand()
the game needs the counts of positions of the board : requiresBoardCount()
the game uses pass move : requiresPass()

Some examples:

Arimaa.requiresReplay() = True
Surakarta.requiresReplay() = False

Surakarta.isMarkov() = True
Fanorona.isMarkov() = False
Arimaa.isMarkov() = False

International_draughts.hasDelayedRemoval() = True

RE: Types of games - DennisSoemers - 01-29-2020

Quote:a player can play several times in a row : game.requiresReplay()

We should be able to add a method for this in the next version.

Quote:the legal moves of a state do not depend on the previous states i.e. only depend on the current state (i.e. on current properties of pieces (position, state, ...) and the current player) : isMarkov()

Quote:the captured pieces are only removed at the end of each player moves sequence (games with remove(apply:false)) : hasDelayedRemoval()

Quote:the game uses hands : requiresHand()

We should be able to add a method for this in the next version.

Quote:the game needs the counts of positions of the board : requiresBoardCount()

In our current dev version we have "game.requiresCount()". If that already exists in the current pre-release, I think that's what you're looking for. Note that "count" in Ludii is different from "stacking". requiresCount() would return true in Mancala games for instance, where sites can contain counts greater than 1. But it would still return false in "stacking" games, where pieces are stacked on top of each other. Backgammon for example uses stacking, not count. Stacking games may be detected using game.isStacking().

Quote:the game uses pass move : requiresPass()

I... think we can implement this, but would probably only make it return true for games where "Pass" is explicitly mentioned in a game's .lud description, i.e. games where players can really actively choose to press the Pass button even when they may have other legal moves available. Internally, Ludii also sometimes automatically applies Pass moves for human players, and expects AIs to generate their own Pass moves in cases where no legal moves are available. For instance, drawn games of Tic-Tac-Toe in Ludii do not end after 9 moves, but after 11 moves where 2 Pass moves are appended at the end. These cases would probably return false.

RE: Types of games - Quentin Cohen-Solal - 01-29-2020

[quote pid='79' dateline='1580330052']

Quote:the legal moves of a state do not depend on the previous states i.e. only depend on the current state (i.e. on current properties of pieces (position, state, ...) and the current player) : isMarkov()

I'm not as sure about this one. Will have to discuss this with the other members of the Ludii team... What do we count as "the current state"? Only properties that a human could visually see, by looking at the board? Or all properties that are visible to AIs in the Trial and/or State objects that we supply to them? Because if we consider what's technically visible to the AIs, I'm pretty sure that all of our games would be Markov... We'll see what we can come up with.
[/quote]

If to determine the next state, the game needs to access the game history, then the game is not Markov. Anyway, a "isVisualMarkov" method would already be interesting.

[quote pid='79' dateline='1580330052']

Quote:the captured pieces are only removed at the end of each player moves sequence (games with remove(apply:false)) : hasDelayedRemoval()

I think we already have this. You can try "game.hasSequenceCapture()". I think that's what your looking for, at least in our current dev version. I'm not 100% sure whether this also already exists in the current public pre-release, but probably it does.
[/quote]

game.hasSequenceCapture() seems to be what I'm looking for. However, is there also a method to know if we can jump over a piece that has already been taken, that is to say to discriminate games such as International Draughts with games such as Coyote ?

Quote:
Quote:the game needs the counts of positions of the board : requiresBoardCount()

In our current dev version we have "game.requiresCount()". If that already exists in the current pre-release, I think that's what you're looking for. Note that "count" in Ludii is different from "stacking". requiresCount() would return true in Mancala games for instance, where sites can contain counts greater than 1. But it would still return false in "stacking" games, where pieces are stacked on top of each other. Backgammon for example uses stacking, not count. Stacking games may be detected using game.isStacking().

It's not what I'm looking for. A game with hands usually requires count. Thus, with a game which requires count and has hands, I cannot know if the board requires count. Maybe there should be a requieresCount for each container?

RE: Types of games - DennisSoemers - 01-30-2020

Quote:If to determine the next state, the game needs to access the game history, then the game is not Markov. Anyway, a "isVisualMarkov" method would already be interesting.

Sure, but technically we include quite some parts of the game history as part of the game state representation. So that makes the term a bit ambiguous.

Quote:game.hasSequenceCapture() seems to be what I'm looking for. However, is there also a method to know if we can jump over a piece that has already been taken, that is to say to discriminate games such as International Draughts with games such as Coyote ?

Ah, no. In principle that's exactly what game.hasSequenceCapture() already tells you. If that method returns true, it means that captured pieces are only marked as captured, but not yet removed, until a turn has been fully completed. So if the rest of the game's rules allow it, this would mean you could hop back over that piece.

The thing with International Draughts is that, in the move rules in its .lud file, we also have the following snippet:

Code:
(not (in (step) (captureSequence)))

This is an additional rule that explicitly says that we can't step into a position that was previously visited during the current sequence of capture-moves. Having a method to detect the presence of this rule would be considered too specific for our General Game System.

Also not that this rule is not necessarily a game-wide rule. The same holds for the hasSequenceCapture() that we already do have by the way. It just means that at least some of our move rules somewhere in the game use this mechanism where pieces don't disappear right away. But technically it could be possible that there are also different move rules in the game somewhere for which this does not apply. For instance, we could imagine a variant of International Draughts where the regular Man pieces do use this mechanism, but the Dame pieces do not. Or the other way around.

Quote:It's not what I'm looking for. A game with hands usually requires count. Thus, with a game which requires count and has hands, I cannot know if the board requires count. Maybe there should be a requieresCount for each container?

Ah, I see what you mean. Currently this actually is a game-wide property in Ludii. As soon as one of the containers (like a hand) needs support for counts at sites, ALL of the containers in that game will support counts at sites.

We would very much like to look into making this a per-container property, because indeed we -- as humans -- know that for many games only the hands really need counts, and the larger boards don't. If we find a way to detect -- given a game's .lud description -- that some containers will never need support for counts, we can take this into account for our state representation and get improvements in speed and memory-efficiency for these games. We're not sure yet if or how we can automatically determine this from any given .lud description though. Essentially we need to be able to prove that a set of rules will never allow for moves to be generated that increase the count beyond 1 for any site of a given container. This is often easy to see for humans when reading the rules, but a bit more difficult to really rigorously prove in an automated way.

So... if we find a way to do that, absolutely we will, but we're not yet sure that that will happen (any time soon).