Jump to content
• Advertisement

Public Group

# Game Tree Creation

This topic is 5389 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

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

##### Share on other sites
Advertisement
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

##### Share on other sites

• Advertisement
• Advertisement

• ### Popular Now

• 17
• 10
• 21
• 16
• 9
• 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!