Take the 2-minute tour ×
Board & Card Games Stack Exchange is a question and answer site for people who like playing board games, designing board games or modifying the rules of existing board games. It's 100% free, no registration required.

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.


share|improve this question
    
The start of the Yahtzee paper talks about prior work detailing how to maximize the score for a single player. Do you know of any similar results for single player RttA? It seems (from playing the games) like RttA is far more complex than Yahtzee. –  tttppp Feb 21 '12 at 16:20
    
@tttppp, game complexity is measured in a different way with respect to computer algorithms trying to determine an optimal strategy than the way that humans view complexity. –  user1873 Feb 22 '12 at 13:25
    
Yep, I can believe that. I still think there's a correlation between the two measures of complexity though. –  tttppp Feb 22 '12 at 15:29
1  
As an example of a game that seems more complex to humans, see "There is a game that is isomorphic to tic-tac-toe" on the wiki page for tic tac toe: en.wikipedia.org/wiki/Tic-tac-toe#Variations –  tttppp Feb 22 '12 at 15:30
1  
@DaveDuPlantis, for a probabilistic game, the game is "solved" if an optimal policy can be found: what move to make in every possible circumstance, to maximize your final score. Blackjack is "solved" in this way; you don't know if you'll win, but you'll know that you took the best possible choice given that you don't know what card comes next. (Also, as a side note, the Wikipedia page is for deterministic games; Yahtzee is not deterministic.) –  Paul Marshall Dec 5 '12 at 2:03

1 Answer 1

I think you would need to know an idle strategy for single player as a baseline (potentially using a variant where you have to keep skulls) since most building games allow you to ignore the other player if you are playing well enough. This makes solo play a great baseline for how to play multiplayer.

If you don't have a good algorithm to figure that out, deciding how to handle the other player becomes much more complex.

Finally having the solo strategy solved allows you to create significantly better baselines for determining when an action would be bad. Since you would know that in single player that move would never be beneficial, you could more quickly put together heuristics for multiplayer.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.