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