[captn3m0]

If you are interested in this, I maintain a list of boardgame-solving related research at 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.

[fho]

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.

[anonymoushn]

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]

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]

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.

[piyh]

It's like if you turned tuning magic mana bases into a stand alone game.

[captn3m0]

+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]

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]

For Adama ( 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.

[iwd]

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

[LeifCarrotson]

> 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.

[mathgladiator]

You are correct, but some games can yield exceptionally complicated state machines.

I designed a language for solving this: 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.

[fho]

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? :-)

[nicolodavis]

You could consider using a library like boardgame.io for this.

[fho]

I'll look into that.

[mathgladiator]

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/

[JoeDaDude]

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

[captn3m0]

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

[1]: https://www.chessprogramming.org/Arimaa

[mathgladiator]

Thanks for this! I'm currently designing a language for complex board games like Battlestar Galactica: 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.

[majani]

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.

[ketzo]

And why so many board games incorporate decks/hands of cards.

[mathgladiator]

Not just luck but deception as well which takes some games to new levels.

[alper111]

This looks very good, thanks.