5 ms·

If you are interested in this, I maintain a list of boardgame-solving related research at https://github.com/captn3m0/boardgame-research https://github.com/capt

If you are interested in this, I maintain a list of boardgame-solving related research at https://github.com/captn3m0/boardgame-research https://github.com/captn3m0/boardgame-research, with sections for specific games. This looks really interesting. It would be a good project to test this against a general card-playing framework to easily test it on a variety of imperfect-information games based on playing cards.

alper111 5y ago
This looks very good, thanks.
fho 5y ago
I tried my hand once or twice at (re-)implementing board games [0], so that I could run some common "AI" algorithms on the game trees. What tripped me up every time is that most board games have a lot of "if this happens, there is this specific rule that applies". Even relatively simple games (like Homeworlds) are pretty hard to nail down perfectly due to all the special cases. Do you, or somebody else, have any recommendations on how to handle this? [0] Dominion, Homeworlds and the battle part of Eclipse iirc.
- nicolodavis 5y ago
  You could consider using a library like boardgame.io for this.
  - fho 5y ago
    I'll look into that.
- captn3m0 5y ago
  +1 to boardgame.io. It provides very good abstractions for turns, phases, players, and partial information. I’ve implemented small games with a few hours of effort, and that includes a UI.
  - penteract 5y ago
    It's a good set of abstractions, but I've found that the system used for immutability (immerjs) carries noticable performance costs (a factor of more than 2), to the point that it was faster to make a mutable copy of almost all the gamestate at the start of the 'apply move' code.
    - mathgladiator 5y ago
      For Adama ( http://www.adama-lang.org/ http://www.adama-lang.org/ ), I am using a mutable tree with two copies and then built transactions such that I can emit deltas on the parts that change. I have all the benefits of immutability without the cost PLUS I have a cheap undo/redo log.
- anonymoushn 5y ago
  Dominion and Homeworlds are pretty complicated! Maybe you can start with a simpler game like Splendor. In my 2-player Splendor rules engine, the following actions are possible: 1. Purchase a holding. (90 possible actions, one for each holding) 2. If you do not have 3 reserved cards, reserve a card and take a gold chip if possible. (93 possible actions, one for each holding and one for each deck of facedown cards) 3. If there are 4 chips of the same color in a pile, take 2 chips of that color. (5 possible actions) 4. Take 3 chips of different colors, or 2 chips of different colors if only 2 are available, or 1 chip if only 1 is available. (25 possible actions) 5. If after any action you have at least 11 chips, return 1 chip. (6 possible actions which are never legal at the same time as any other actions) This still doesn't correctly implement the rules though. In the actual game, you'd be allowed to spend gold chips when you don't need to, which would make purchasing holdings contain extra decisions after you pick which holding to purchase about which chips you'd like to keep.
  - fho 5y ago
    I actually played Splendor for the first (three) time(s) some time ago and honestly didn't really like it. It's a very simple game, true. I feel like there are not many decision points for me as a player and therefore there is not much strategy involved. But maybe that is just my view after very few games. (At the same time that probably makes it a good choice for a game implementation) Thing is that for all my examples above I had a "good" reason to implement that specific game: 1. Dominion (shortly after it came out) To evaluate strategies to best my friends (obviously). 2. Eclipse Has a nice rock-paper-scissors type of ship combat, where you can counter every enemy build (if you have enough time and resources). Calculating the odds of winning would be interesting. 3. Homeworlds Seems to be a very fascinating game. But without any players to compete with [0] ... AI to the rescue ;-) [0] I am aware of SDG where I could play online, but that site is in decay mode. Getting an account involved mailing the maintainer and those times I tried to start a game no players showed up.
    - henshao 5y ago
      I think splendor gets more interesting if your opponents are also trying to be strategic. You can see what color chips they are picking up, which lets you know what they are aiming for, which influences what card you want to aim for or reserve. Mid game, you can see what colors other people are missing and try to corner colors to give you room to breath and pick up cards. You can also see the set of colors people are holding to see which of the 4 final bonus point cards are being fought over. I like the game for what it is. I'd say, surprisingly strategic.
- iwd 5y ago
  If you’re doing it for fun, one option is to start with a simplified version of the game. It’s faster to implement and faster to run. And you’ll get insights you can apply to the full game. That’s what I did when I applied RL to Dominion, because the complexity of the game depends heavily on the cards you include! See part 3 of https://ianwdavis.com/dominion.html https://ianwdavis.com/dominion.html
- LeifCarrotson 5y ago
  > What tripped me up every time is that most board games have a lot of "if this happens, there is this specific rule that applies". Even relatively simple games (like Homeworlds) are pretty hard to nail down perfectly due to all the special cases. The key is to build a data-driven state machine, rather than writing logic with a bunch of 'if' statements.
  - fho 5y ago
    I am "camp Haskell", so my approach was pretty much data-driven. But what is a state machine if not a big nest of if-else statements? :-)
  - mathgladiator 5y ago
    You are correct, but some games can yield exceptionally complicated state machines. I designed a language for solving this: http://www.adama-lang.org/ http://www.adama-lang.org/ I get all the benefits of a data driven state machine with the simplicity of a language that supports asynchronously asking users for updates.
- mathgladiator 5y ago
  I'd appreciate you checking out my language and providing feedback. An element that helps is building a stateful server and using streams where the people behave like servers: http://www.adama-lang.org/ http://www.adama-lang.org/
JoeDaDude 5y ago
Thank you for posting! Maybe you can include the game of Arimaa [1]. Arimaa was designed to be hard(er) for computers and level the playing field for humans. Algorithms were developed eventually, though I have not kept up to know where that stands today. [1]. https://en.wikipedia.org/wiki/Arimaa https://en.wikipedia.org/wiki/Arimaa
- captn3m0 5y ago
  Arima has enough research that it’s covered in the Wikipedia section[0] as well as the Chess Programming Wiki[1], which is linked in the README. I’m specifically trying to collect research on contemporary games, which are not so easily available. Chess/Go and alike games are very covered already, however imperfect information games are much rarer for eg. [0]: https://en.m.wikipedia.org/wiki/Computer_Arimaa https://en.m.wikipedia.org/wiki/Computer_Arimaa [1]: https://www.chessprogramming.org/Arimaa https://www.chessprogramming.org/Arimaa
majani 5y ago
Imperfect information games will always have a luck element that gives casual players an edge. That's basically the appeal of card games over board games.
- mathgladiator 5y ago
  Not just luck but deception as well which takes some games to new levels.
- ketzo 5y ago
  And why so many board games incorporate decks/hands of cards.
mathgladiator 5y ago
Thanks for this! I'm currently designing a language for complex board games like Battlestar Galactica: http://www.adama-lang.org/ http://www.adama-lang.org/ Something that I found amazing was inverting the flow control such that the server asks players questions with a list of possible choices simplifies the agent design tremendously. As I'm looking to retire to work on this project, I can generate the agent code and then hand-craft an AI. However, some AIs are soooo hard to even conceptualize.

alper111 5y ago

This looks very good, thanks.

fho 5y ago

I tried my hand once or twice at (re-)implementing board games [0], so that I could run some common "AI" algorithms on the game trees. What tripped me up every time is that most board games have a lot of "if this happens, there is this specific rule that applies". Even relatively simple games (like Homeworlds) are pretty hard to nail down perfectly due to all the special cases. Do you, or somebody else, have any recommendations on how to handle this? [0] Dominion, Homeworlds and the battle part of Eclipse iirc.

nicolodavis 5y ago
You could consider using a library like boardgame.io for this.
- fho 5y ago
  I'll look into that.
captn3m0 5y ago
+1 to boardgame.io. It provides very good abstractions for turns, phases, players, and partial information. I’ve implemented small games with a few hours of effort, and that includes a UI.
- penteract 5y ago
  It's a good set of abstractions, but I've found that the system used for immutability (immerjs) carries noticable performance costs (a factor of more than 2), to the point that it was faster to make a mutable copy of almost all the gamestate at the start of the 'apply move' code.
  - mathgladiator 5y ago
    For Adama ( http://www.adama-lang.org/ http://www.adama-lang.org/ ), I am using a mutable tree with two copies and then built transactions such that I can emit deltas on the parts that change. I have all the benefits of immutability without the cost PLUS I have a cheap undo/redo log.
anonymoushn 5y ago
Dominion and Homeworlds are pretty complicated! Maybe you can start with a simpler game like Splendor. In my 2-player Splendor rules engine, the following actions are possible: 1. Purchase a holding. (90 possible actions, one for each holding) 2. If you do not have 3 reserved cards, reserve a card and take a gold chip if possible. (93 possible actions, one for each holding and one for each deck of facedown cards) 3. If there are 4 chips of the same color in a pile, take 2 chips of that color. (5 possible actions) 4. Take 3 chips of different colors, or 2 chips of different colors if only 2 are available, or 1 chip if only 1 is available. (25 possible actions) 5. If after any action you have at least 11 chips, return 1 chip. (6 possible actions which are never legal at the same time as any other actions) This still doesn't correctly implement the rules though. In the actual game, you'd be allowed to spend gold chips when you don't need to, which would make purchasing holdings contain extra decisions after you pick which holding to purchase about which chips you'd like to keep.
- fho 5y ago
  I actually played Splendor for the first (three) time(s) some time ago and honestly didn't really like it. It's a very simple game, true. I feel like there are not many decision points for me as a player and therefore there is not much strategy involved. But maybe that is just my view after very few games. (At the same time that probably makes it a good choice for a game implementation) Thing is that for all my examples above I had a "good" reason to implement that specific game: 1. Dominion (shortly after it came out) To evaluate strategies to best my friends (obviously). 2. Eclipse Has a nice rock-paper-scissors type of ship combat, where you can counter every enemy build (if you have enough time and resources). Calculating the odds of winning would be interesting. 3. Homeworlds Seems to be a very fascinating game. But without any players to compete with [0] ... AI to the rescue ;-) [0] I am aware of SDG where I could play online, but that site is in decay mode. Getting an account involved mailing the maintainer and those times I tried to start a game no players showed up.
  - henshao 5y ago
    I think splendor gets more interesting if your opponents are also trying to be strategic. You can see what color chips they are picking up, which lets you know what they are aiming for, which influences what card you want to aim for or reserve. Mid game, you can see what colors other people are missing and try to corner colors to give you room to breath and pick up cards. You can also see the set of colors people are holding to see which of the 4 final bonus point cards are being fought over. I like the game for what it is. I'd say, surprisingly strategic.
iwd 5y ago
If you’re doing it for fun, one option is to start with a simplified version of the game. It’s faster to implement and faster to run. And you’ll get insights you can apply to the full game. That’s what I did when I applied RL to Dominion, because the complexity of the game depends heavily on the cards you include! See part 3 of https://ianwdavis.com/dominion.html https://ianwdavis.com/dominion.html
LeifCarrotson 5y ago
> What tripped me up every time is that most board games have a lot of "if this happens, there is this specific rule that applies". Even relatively simple games (like Homeworlds) are pretty hard to nail down perfectly due to all the special cases. The key is to build a data-driven state machine, rather than writing logic with a bunch of 'if' statements.
- fho 5y ago
  I am "camp Haskell", so my approach was pretty much data-driven. But what is a state machine if not a big nest of if-else statements? :-)
- mathgladiator 5y ago
  You are correct, but some games can yield exceptionally complicated state machines. I designed a language for solving this: http://www.adama-lang.org/ http://www.adama-lang.org/ I get all the benefits of a data driven state machine with the simplicity of a language that supports asynchronously asking users for updates.
mathgladiator 5y ago
I'd appreciate you checking out my language and providing feedback. An element that helps is building a stateful server and using streams where the people behave like servers: http://www.adama-lang.org/ http://www.adama-lang.org/

JoeDaDude 5y ago

Thank you for posting! Maybe you can include the game of Arimaa [1]. Arimaa was designed to be hard(er) for computers and level the playing field for humans. Algorithms were developed eventually, though I have not kept up to know where that stands today. [1]. https://en.wikipedia.org/wiki/Arimaa https://en.wikipedia.org/wiki/Arimaa

captn3m0 5y ago
Arima has enough research that it’s covered in the Wikipedia section[0] as well as the Chess Programming Wiki[1], which is linked in the README. I’m specifically trying to collect research on contemporary games, which are not so easily available. Chess/Go and alike games are very covered already, however imperfect information games are much rarer for eg. [0]: https://en.m.wikipedia.org/wiki/Computer_Arimaa https://en.m.wikipedia.org/wiki/Computer_Arimaa [1]: https://www.chessprogramming.org/Arimaa https://www.chessprogramming.org/Arimaa

majani 5y ago

Imperfect information games will always have a luck element that gives casual players an edge. That's basically the appeal of card games over board games.

mathgladiator 5y ago
Not just luck but deception as well which takes some games to new levels.
ketzo 5y ago
And why so many board games incorporate decks/hands of cards.

mathgladiator 5y ago

Thanks for this! I'm currently designing a language for complex board games like Battlestar Galactica: http://www.adama-lang.org/ http://www.adama-lang.org/ Something that I found amazing was inverting the flow control such that the server asks players questions with a list of possible choices simplifies the agent design tremendously. As I'm looking to retire to work on this project, I can generate the agent code and then hand-craft an AI. However, some AIs are soooo hard to even conceptualize.