An efficient but effective artificial intelligence for Big 2

(tl;dr: You can play against an AI computer user I designed for an online Big 2 game here.  The bots are capable of calulcating the expectation for its score for every possible line of play very quickly, resulting in a rather worthy opponent for even the most seasoned Big 2 players).

The dynamics in Big 2 make programming AI for it an interesting problem.  The usual “game tree” approach when solving games like Chess or Reversi can still somewhat be applied.  However, like programming optimal AI for backgammon, there is an element of the unknown to be included.  We know the cards we hold in our hand, but how might they be distributed amongst the other concealed hands?

There are many other factors that human players have to their advantage.  They can spot and exploit players’ weaknesses and habits, bluff, and come to logical conclusions putting those two weapons together.

Emulating this behaviour and analyzing a fairly large “game tree” makes designing a fast, yet effective AI for Big 2 a challenge.  For AI that is controlled by the server (for obvious reasons it is server-side and not client-side), we have to be careful too to not take up many cycles per AI decision.  The assumption is that multiple computer players will be running at once, so for a multiplayer online gaming site, CPU cycles for AI should be minimal.

So instead of a game tree where we guess what cards will be played (and where they lie) and determine the optimal play by looking ahead, the approach taken is one giant heuristic: let’s calculate the expected value of a play simply from the cards we see and the cards we did not see up until the play.  Ultimately the goal of Big 2 is to get rid of all your cards, so we simplify the calculation by estimating how many cards will be shedded by playing a certain hand.

The process is simple: when it’s the computers turn, what are all the possible plays we have?  If a single was played, we can play another single, or pass.  If the computer is leading, then anything is possible, but passing.  Whichever the case, we have a small finite set of moves.  Now for each move, how will our hand look like after?  What will our possible plays be?  To answer this problem, we treat it as if the computer is leading a hand, and determine the set of all plays regardless if we are approached with a single, double, triple or poker hand.  Now, given the cards that are concealed in everyone else’s hand (and we know the exact set of cards, since the computer easily tracks what cards have already been played, we just don’t know how these cards are distributed — we could guess and assign probabilities, but for purposes of efficiency, we opt not to) let’s calculate how many cards we expect to shed by the end of the game.  If one of our plays in our “future” hand contains a poker hand, how likely is it going to beat all the other possible poker hands out there?  If it beats all the other possible poker hands (or a high percentage of them), how likely are we even going to be seeing a poker hand in play?  That factor is nil if the remaining players have 5 or less cards each.

Anyway, just by answering those questions above you have a relatively good gauge on expected value, and interestingly enough figuring out these probabilities is fast, by applying some good finite mathematics formulae.  One thing that human players do well is to have a game plan to run out their cards, waiting for a deuce to be played to promote one of their deuces, giving them an unbeatable exit plan.  To emulate this on the AI side, we simply do a small probability assignment ourselves: when we know a certain line of play has hands that can be unbeaten (or close to unbeaten), we can boost the probability to 1 (or close to 1) for a weaker hand that had no chance of being played unless the computer leads it itself.

So with the original probabilities calculated and the “fudging” of probabilities to emulate creating a “game plan” with a certain line of play, we have a rather decent AI for Big 2 that can give even the most seasoned players a challenge.  Although the computer still does funny stuff from time to time, it makes up for its shortcomings by doing pinpoint probability calculations quickly, and also has the inhuman ability to figure out exactly what cards are left, to accurately determine the strength of its hand.

So how does it play?  You be the judge!