Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

For fun I am building the game 5 crowns. Well I've gotten to the point where I am implementing the rules for the computer players. I've found that my decision tree has so many nodes on it that I wonder if it would be easier to implement an algorithm that would take a small subset of the nodes and infer the rest from that basic subset.

Basically I would like to input a subset of rules.
So the following are the rules for each round

  • Round number determines which card is wild
    • Minimum card value is 3 so in round one 3's are wild.
  • You may only have a specific number of cards in your hand.
    • The amount of cards in your hand is equal to the value of the card that's wild.
  • You can draw from the discard pile or the deck.
  • Your goal is to be the first one to lay down their hand by building sets or runs.
    • A set or run must have at least 3 cards in it.
    • Runs can only have cards of the same suite.
  • After a player lays down their hand each remaining player has one more turn to lay down.
  • Any cards left in your hand when the round ends are totaled and added to your score.
  • Higher cards are worth more points.

So if my hand was the following, and it was the first round (I.E. 3's are wild):

hand = [{value: 3, suite: hearts},  //3 of hearts
        {value: king, suite: clubs}, //king of clubs
        {value: 7, suite: spades}]  // 7 of spades

And the card on top of the discard pile is a 5 of diamonds ({value: 5, suite: diamonds})

I would engage in the following thought process:

  • The 5 has a lower score then the 12 or 7, which would be good if I can't lay down when the round ends.
  • However, unless someone before me has already laid down, I will have at least one more turn; at which point, if I need to, I can ditch the 12.
    • There is a high probability that if the player right before me has a 12, they will dump it. Allowing me to pick it up next turn and lay down.
  • This may not be the first turn and I may of seen the player after me take a 7 or 12.
  • If I draw a card there is a higher probability of getting something useful (I.E. another 7, 12, or wild). Which would let me go out.

Most human players would accept the risk inherent in keeping the 7 or 12 and draw a card from the deck, instead of taking the 5.

The above logic isn't very hard to implement. It's when you extrapolate it out and have to do the cost/benefit analyses on 13 cards in your hand, that decision making tree becomes a lot more complex. Which would be why I want to look into machine learning to solve this problem.


As a note I have already implemented the logic to determine if you can go out. The above applies to how the computer should evaluate the pro's and cons of a specific action (which card to draw, and which card to discard, and to an extent, when in higher rounds, how to structure the runs/sets needed to lay down it's hand).

share|improve this question
3  
Wow... I got lost very quickly. Any chance you can make it easier to read/understand? –  Polar Apr 9 '13 at 22:41
    
@Polar revised it –  ryan Apr 10 '13 at 6:29
add comment

4 Answers

up vote 2 down vote accepted
+50

The best technique to use here is Reinforcement Learning.

These techniques rely on feedback from the environment in order to learn. Feedback takes the form of a numerical reward signal, and guides the agent in developing its policy. You can model the environment as a Markov decision process, which is defined by a set of states, actions, transition probabilities, and expected rewards. Each action has a probability of being the action selected, as well as an associated value, which corresponds to the expected reward of taking the action. A greedy action is an action that has the greatest value. In order to learn, the agent must balance exploration and exploitation of the environment. During exploration, the agent tries non-greedy actions in hopes of improving its estimates of their values.

One of the most easiest ways to implement a Reinforcement Learning algorithm is using the Q-learning algorithm.

share|improve this answer
    
How do you suggest the value of the reward signal be determined? The hard part of this problem is knowing what a good move is, rather than teaching something to make good moves once you know what they are. –  Bogdanovist Apr 19 '13 at 11:04
    
That's the beauty of this algorithm you only need to define the reward when you reach a "winner" state. Then the algorithm "learns" the reward of all the different intermediate transitions. This is a good Q-learning tutorial –  auriarte Apr 19 '13 at 15:24
add comment

What you're looking for is called a supervised neural network.

This is a neural network that is trained with known data, rather than pitting a fitness function against unknown data. Where do you get the known data? You'll create it yourself.

There are two ways to do a cost/benefit analysis. The first is to determine some algorithm to predict likely cost and likely benefit of any action. The second is to record actual costs and benefits. The latter is only possible with large sources of data, but with modern computing and an easily automated process (such as your game), you can create this data fairly simply.

The data will be derived through many hundreds or thousands of sessions per set (the more sessions, the more accurate the analysis). These sessions will randomize all unknown data (other players' hands, the draw pile) and keep consistent the known data (turn number, player's hand, discard pile, whether it's the final turn). The decision made (draw from discard pile, draw from draw pile, etc) for a turn will be random, but remembered.

The reason to keep the known data consistent through the set of sessions is because this data will be the neural network's input. The reason to keep the unknown data random is because you want to teach the AI the odds of a decision based only on the known data. The reason to randomize the decision made is that the important aspect of the session is not which decision was made but the result of of the decision.

The sessions in a set give you results tied to decisions. This gives you, over the course of many sessions, the actual costs and benefits of each choice. For example, you might end up with, given a certain hand and a certain discard pile card, 20% of the "Draw from Discard" sessions resulted in a positive outcome, while 40% of the "Draw from Draw Pile" sessions resulted in a positive outcome. Or you could be recording the outcome as a continuous variable instead of a binary "good/bad", so you might find the average of one choice to be 0.87 and the average of the other to be 0.34.

This data is then used to trained the neural network. The known data is the input (number of turn, final turn yes/no, cards in hand) while the outcome of your set of sessions is the output of the neural network. Over many thousands of sets, the neural network will learn, given a random hand and other known variables, what the odds are for drawing from the discard or drawing from the draw piles (or any other choices one could make, such as discarding cards).

Notes:

  1. Running through thousands of sets of thousands of sessions might seem worrisome, but this entire process is automated, from a single session to the training of the network. It can be done overnight if the process seems too lengthy.

  2. You can play the sessions through the entire round, or you can play only a single turn. Playing through the round means a simpler analysis of the benefit of the decisions made (won or lost) but a slightly more complicated process of analysing each choice. A single turn means determining some function to score that turn's benefit/cost (if you gained a set, the sum of the card numbers, etc), but a simpler process integrating it into the neural network.

share|improve this answer
add comment

Maybe you should take a look at the Genetic Algorithms.

To solve your problem with these you basically need a function with the tree as the input and a number as output. If the number is higher, the decision tree is better.

The crossover function could be that you take some leaf parts from the tree and insert it at random places in the other tree.

The random mutation function could be that you randomly create treeparts and operations.

share|improve this answer
add comment

I think you are misunderstanding the role of machine learning, at least in its current 'off the shelf' form. In order to apply machine learning to assist with a decision you need to be able to reduce the problem into a set of values of a number of consistent inputs, a set of possible outputs to choose from and a function that lets you assess the comparative utility of the different outputs.

For your problem, getting it into this form is a much more difficult problem than applying some machine learning algorithm once you've done that.

To put in another way, machine learning doesn't do the cost/benefit analysis for you, it requires that to be implemented in order to optimise some algorithm for making decisions to optimise the cost/benefit. Doing the cost/benefit is the hard part of your problem, but it's not something that machine learning will help you with.

The way that you could implement machine learning would be to do no cost/benefit analysis at all and measure everything simply by games won, using that as your metric to evaluate models. Say you come up with an algorithm for playing that game that depends on a number of free parameters. If you have that algorithm play thousands of games against itself, you can use any multidimensional minimisation algorithm to search for the set of parameter values that is most likely to win. You still need to come up with that algorithm yourself though. You could use something like a neural network, which come with some standard ways of training the free parameters against the fitness function (in your case, winning the most number of games).

The down side to this approach is that it is essentially a black box and you are training the algorithm against itself (or some other similarly parametrized models), so you are not training it to be the best algorithm possible, just one that is the best possible given the limitations imposed on it by how you construct it. Once you have trained the model it can be difficult to understand why it makes particular moves so it can be difficult to correct the propensity to consistently do something silly in a particular situation.

share|improve this answer
add comment

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.