Complex Hearts AI

For some reason from the moment I heard of it, I’ve really loved the game of Complex Hearts. It’s not even that mathematical by nature–you just have to keep track of two sets of scores–but the idea of casually saying “I have -4 + 13i points” makes it an awesome game to play. So I wrote an AI for it. It’s one of the most complex (this will never get old) things I’ve ever written and it feels like a great achievement (until it epically fails against humans), so I thought I’d say something about it. It was written in C#, OOP is fairly central to its inner workings, and it uses just the four standard libraries for C# console apps (System, System.Collections.Generic, System.Linq [I did actually use Linq believe it or not. Sorting a list by value], System.Text) – I got by without using a single ArrayList!

Principles of operation

The program hinges around this single critical function GetExpectedScore(…), which attempts to determine the expected score one would accumulate after that trick if a certain card (c) is played. It’s the largest function in the program, and produces some rather convincing results. It looks at each player (p) in turn and attempts to sum the expected accumulated score from each. It does this by getting a list of point cards below the value of c, finding the probability that p has card c, arranging the point cards in order of point magnitude, then finally summing points*probabilities. It sums points by assuming each player will play the highest point card he can without winning the trick (i.e. dump the most painful card he can on you), and takes into account probabilities of being void, so there’s a sort of cascade going on. Letting P(c) be the probability p has card c, N(n) be the nth most painful card playable by p and V(n) be the score given by the nth most painful card:

ExpectedScore =
P(N(1))*V(1) +
(1-P(N(1)))*P(N(2))*V(2) +
(1-P(N(1)))*(1-P(N(2)))*P(N(3))*V(3) + …

The program sort of has two hearts, a bit like The Doctor. The first (over 200 lines) is two custom types: each player is an object, and, more importantly, the game itself is an object. This allows a trivially easy-to-implement and foolproof undo function, as well as the ability to create a duplicate game for the sake of simulations. This also includes a really primitive function for attempting to assign probabilities to players having cards (see screenshot below). It appears to be sufficient.

The second is about 350 lines of code enclosed in a region aptly labelled ‘clever stuff’. This is where the interesting functions which determine the best card to play, or the best cards to pass, all of which make use of GetExpectedScore (which itself is in this region). The best card to play is the one that has the lowest expected score determined by GetExpectedScore, and the best cards to pass are those with the highest expected scores. These tend to be high hearts, and spades of value above and including the queen.

User interface

I love console programs, and I don’t think I could have made a better UI for this using a Windows form. It’s all nicely colour coded: cyan for ‘info’, yellow for ‘notice’, red for ‘important’, green for ‘question’ and gray for ‘debug’. I even wrote a procedure to print each player’s table of card probabilities:

Click to embiggen.

Seems to work

I’ve test run it a couple of times with actual games, though personally playing the other three players slightly invalidates the testing! The AI seems to make good decisions and appears surprisingly good at not picking up points, hence doing pretty well for itself in my opinion! Apart from some interesting encounters involving code that looks like it was written while drunk (my code is normally pretty terrible) and functions I defined but never finished coding resulting in very strange happenings (“just make it return ‘1’ for now, I’ll code it later”), I’ve needed to add minor caveats here and there, such as taking into account the cards currently on the table when evaluating the probability of winning the trick and the points currently on the table when evaluating the expected score from winning that trick, and taking into account the player’s current score when deciding which card to play.

Test run. The two previous players have played the Ace of Spades (AS) followed by the Queen of Spades (QS). The player has two spades from which to choose (JS and KS). The AI recognises that although KS beats QS, potentially winning unwanted points, it realises any spade played will be beaten by AS with probability 1, so the expected accrued score from each card is 0 + 0i.

Limitations

The AI doesn’t know about shooting, or, more importantly, the existence of the 10 of clubs. I really don’t know how to incorporate that into the current structure which is a real pity considering that’s in a way the entire point of having complex scoring (otherwise you’d just have two separate sets of scores to keep track of which have nothing to do with each other). I have yet to code in the rule about breaking hearts, though it’s pretty unlikely to lead with hearts anyway considering that would tend to result in picking up points (unless you play 2H or something). It is also extremely defensive: it assumes every other player is attempting to screw it over, and consequently doesn’t bother trying to screw other players over at all. Perhaps I should include a constant that decides the aggressiveness of the program – the AI will choose to play the card that most screws over another player (c) provided that c’s expected score is no higher than a certain value, or no higher than a certain fraction of c’s value, or something. Additionally, the algo for working out expected scores is actually wrong – it makes an underestimate because it doesn’t use Bayes’ Theorem (though it’s still quite good). I should implement an improvement soon.

Advertisements

One Response to Complex Hearts AI

  1. […] used that work for the A2 computing project, did some really cool (theory-based) personal projects (1, 2), was invited to the next round of the British Informatics Olympiad (which I unwillingly turned […]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: