# Enumerating full game tree for small board game

I am trying to list all the possible positions in a small board game (nannon) (using C++)

So far I have decided to split it into two parts, the pieces that are in home positions and end positions (which aren't on the board) and the pieces that are in play (on the board).

Now, I can list the positions when the pieces are on the board with the STL algorithm next_permutation (on a 6 point structure like : point_1 = "White", point_2="empty"......point_5="Black", point_6="empty")

I am left with how to list all the positions of pieces which are off the board.

I have decided to have a set of bins:

white in home position
white in end position
White in play
black in home position
black in end position
black in play

white has three pieces that can be put in any of these bins (e.g 2 in home bin and 1 in play bin), same goes for black, like this:

white in home position = 2
white in end position = 0
White in play = 1
black in home position = 0
black in end position = 1
black in play = 2

p.s: (i tried just adding the home/end/in-play bins to the "board" structure and running next_permutation but that gives nonsensical positions like black pieces in the home bin. I guess I could just list them ALL and then prune the nonsensical ones but that seems like over kill)

• There's a fixed set of pieces right? Instead of listing the positions and enumerating which pieces can be in them, I might try listing the pieces and enumerating the positions where they can be. That way you don't have to worry about representing empty positions. Also try sorting the pieces by position, to eliminate combinations that differ only by changing the order of pieces. Commented Jul 31, 2013 at 22:35
• Why are you trying to do this? Are you making a game based on a state engine and want to predetermine all states? If so, it may be way easier to define rules and go from there. Moving between a bunch of predetermined states is unnecessary for many games.
– mobo
Commented Aug 1, 2013 at 5:55
• Thanks Nathan, that really helped. Anyway to give you points for your comment?? Commented Aug 1, 2013 at 15:02
• @cleerline No, but I posted a (slightly expanded) version as an answer. Commented Aug 1, 2013 at 21:35