Recommend
10 
 Thumb up
 Hide
19 Posts

Hive» Forums » General

Subject: Hive Challenge - How complex is Hive? rss

Your Tags: Add tags
Popular Tags: [View All]
Randall Ingersoll
United States
Port Orange
Florida
flag msg tools
mbmbmbmbmb
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.
4 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Bartek Jarosz
Poland
Wrocław
lower silesia
flag msg tools
Avatar
mbmbmbmbmb
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
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Jarek Szczepanik
Norway
Oslo
Oslo
flag msg tools
badge
Avatar
mbmbmbmbmb
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 non-math 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.
2 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Bartek Jarosz
Poland
Wrocław
lower silesia
flag msg tools
Avatar
mbmbmbmbmb
i count all posiblites not just opening.
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Randall Ingersoll
United States
Port Orange
Florida
flag msg tools
mbmbmbmbmb
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.
3 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Randall Ingersoll
United States
Port Orange
Florida
flag msg tools
mbmbmbmbmb
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
2 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Jarek Szczepanik
Norway
Oslo
Oslo
flag msg tools
badge
Avatar
mbmbmbmbmb
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 1-4 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 3-piece layouts.

Last time I forgot Black-White 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 1-4 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 000-8=9 992 piece permutations

Final result

Piece layouts x piece permutations = 74 x 9 992 = 739 408

 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Randall Ingersoll
United States
Port Orange
Florida
flag msg tools
mbmbmbmbmb
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.



 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Randall Ingersoll
United States
Port Orange
Florida
flag msg tools
mbmbmbmbmb
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 non-symmetrical positions (5*94 = 470)
group B) figure 5 a symmetrical, 3 bug position (94)
group C) the non-symmetrical 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 non-symmetrical 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.
3 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Randall Ingersoll
United States
Port Orange
Florida
flag msg tools
mbmbmbmbmb
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
2 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Jarek Szczepanik
Norway
Oslo
Oslo
flag msg tools
badge
Avatar
mbmbmbmbmb
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.
1 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Bartek Jarosz
Poland
Wrocław
lower silesia
flag msg tools
Avatar
mbmbmbmbmb
i like that results, a lot of fun. really interesting thread
1 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Scrumpy Jack
United Kingdom
flag msg tools
badge
Avatar
mbmbmbmbmb
Berud wrote:
i like that results, a lot of fun. really interesting thread


it's the geek in boardgamegeek
1 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Randall Ingersoll
United States
Port Orange
Florida
flag msg tools
mbmbmbmbmb
I'm a Geek and proud of it !
2 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
R T
United States
Hesperia
California
flag msg tools
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/mathematics-and-chess

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 larger--I 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.

2 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Russ Williams
Poland
Wrocław
Dolny Śląsk
flag msg tools
designer
badge
Avatar
mbmbmb
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 "same-iness" 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.
5 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
LCG 74160
msg tools
mbmb
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...
1 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
LCG 74160
msg tools
mbmb
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...
 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Randall Ingersoll
United States
Port Orange
Florida
flag msg tools
mbmbmbmbmb
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.
1 
 Thumb up
 tip
 Hide
  • [+] Dice rolls
Front Page | Welcome | Contact | Privacy Policy | Terms of Service | Advertise | Support BGG | Feeds RSS
Geekdo, BoardGameGeek, the Geekdo logo, and the BoardGameGeek logo are trademarks of BoardGameGeek, LLC.