How can I improve the performance of my approach to solving a 1-player version of the card game "The Game" by Steffen Benndorf?

Question

I would like to create an AI for the 1 player version of the card game called "The Game" by Steffen Benndorf (rules here: https://nsv.de/wp-content/uploads/2018/05/the-game-english.pdf).

The game works with four rows of cards. Two rows are in ascending order (numbers 1–99), and two rows are in descending order (numbers 100–2). The goal is to lay as many cards as possible, all 98 if possible, in four rows of cards. The player can have a maximum of 8 cards in his hand and has to play at least 2 cards before drawing again. He can only play a greater value on an ascending row and a smaller value on a descending row with one single exception that lets him play in the reverse order: whenever the value of the number card is exactly 10 higher or lower.

I already implemented a very simple hard-coded AI that just picks the card with the smallest difference and prioritizes a +10/-10 play when possible. With some optimizations, I can get the AI to score 20 points (the number of cards left) on average which is decent (less than 10 points in an excellent score) but I'm stuck there and I would like to go further.

As there is randomness because of the draw pile, I was wondering if it was possible to implement a robust and not hard-coded AI to play this game.

Currently, my AI is playing piecemeal with a very simple heuristic. I do not see how to improve this heuristic, so I am wondering if it is possible to improve the performance by having a view over several turns for example. But I don't see how to simulate the next rounds since they will depend on the cards drawn.

Answer 1

There are a few different ways to improve on your simple heuristic approach, but they mostly resolve to these three things:

• Find a better heuristic. This could be done by calculating probabilities of results, or running loads of training simulations and somehow tuning the heuristic function.

• Look-ahead search/planning. There are many possible search algorithms. Most rely on you being able to simulate the impact of future decisions before taking them.

• Take account of more player knowledge. So far your simple heuristic does not take account of which cards have already been played (thus which values remain to be drawn).

Currently my AI is playing piecemeal with a very simple heuristic. I do not see how to improve this heuristic so I am wondering if it is possible to improve the performance by having a view over several turns for example. But I don't see how to simulate the next rounds since they will depend on the cards drawn.

I think the main conceptual barrier you have to improvements is how to account for the complex behaviour of probabilities for drawing specific useful cards. There are a few ways to do this, but I think the simplest would be some kind of rollout (simulated look ahead), which might lead to more sophisticated algorithm such as Monte Carlo Tree Search (MCTS).

Here's how a really simple variant might work:

1. For each possible choice of play in the game that you are currently looking at:

   1. Simulate the remaining deck (shuffle a copy of the known remaining cards)

   2. Play a simulation (a "rollout") to the end of game against the simulated deck using a simple heuristic (your current greedy choice version should be good as long as it is fast enough, but even random choices can work). Take note of the final score.

   3. Repeat 1.1 and 1.2 as many times as you can afford to (given allowed decision time). Average the result and save it as a score for the choice of play being considered.

2. Instead of choosing the next play by your heuristic, choose the one that scores best out of all the simulations.

This statistical mean of samples works in a lot of cases because it avoids the complexity and time-consuming calculations that would be required to make a perfect decision analytically from probability theory. The important things it does in your case is look-ahead planning plus taking account of additional knowledge that the player has about the state of the game.

MCTS is like the above but nested so that the simulations are made from multiple starting points.

In terms of robustness, provided you run enough rollouts per decision to be confident about the mean scores, then it should be OK.