Cartographers simulation v0

[Carl]

I created a small script to simulate Cartographers games using a greedy algorithm. Currently, it only scores the game once, at the end of the game, and it does not take into account points for Coins (either from mountains or pieces). There are also no monsters.

https://imgur.com/a/sEg4rYW

I'm 'cheating' a little bit here, because I'm taking the best of 10 plays for a particular set of cards. However, there is no learning going across games (i.e. the simulator doesn't make use of what cards will come up later in the game).

Hopefully if I keep going there will be more interesting updates later.

[Jimmy V.]

Great!

By greedy algorithm, do you mean your bot picks a random move among the ones that maximise short-term scoring?

Also your screenshots don’t say what edicts are played. So it is a bit puzzling.

[Carl]

Updated descriptions. It picks the best move that maximizes 'long-term score', based on all the edicts coming up to score (but not taking into account when they are scored). In this case, since all edicts are scored at the end, the scoring function is simply the sum of all edict scores used.

Of course it has the obvious drawback that edicts that require 'planning', e.g. Wildholds, Borderlands, are probably not played anywhere close to optimally. The edicts which rely on short-term score and are not severely constrained (e.g. Canal Lake) are probably played pretty the best.

Given that it seems to lead to reasonable play, my idea is that it would be possible to feed these games into a policy network to create a deep (or shallow) learning engine which should play significantly better. But I'm not exactly sure how to do it so not committed yet

[Carl]

I now have a working simulation of the whole game with most rules incorporated, and most score cards from base game and heroes.

https://imgur.com/a/SjkT58p - shows the same draw of cards with and without monsters, with the same score cards and a greedy vs greedy + tweaks algorithm (some minor tweaks to make progress toward Borderlands/Wildholds in greedy strategy).

I'm showing the best of 10 plays for each layout with that strategy.

• Greedy, no monsters 116p (avg 106, std 6.7)
• Greedy w tweaks, no monsters 153p (avg 135, std 7.7)
• Greedy, 2 monsters 97p (avg 91, std 4.7)
• Greedy w tweaks, 2 monsters 122p (avg 107, std 7.3)

[Lieven D.]

I'm interested in making my own simulation, but I got stuck at how to program counting of points in for example greengold plains.

I know you get 3 points for each village cluster adjacent to at least three other terrain types, but where do you start (and stop) counting,
seems not very obvious how to program this

Do you have any hints on how I could tackle this problem?

[Carl]

I'm not sure exactly what the question is. There is a basic problem of how to identify clusters and neighbors of clusters on the board. A lot of scoring cards require that and luckily it is not that hard to identify the groups on the board.

There are simple examples here: https://www.hackerrank.com/challenges/connected-cell-in-a-grid/problem or here: https://medium.com/analytics-vidhya/number-of-islands-day-5-python-5c12783515b2. I prefer a version that counts the cells and does not alter the grid. Once you have identified the groups it's easy to identify their neighbors.

If you want to get fancier I think you can keep track of only changes in groups as new tiles are placed but I didn't do this.

Another more interesting question for an AI is how to score village cells that are not yet next to three other cells. I do this with a partial score for such clusters (e.g. 1p for being next to 2 types of terrain instead of 0). It helps the AI to look for moves that are more likely to be promising. It's quite time-consuming to test these parameters, and that's one reason why rule-based methods are not so popular, but at least it is easy to make a first attempt.

Happy to try to answer if you have more specific questions.

[Lieven D.]

Thanks for your response Carl. You understood my question well.

... and luckily it is not that hard to identify the groups on the board.

If you know how to do it, it probably isn't that hard, but if you don't...
I must say I'm far from an expert at programming, I'm not a programmer by profession.
Still, I just had a look at the provided links. Now trying to translate that into working code.
Wish me luck, I'll need it...

[Jimmy V.]

Thanks for your response Carl. You understood my question well.

... and luckily it is not that hard to identify the groups on the board.

If you know how to do it, it probably isn't that hard, but if you don't...
I must say I'm far from an expert at programming, I'm not a programmer by profession.
Still, I just had a look at the provided links. Now trying to translate that into working code.
Wish me luck, I'll need it...

Hi Lieven,

If you are not a professional programmer, then I can understand that this may be a bit tricky. It will be a good exercise for you in any case. Carl described it well, you need to be able to find clusters, their list of squares and their neighbouring clusters. Once this is done, most edicts can be written quickly.

What Carl means here is that AI is yet another level of complexity. It is a very open question as how you approach the problem. Some will give better results than others. The computing of edict scores on the other hand is pretty scripted. There are not many different ways to reach the goal, which is 100% accuracy. In the AI field, there is no such thing as 100% accuracy or perfect solution (unless the game is simple enough like Tictactoe or 4 in a row and even Reversi).

With the partial scoring of the edict, Carl gives a good example of what we did with most of our AIs here. Evaluating long-term potentials of moves is key to our AIs. We rely on these human-generated evaluations and never use any black box (Neural Network, Deep Learning, Monte-Carlo simulations) that would give a solution with little human intervention. We do it the (old) hard way, by building mathematical models of the games.