Yahtzee has been weakly solved* for single player, and uses about the same dice on average. The game is probably only slightly more complex than Yahtzee.
Can an optimal strategy for Roll Through the Ages for two players be implemented on modern hardware?
A couple of things worry me about the two player game. The two player game could technically never end, as neither player is forced to build monuments or buy developments. I am not certain that this is a problem for discovering an optimum strategy, but it could be. Another troublesome point, is that in RTtA even though you only start out rolling 3 dice, you can have you rolling as many as 7 dice per turn (as early as turn 3) instead of Yahtzee's 5 dice. This has already tripled the number of outcomes (using the bag-model described below) for the first roll of a turn.
(*Note: Given any roll of the dice, has an optimal strategy for "rerolling which dice/building which monument/buying which tech" be calculated that will maximizes your points while minimizing your losses such that you have the greatest chance of winning a game? (on current hardware))
The more I think about this problem, the less I think this community has the expertise to answer it. It is probably better suited for Math.SE, or StackOverflow.
Roll Through the Ages - (Solitaire Play)
1) Roll X Dice (x = Cities, x = 3-7)
1a) Choose dice to keep or re-roll, (skulls must be kept in the multiplayer game).
1b) Choose dice to keep or re-roll, (skulls must be kept in multiplayer game)
2) Feed Cities and resolve disasters.
3) Build Cities and/or Monuments.
4) You may buy up to 1 development.
5) Discard Goods in excess of 6.
Game ends at the end of the round when one player has 5 developments, or all monuments have been completed by at least one player. (solitaire play ends only on the 10th round).
Game Complexity
You can look at the complexity of a game it two different ways.
All possible games (game tree size), or all possible game states (state-space complexity).
From this paper about Optimizing Solitaire Yahtzee scores. You can see one of the generalizations about the game tree. The completely specified game tree is very complex.
(game tree size) = (permutations rolling 5 six sided dice) (ways of rerolling)^(2 times) (ways of choosing score line)
(game tree size) = (6^5) * (7^5)^(2) * (13!)
(game tree size) = (approx) 1.725 10^170
Trying to solve Yahtzee using this model is not feasible using modern desktop hardware. This isn't a problem, because the previous model made some assumptions that aren't true. For one, it assumes that you can distinguish between the different dice. This of course isn't the case. A roll of { 1, 1, 1, 1, 2} is exactly the same as { 2, 1, 1, 1, 1} (as well as 3 other rolls).
|Value |Lists|Bag|Lists|
+---------+-----+---+-----+
|a,a,a,a,a| 1| 6| 6|
|a,a,a,a,b| 5| 30| 150|
|a,a,a,b,b| 10| 30| 300|
|a,a,a,b,c| 20| 60| 1200|
|a,a,b,b,c| 30| 60| 1800|
|a,a,b,c,d| 60| 60| 3600|
|a,b,c,d,e| 120| 6| 720|
+---------+-----+---+-----+
Total |252| 7776|
+---+-----+
The bag model versus the list model gives us a reduction in possible dice states (from 7776 to 252) (Note: For RTtA, if you are rolling 7 dice, the bag model only has 792 (instead of 279936) initial outcomes on the first roll). Using this model does make it more difficult to calculate all the possibilities of what you can reroll. I won't go into the details (read the linked white paper if you are interested), but it reduces the game-tree size to 2.806*10^119 (51 fold decrease). This is a model of the entire game-tree, and it could be used to determine the optimal strategy from any point in a game. A similar bag-deterministic model can be used for RTtA to reduce complexity, but this isn't really what we are trying to solve. What we are really interested in, is the state-space complexity. Jakub Pawlewicz's paper has done even more optimization to remove the number of edges (transitions) from one state (node) to another, and mentions that what would have taken 10 minutes without edge optimization only takes 30 seconds on modern hardware.
More research.
