Sign in to follow this  
James2130

Game Tree Creation

Recommended Posts

I need help from a smart person who knows about game state trees and their creation. I have to create a game state tree for a game called 'Fifteen' in which 2 players alternately pick a number between 1 and 9, removing it from the list of available digits and adding it to his/her total. Totals start at 0. The objective of the game is for each player to be the first to reach a total of 15 using the digits they have picked. If both players go over this amount then it is a draw. For Example: The first player can choose any digit, 1-9 beause none have been taken already. The second player, however, cannot pick the digit that player one just picked, so he only has 8 options to choose from. The digits available to the second player are determined by what the first player didnt choose in his first move. The problem is, i have to write an algorithm to create the entire game state tree. I have been given Tree ADT operations which include, Create, isEmpty, isLeaf, Add, Delete, Find to create it. I am also allowed to use other ADT's such as Stacks and Queues and i MUST create my own Node record structure to hold all data needed for the tree creation process. I have been looking on the net for information on how to create a game state tree either recursively or iteratively but ive had no luck. Any help would be greatly appreciated, Thanks.

Share this post


Link to post
Share on other sites
Well, in such a simple game, game states are represented by:
- Who is the next player?
- Who owns what number.

The children of a node are simply the states that might happen after the next player chooses a number (so a node has N children, where N is the amount of numbers left).

However, this is not a great idea, as your tree would contain O(n!) leaves, which is not acceptable (as in: a tree is not a great idea for this, since a given state can be reached in different ways, and as such find itself in two different subtrees).

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this