# Is Circus Maximus solvable?

Circus Maximus is a chariot racing game in which players place their 3 chariots within the starting gate, and then take turns racing around the oval course to be the first to place all 3 chariots at the ending squares,

Since there are only 15 starting locations, and each turn both players only have access to a move 1, 2, 3, 4, or 5 in a straight line cards (or pitch a card to change direction), but still must reserve a card for each chariot...

Shouldn't this game be solvable at least as a 2-player game with minimal computing time? By solvable, I mean that a brute force solution can be obtained with PC hardware available to that average person, and a sequence of moves exists that if followed results in a win.

The rules can be found here http://boardgamegeek.com/filepage/19658/rome_rules-pdf

-
Do you have a link to the actual game mechanics? I found a few things on the web but it looks like it is more than the simple dynamics you have outlined. – Chad Jan 9 '12 at 16:23
Sorry about that. Just realized that Circus Maximus is it's own game, outside of the GMT release in Rome (triple game pack). – user1873 Jan 10 '12 at 2:05

I suspect that you're right that in principle and possibly even in practice an optimal AI could be built for this game to determine who can win from the starting position, though it would likely take more computing power than you're likely to have readily available. The best approach for brute-force solving a game like this is something close to what user1873 suggests in comments: rather than considering all lines of play, simply consider all board positions and determine the value of each board position. This is the approach that's typically taken for solving Chess endgames; while this board has many more cells (I count roughly 200, although the diagram isn't very clear) than the average chessboard, the fact that all the pieces are identical here does help a bit, and so it may be within reach; note that the chess endgames with 6 and 7 pieces have been solved for quite a while now. There are roughly (200 choose 3) = 200*199*198/6 = 1313400 positions for one team's chariots, and so roughly 1.7 trillion positions for all the chariots that would need to be evaluated.

Now, note that you don't have to build a 'move matrix' of 1.7 trillion x 1.7 trillion entries explicitly; that would be too large. Instead, the game could be solved with a sort of backtracking: first, identify those positions which are clearly won, and which person is winning them. Next, 'backtrack' - that is, play a turn in reverse - to identify all of the positions from which won positions can be reached, and then forward-evaluate each of those positions with a short move tree for that one turn to determine which of these positions lead to a forced win by one player or the other. You need a 'move tree' here because a turn isn't just a single move, but instead consists of multiple interlocking moves by the two players. Once that first turn's worth of backtracking has been done, another turn's worth can be handled in the same fashion; positions can be continuously added to a queue for evaluation, with a bunch of new 'one-move-back' positions added each time the queue empties.

Unfortunately, the catch here is in that move tree; the branching factor there is large enough that it probably pushes an explicit solve out of the realm of practicality (although perhaps not out of feasibility for someone with enough computing power). A 'move tree' consists of an assignment of the cards 1-5 to 3 chariots (plus a possibility of throwing cards away) for each player, plus some interleaving; this gives roughly (ignoring the throwaway) 75 moves at the first branch (3 different chariots that can be moved, times 10 (picking 3 cards from 5) + 10 (picking 2 cards from 5) + 5 (picking 1 card from 5) possible moves for the picked chariot) and up to 28 moves at the second branch (2 chariots that can be moved, times 4 (picking 3 cards from 4) + 6 (picking 2 cards from 4) + 4 (picking 1 card from 4) possible moves for the picked chariot). Since cards can be thrown away for turns, we'll back-of-the-envelope bump these to 100 and 50, and call it 10 moves at the bottom branch; this gives roughly 50,000 moves for each player that have to be considered in the move tree, or about 2 billion possible branches to examine on the move tree. I suspect this is highly overestimated - possibly by up to a factor of 100 or so - but a more careful analysis would be much trickier to finagle here. Even so, I'd guess there are many million possible ways of each turn playing out, and while doing some standard alpha-beta pruning (using established positional values) will cut that back down, it's still likely to take quite a bit of work at each of the 1.7 trillion nodes to establish a value.

Since positions may have to be evaluated more than once (if the first time determines that they can't be wholly solved yet), the overall work done is likely to be on the order of several exaflop (i.e., quintillions of operations total) worth of computation. That's a lot of operations - but note that you could get yourself access to a petaflop/second's worth of computational power, and thus do the whole solve in a few thousands of seconds - i.e., a few hours (possibly a few days). The biggest bottleneck is likely to be access speed to the database of values for positions, since something on the order of a terabyte (the rough size of that database) is still a bit too large to be kept in memory at this point; it'd have to be carefully designed to keep as much as feasible cached in memory and to be very smart about its disc accesses.

That said - I'd say that this is right on the edge of supercomputer feasibility right now; if the game were a bit better-known, this would make an excellent graduate project for a sufficiently motivated supercomputer programmer (or team).

-

Sort of.

A computer could brute force the optimal move each round based upon the decisions made by the opponent. You could even construct a matrix(huge) of all possible moves for a game. But there is no single path of one players choices that would guarantee a win. Your opponent can make choices that counter your choices effectively and give them the advantage and vice versa.

But there are a limited enough set of rules that it would be possible to create a matrix of all winning solutions in a modern database and based off of that database quickly return the most effective strategy to counter your opponents most recent move. That program would be non trivial to write but the rules are simple enough that it should not be unreasonable.

-
My guess was that it should be solvable, since each turn you have so few permutations of moves (fewer than 5 cards in any order (5!) * possible use on each chariot or discard (4), * possible direction for each card (6). Would probably require some pruning to remove less desirable legal moves that probably wouldn't result in a win, but could (backwards on the track). Perhaps just an examination of all possible moves from all possible positions, and which other game states that leads to) very big matrix n*(n-1)*...(n-5) different game states. – user1873 Jan 10 '12 at 16:17
@user1873 - But there is no 1 set of moves that guarantees you a win regardless of what your opponent does. But yes you could have a matrix of winning moves and each round prune off those results that no longer apply. Each round would shrink the applicable moves by a factor of around 5~15 – Chad Jan 10 '12 at 16:31
@user1873 Even with some pruning, a game with that level of branching may well be beyond brute force. Draughts (or Checkers) has a branching factor of about 10, and I don't think the lines of best play have been computed yet. – tttppp Jan 11 '12 at 8:52
I've just wiki'd it, and the best line for draughts has been found - it's a draw. It doesn't sound like it was an easy job to solve it though. – tttppp Jan 11 '12 at 9:02
@tttppp - brute force would be a bad characterization of how I would solve the problem. I would create a database of all possible branches encoded to allow an indexed and aggragated search to find the highest percentage of wins. In the event of a tie go with the highest number of wins. Each round you can prune a factor of 5. The initial setup of the db may take a few hours to complete. But once complete the run-time processing needed would be very doable. That said the effort value required is far greater the reward value. – Chad Jan 11 '12 at 14:23