Jump to content
  • Advertisement
Sign in to follow this  
jsbach

algorithm wanted - food for thought

This topic is 4706 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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...

Share this post


Link to post
Share on other sites
Advertisement
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

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
Palidine's suggestion would be the best to go with; however, I think it would be better to have the computer use probabilities which have the best chance of getting it the most points, rather than whether or not it will "beat" another player's roll of the dice, because beating the player's roll and getting the most points are two completely different things.

For example, say the player gets four two's during his/her turn. For the computer's turn, if it were to then calculate what would "beat" the player's score, it could determine that four three's, four four's, four five's, four six's, five two's, five three's, five four's, etc. would beat the player. Instead of taking that route, after the first roll the computer should examine the probabilities of getting a certain combination of the dice (i.e. five of a kind, straight, full house), then compare that with which probable set would have the largest payoff (i.e. the computer may have a higher probability of getting five sixes than a large straight, but the large straight would pay more than the five sixes if the computer rolled properly).

Just my thoughts. :)

Share this post


Link to post
Share on other sites
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).

Share this post


Link to post
Share on other sites
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).

Share this post


Link to post
Share on other sites
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!

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!