Hi, Here's some food for thought for ya... You all know the classic game Yahtzee where the player have to roll 5 dice up to 3 times, hold the ones he wants to keep and re-roll the others and score points very much in a manner of a Poker game. Now, I want to program a version which allows to play against the computer... player 1 is a human and player 2 is Mr. PC and he's a real tough opponent... I would like to get some general ideas for a basic algorithm. But let's take a quick look at the three rolls: roll 1 choose a scoring option, hold some of the dice and go on to roll 2 or choose a scoring option, score and end turn roll 2 hold some of the dice and go on to roll 3 or choose other scoring option hold some of the dice and go on to roll 3 or choose a scoring option, score and end turn roll 3 choose a scoring option, score and end turn Now, of all the decisions that has to be taken after each roll I found that the most essential is choosing the RIGHT scoring options. So I think my question will come down to: How to decide which scoring options is the right one, the one that potentially will give the highest score? All ideas will be greatly appreciated...

Maybe make it probability based. There are a fixed number of "hands" just like in poker. Each has a probability. You'd score the probability that the current hand will beat an unknown player's hand. You then score the probablility of each other hand you could get by turning in dice and re-rolling or whatever. Then do some algorithm to evaluate those probabilities in order to decide if you re-roll or hold.

-me

I agree with Palidine ; you can use probabilities calculations or determine score with tree-based algorithms.
Each node of the tree would represent a roll

Thank you all for your input.

After giving the problem some thought I am quite convinced that the best approach would be the "dirty" one rather then using an algorithm,
i.e. using "If - Else logic" to cover all the different possibilities.
After each roll an analysis of the result is made (there are 7 possible results: straight, one pair, two pairs, one pair and three of a kind, three of a kind, four of a kind, five of a kind). Then according to the result a few checks are made in order to decide which available scoring option is best to go for, fine tuning the decision with each check.

For example: After roll 1 I have in hand a pair of 3's (and the 3 other dice have different values). I check if there is an available scoring option suitable for pair (i.e. three of a kind, full house, 3's and so on). If I find one (or more) I keep the pair and go on to roll 2 and then repeat the procedure. If not, I look at one of the three other dice (probably the one with the greatest value) and look for adequate scoring option for that die. In this manner I try to cover all possibilities for each of the seven dice combination which I assume is not TOO much to handle with "If - Else" logic. And thus I believe the best scoring option for each combination can be chosen better then any algorithm.
What do you think?

BTW In Yahtzee you don't have to beat the other player hand like in poker but you have to have greater final score in order to win the game.

My variation can be played akso with 6 die (http://www.download.com/NiceDice/3000-2647_4-10507485.html?tag=lst-0-7).

How good do you want your player to be?

For a really good player, you'll want both:

A strategic manager that decides "how aggressive should I play in order to defeat my opponent" and "what is the value of a scoring method".

A tactical manager that works out the probablities of various scores given the current roll and "re rolling" a given set of dice.


If you are 20 points below your opponent in the game, you should play differently than if you are 20 points ahead of your opponent in the game. That is the job of the strategic manager.

Deciding the "cost" of a given scoring mechanism is also a Strategic part of the game.


The Tactical manager is easier.

Each round consists of 2 choices and 5 random numbers. Each of the choices has 2^5 (32) options. So that is 256 branches.

The first 5 dice are always given at the point where the tactical manager takes over.

That leaves up to 6^10 random possibilities in the future (less if you choose to roll fewer dice).

It works out to about 100 million possible futures. So, given a scoring function, it wouldn't be that computationally difficult to find the strategy that generated the maximium expected score.

It would take a bit more effort to program in "aggressiveness" (ie, being willing to give up maximizing the average in order to increase the probability of a higher score) or "defensiveness" (being willing to sacrafice the average in order to minimize the chance of a lower score) by simply munging your score function.

In essence:
A Strategy is a function that takes the current game state, and generates a "score" function.

A "score" function is a mapping from (round outcome) to (value).

A Tactic is a function from a "score" function to a decision about how many dice to re-roll.

With current computers, you can write a "perfect" Tactic function (one that exaustively examines the future game-space of the current round).

There's a lot of "food for thought" in your post...
I read it 3 times and still can't say I fully understeand it.
Perhaps if you'll answer my questions [within the quote] the rest will apear more clear to me.

Quote:Original post by NotAYakk
How good do you want your player to be? [good enough to chalange a human player]

For a really good player, you'll want both:

A strategic manager that decides "how aggressive should I play in order to defeat my opponent" and "what is the value of a scoring method". [value of a scoring method? what do you mean by that?]

A tactical manager that works out the probablities of various scores given the current roll and "re rolling" a given set of dice.


If you are 20 points below your opponent in the game, you should play differently than if you are 20 points ahead of your opponent in the game. That is the job of the strategic manager.

Deciding the "cost" of a given scoring mechanism is also a Strategic part of the game.


The Tactical manager is easier.

Each round consists of 2 choices [what choices?]
and 5 random numbers. Each of the choices has 2^5 (32) options. So that is 256 branches. [could you elaborate more on that?]

The first 5 dice are always given at the point where the tactical manager takes over.

That leaves up to 6^10 random possibilities [6^10? why?]
in the future (less if you choose to roll fewer dice).

It works out to about 100 million possible futures. So, given a scoring function, it wouldn't be that computationally difficult to find the strategy that generated the maximium expected score.

It would take a bit more effort to program in "aggressiveness" (ie, being willing to give up maximizing the average in order to increase the probability of a higher score) or "defensiveness" (being willing to sacrafice the average in order to minimize the chance of a lower score) by simply munging your score function.

In essence:
A Strategy is a function that takes the current game state, and generates a "score" function.

A "score" function is a mapping from (round outcome) to (value).

A Tactic is a function from a "score" function to a decision about how many dice to re-roll.

With current computers, you can write a "perfect" Tactic function (one that exaustively examines the future game-space of the current round).

Thanks!