Randall Ingersoll
United States Port Orange Florida

There has been much discussion about the width and depth of Hive compared to other games such as Go and Chess. And the question whether Hive will ever be 'solved' meaning that with best play on both sides either one side will always win or the game will always end in a draw.
This has prompted me to wonder: "How many different ways can a Hive game start?"
So, here is the challenge:
1) Use only Hive Standard (no Mosquito or Ladybug)
2) Assume BoardSpace rules (no Queen placed on the first turn by either player)
3) If the Queen is placed second, turn three will not be wasted on a Queen move
4) Ignore positions that are identical except for rotation and/or reflection
How many unique positions are there after the placement of three bugs by each player?
I have calculated what I think is the correct answer, which I will post in about a week.
What do you think?
2,000
5,000
10,000
25,000
over 100,000
Have fun.

Bartek Jarosz
Poland Wrocław lower silesia

i'm not a math guy, but i count it that way:
each hex have 6 walls and each player have 11 hex so 11x2x6 = 132 walls, and factorial from 132 (132!) is 1.11824865 × 10 Exponentiation 224
pretty impressive

Jarek Szczepanik
Norway Oslo Oslo

A good exercise on probability theory. I think I have the answer IMO rotations and reflections shouldn't be taken into account, because there are no numbered fields in Hive. They are just transformations of the same layout, however are difficult to sort out.
The number I've obtained is pretty impressive. It isn't as big as Bartek's, but is still surprising, even if you set aside reflections and rotations. Well, one thing is sure: solving Hive will be a Stupendous task
A hint for all nonmath people: estimate how many different pieces you have in each turn and how many positions to place a piece are there on each turn.
@Bartek: remember that new pieces placed on second and third turn can't touch enemy fields. In addition, it's indifferent for the outcome, which of three Ants or two Beetles is played.

Bartek Jarosz
Poland Wrocław lower silesia

i count all posiblites not just opening.

Randall Ingersoll
United States Port Orange Florida

The first step is to determine how many unique positions can be formed with the placement of the first three bugs. Here they are:
This is just a fun exercise in combinatorial and permutational mathematics.

Randall Ingersoll
United States Port Orange Florida

According to my calculations here are the answers:
For standard Hive, 164,880 unique positions after each player has played three bugs.
For Hive with one expansion bug: 276,840
For Hive with both Mosquito and Ladybug: 343,992

Jarek Szczepanik
Norway Oslo Oslo

Hmm, how did you come to this result? Mine was 739 408 for standard Hive, but I'm not sure if I'm correct.
My reasoning was as follows:
I. How many combinations of different piece layouts are there?
Out of seven positions you showed, let's forget about number 5&6 for a moment and let's focus on numbers 14 and 7. There are 15 ways (combinations with repetitions  2 elements out of 5) to combine them. Moreover, each combination for the second player can be flipped vertically, giving different shape, so you have to double the number (15x2=30). As for shapes number 5 and 6 they're symmetrical themselves, vertical flipping won't yield anything new. They can be combined with other shapes and themselves on 13 additional ways.
Putting it together, you have 43 different 3piece layouts.
Last time I forgot BlackWhite swaps. These are calculated as follows:
The swaps are only important if we combine two different piece layouts from your drawing  combinations of 2 out of 7 without repetitions = 21 (when combining two identical layouts colour swapping makes no sense, hence combinations without repetitions) Again we have to include vertical flips for layouts 14 and 7 (combinations of 2 out of 5 without repetitions) = 10. So, we have 21+10=31 layouts with swapped colours.
Total number of different piece layouts = 43 + 31 = 74
II. Piece permutations
The rest is simple: each player can play 4 different pieces on first turn, 5 on second, 5 on third: 4x5x5x4x5x5=10 000
Playing two Spiders or two Beetles on first turns
This isn't the final result. When one or both players play two Spiders or two Beetles during first two turns, there will be only four bugs available for the third one. There are eight such situations, so we have 10 0008=9 992 piece permutations
Final result
Piece layouts x piece permutations = 74 x 9 992 = 739 408

Randall Ingersoll
United States Port Orange Florida

Let's start with how many different ways can the first three bugs be placed.
There are 4 choices for the first bug and 5 choices for the second bug and thus 20 ways that two bugs can be placed.
In 6 of these 20 positions there are only 4 choices for bug #3. (If the Queen is placed second (4 choices), if both Beetles have been placed, or if both Spiders have been placed)
In 14 of these 20 positions there are 5 choices for bug #3.
The total different ways that three bugs can be placed is: 6*4 + 14*5 = 94
This count applies to 6 of the 7 initial figures (even though the position in figure #7 can be reached in two different move orders, the final position is the same).
The count is different for position #6. (In position #6, by reflection, GAQ and GQA result in the same position.)
There are 54 unique bug combinations for position #6. (If you would like me to list them, let me know.) Of these combinations, 14 of them are symmetrical. (For example, GAA is symmetrical, GAB is not.)
My next thread will take the above information and calculate the total.

Randall Ingersoll
United States Port Orange Florida

Now let's calculate how many different positions that three White bugs can take.
6 figures * 94 positions = 564 1 figure * 54 positions = 54 total # of White positions = 618 (and the same for Black)
But we cannot just take 618 * 618 to get the total because of the symmetrical figures #5 and #6 and the possibility of reflections.
(At this point in describing my reasoning, I just realized that I made a HUGE MISTAKE on my spread sheet that I used to do the math ) So I must recalculate my numbers that I posted earlier!)
White's 618 positions must be split into 4 groups. group A) the 5 nonsymmetrical positions (5*94 = 470) group B) figure 5 a symmetrical, 3 bug position (94) group C) the nonsymmetrical positions arising from figure 6 (40) group D) the symmetrical positions arising from figure 6 (14)
Combining 4 groups for White and 4 groups for Black we get: (Note that when both players play nonsymmetrical openings, the total must be doubled due to reflection)
White/Black A/A  470 * 470 * 2 = 441,800 A/B  470 * 94 = 44,180 A/C  470 * 40 * 2 = 37,600 A/D  470 * 14 = 6,580 B/A  94 * 470 = 44,180 B/B  94 * 94 = 8,836 B/C  94 * 40 = 3,760 B/D  94 * 14 = 1,316 C/A  40 * 470 * 2 = 37,600 C/B  40 * 94 = 3,760 C/C  40 * 40 * 2 = 3,200 C/D  40 * 14 = 560 D/A  14 * 470 = 6,580 D/B  14 * 94 = 1,316 D/C  14 * 40 = 560 D/D  14 * 14 = 196
GRAND TOTAL = 642,024
I am SO mad at myself for the stupid mistake in my spread sheet that resulted in the wrong numbers posted earlier! ! ! !
But I am reasonably sure that this figure is correct.

Randall Ingersoll
United States Port Orange Florida

New totals with my stupid spread sheet mistake fixed:
With standard Hive  642,024 With one expansion bug  1,078,848 With both expansion bugs  1,306,176

Jarek Szczepanik
Norway Oslo Oslo

Don't worry about mistakes. There are too many things to take into account and making one is easy. I tried three times and obtained two different results I forgot one important thing too and had to correct my previous calculations here. This time the number is higher than yours. One thing is sure  there are over half a million combinations. And the number will rise with each turn. For solving the game however it is more important, how many good/most efficient moves are there during each turn.

Bartek Jarosz
Poland Wrocław lower silesia

i like that results, a lot of fun. really interesting thread

Scrumpy Jack
United Kingdom

Berud wrote: i like that results, a lot of fun. really interesting thread
it's the geek in boardgamegeek

Randall Ingersoll
United States Port Orange Florida

I'm a Geek and proud of it !

R T
United States Hesperia California

I was curious how many possible chess positions there are after 3 moves. There are 20 possibilities for the first move (8 pawns moving 1 or 2 spaces ahead, plus 4 knight moves) and on the next two moves you only have significantly more options in the cases where a bishop or the queen is freed. It turns out that there are on average about 22 moves available in each subsequent position and the actual number of possible positions after 3 moves by each player is 9,132,484:
http://www.chess.com/chessopedia/view/mathematicsandchess
This is not to say that chess is more complicated than Hive, though. Hive doesn't start out with all the pieces in play. The play space ("board") for Hive is largerI played a game of hive recently that was wider and higher (well, diagonally) than a chess board, although the One Hive Rule does limit the possible positions somewhat. Additionally, most chess games simplify down to only a few pieces in the endgame due to captures. Now, many hive pieces are pinned in the end but there are still many active and most could be freed with some effort.
My feel for the game is that Hive is much more complicated than checkers and at least on par with chess. Moreover, the game is still in development and I would contend that it can be made more complicated still by adding appropriate new bugs to the mix.

Russ Williams
Poland Wrocław Dolny Śląsk

Clavaine wrote: I was curious how many possible chess positions there are after 3 moves. Such mathematical analysis seems interesting indeed, although I would caution about equating the size (total number of nodes, or average branching factor, or depth, etc) of the game tree with strategic depth or interest. A big game tree seems necessary but not sufficient to make a game interesting.
I.e. it's necessary since otherwise the game is too easy to fully analyze/solve and play well. But it's not sufficient since if the best move is easy to find, it doesn't matter if there are always thousands of other candidate moves.
And of course if the game is too opaque, or simply boring, then a huge game tree is of no benefit: such mathematical analysis can't capture more subjective elements like "Is a game interesting and fun? Does it somehow resonate with many people? Do the strategic decisions which one makes while playing the game usually feel interesting?"
(I don't mean this as a specific comment about chess vs Hive, just a general comment about the benefits and limits of such mathematical analysis of a game's game tree.)
Quote: My feel for the game is that Hive is much more complicated than checkers and at least on par with chess. My (very subjective) feeling is that there is a bit more feeling of "sameiness" with Hive than with chess, although I enjoy both games. But it may be that the relative lack of strategic information about Hive compared to chess is the problem here. (I should check out Randy's Hive strategy book.)
Quote: Moreover, the game is still in development Agreed, it may well be that the richness and diversity of strategies & tactics will increase with time as more approaches are discovered and developed!
Quote: I would contend that it can be made more complicated still by adding appropriate new bugs to the mix. That seems "unfair", in the sense that you could also make chess (and any other game) more complicated by adding new pieces to the mix. If one wants to compare 2 games, then compare the 2 games as they are, not a current snapshot of one game versus a hypothetical more complicated future version of the other game.



rmingersoll wrote: New totals with my stupid spread sheet mistake fixed:
With standard Hive  642,024 With one expansion bug  1,078,848 With both expansion bugs  1,306,176
I have taken a different approach: use a program to try all the possible (legal) bug placement moves and then eliminate the equivalent boards by rotation and flipping.
I get 680,032 different boards if we only allow new bugs to be placed and 703,604 different boards if we allow existing bugs to be moved.
If there is enough interest in this two years old thread, we can dig further to understand these discrepancies...



lcg74160 wrote: If there is enough interest in this two years old thread, we can dig further to understand these discrepancies...
... which mostly come from the fact that I do differentiate the bugs in my approach (i.e. wA1 is different from wA2) but not only...
After removing the bug instance identifiers, I come up with a new total of 633,188.
I have the feeling that this is closer to reality because the total of 642,024 seems to count illegal positions. For instance, it counts both white and black playing with position #2, which would form a ring so impossible to get only placing (as opposed to moving) bugs...

Randall Ingersoll
United States Port Orange Florida

lcg74160 wrote: I have the feeling that this is closer to reality because the total of 642,024 seems to count illegal positions. For instance, it counts both white and black playing with position #2, which would form a ring so impossible to get only placing (as opposed to moving) bugs...
Aha, I think that I missed this.


