search

google-deepmind / open_spiel

OpenSpiel is a collection of environments and algorithms for research in general reinforcement learning and search/planning in games.
Apache License 2.0
4.14k stars 910 forks source link

How to implement games with interruptions #979

Closed rezunli96 closed 1 year ago

rezunli96 commented 1 year ago

Hi. In some card games (e.g., UNO, Mahjong), when a player plays a certain hand, then it is possible for another player to interrupt, do some action, and become the next player. Usually if multiple players interrupt it is the first one who shouted becomes the next player.

But I think it is hard to implement in OpenSpiel as it has a real-time flavor. I can see one feasible solution is to determine some pre-fixed round robin order and ask each player whether it wants to interrupt.

Another possible solution might be to implement it as a simultaneous node. And for those who choose to interrupt just randomly decide who is the next player.

But these may not be perfectly satisfactory as they may change the vanllia game mechanic.

I wonder was there a similar situation for the existing implemented games? And what were their solutions?

lanctot commented 1 year ago

Magic: The Gathering would be another example (but I didn't think UNO would be?)

The only way I see this being feasible is as you say: some kind of regular prompt to ask if the others want to interrupt. I like the idea of a simultaneous node to avoid the round-robin querying of the players.

I agree it's not the best solution and ideally there would be some for of support for real-time games.

There are no games in OpenSpiel of this form, currently. Is this coming up in Mahjong? Can you give an example of a situation where it occurs that you're currently trying to figure out? Because if it's in Mahjong, that game has been used for AI before and then OpenSpiel could adopt what is commonly done in the Mahjong engines to address this.

rezunli96 commented 1 year ago

Oh for UNO I just checked wikipedia, turns out yes the official rule doesn't have interruption, while there is a jump-in rule in some house-rule.

Wow that makes implementing UNO much easier than I thought! I think I am also interested in implementing UNO now, if there isn't a copy-right related issue?

In riichi Mahjong for example (I think it also applies to most of the Mahjong versions), if a player discards a tile, then the other players can call and claim this tile to form a "group" (part of the winning hand it wants to have). For certain group category like Pon, I think it is the first one shouted claim the tile.

Not sure how the current engine did. My guess is they also have a real-time flavor. The AI decides whether to call or not if such an option is presented at the current step. But it might happen that an AI called at its end, but got preempted by another player. Some implementation I read seems to use a two-phase commitment-like protocol (the players first purpose their calling action, and then one of them will get executed eventually). An example is in Section 2.1 of this paper

lanctot commented 1 year ago

UNO is a commercial game still sold widely in stores, so it'd be best to ask for permissions.

However it is quite similar to Crazy Eights, so I'd suggest implementing that one instead.

rezunli96 commented 1 year ago

Ok, I will take a look at Crazy Eights. Thanks!

lanctot commented 1 year ago

Closing due to inactivity. Please re-open if you want to continue the discussion.