The first AI I made for my San Juan clone was a random one. It used random functions to determine which cards to discard to build, which cards to build, which factories to produce goods on, etc. Obviously, it wasn’t a very challenging opponent and I wanted to do better.

I looked at some other hobbyist San Juan clones to see how their AI had been written. There was one AI which people thought was challenging, and I found out that the AI had been evolved through genetic algorithms. The difficulty I was having was that there were many different actions (pick roles, build cards, discard cards, produce goods, trade goods, etc) that an AI had to do, and the AI also had to take into consideration the current state of the game such as what they and other players had in play, what they had in their hand, what roles had been called etc. It seemed like a decent AI would be a lot of if-then-else clauses.

As I thought about it more, I was able to simplify the problem greatly. I realized that at any point in the game, you only care about two things:

1. An ordering of roles you want to call
2. An ordering of cards that are important to you

(1) is only needed when you pick a role. For example, if you have 13 cards in your hand, you probably will value calling Builder highly, and then Producer, and then finally Trader, Councillor or Prospector (since you don’t need any more cards in your hand). At any given moment (although you only care when you have to pick a role) there is a preferred order given the conditions in the game.

(2) is needed much more often. The concept is that, given a set of cards, there are some I value more highly than others (because I want to build it etc). The ones I don’t value, I am free to use to pay for building or to discard them. By having an order of the cards at any given point in the game, the AI can figure out what they want to build, how to pay for it, whether they should bury a card in their chapel and also consider what role they should pick. The complexity comes because of the number of different cards, and the effect of other cards in play. Some combos are great (i.e. Aquaduct + Well), some combos are useless, and some are counterproductive (Triumphal Arch with no monuments).

By implementing these two things, I was able to create a variety of AIs with different strategies. It can still get quite complex – I haven’t tried making an AI which reacts to (i.e., blocks) another user’s strategies. I’ve also been thinking about evolving an AI, but modelling the problem domain is so foreign to me that I can’t get my head wrapped around it yet.

Posted by Kevin in Blogs Tags: android, appdev, condado