In 1995 the Connect-4 Game was solved with a brute force approach. Using the standard 6 high / 7 wide grid, first player can force a win in 41 moves. Complexity of the Connect-4 game could be considered as the number of possible disc configurations, which is 4,531,985,219,092 (wiki source).
Gobblet is a zero-sum game with very simple rules and similar goal (rules here).
I would like to write a program which solves the Gobblet Game, but before trying I would also estimate the game complexity. Considering
1,2,3,4white goblets from the smallest to the greatest and
A,B,C,Dblack goblets, if my calculation is fine, a square can be occupied in 81 different ways
empty = 1
1,2,3,4,
A,B,C,D = 8
12,13,14,1B,1C,1D,23,24,2C,2D,34,3D,
A2,A3,A4,AB,AC,AD,B3,B4,BC,BD,C4,CD = 24
123,124,12C,12D,134,13D,1B3,1B4,1BC,1BD,1C4,1CD,234,23D,2C4,2CD,
A23,A24,A2C,A2D,A34,A3D,AB3,AB4,ABC,ABD,AC4,ACD,B34,B3D,BC4,BCD = 32
1234,123D,12C4,12CD,1B34,1B3D,1BC4,1BCD,
A234,A23D,A2C4,A2CD,AB34,AB3D,ABC4,ABCD = 16e.g the configuration A3D means the smallest black goblet is under a greater white goblet, which is under the biggest black goblet.
But, since we have only 24 pieces total, I expect possible board configurations are much lower than 81^16.
So I wonder how complex the game is, if calculation can be done with accuracy, or at least I would like to know if Gobblet is more or less complex than Connect-4.
$\endgroup$ 22 Answers
$\begingroup$Here's a start on improving the $81^{16}$ upper bound.
The total number of ways that gobblets can be placed on the board is no more than
$$\left({16\choose0}+2{16\choose1}+4{16\choose2}+8{16\choose3}+14{16\choose4}+20{16\choose5}+20{16\choose6}\right)^4\\=277{,}993^4\approx5.97\times10^{21}$$
That is, a state of the board is determined by specifying, for each size gobblet, how many of that size are on the board, where they are, and which of those positions are occupied by white gobblets (and which by black). For example, there are $16\choose4$ ways to pick squares on which to place $4$ small gobblets, and for each of those choices there are ${4\choose1}+{4\choose2}+{4\choose3}=4+6+4=14$ ways to pick which squares are occupied by white gobblets.
This is still only an upper bound, because some of these states are not realizable in actual play, for various reasons. In particular, it ignores the fact that there cannot be more small gobblets on the board than larger ones (because of the way that gobblets are allowed to enter into play). It also ignores the fact that the game may end before a given state could be reached. Nonetheless, $6\times10^{21}$ is several orders of magnitude smaller than $81^{16}\approx3.4\times10^{30}$, so at least it's a start.
$\endgroup$ $\begingroup$Did you ever complete your project? I am interested in hearing your results.
Building on @Barry's answer: for practical purposes, you can eliminate "equivalent" positions - i.e. all the pieces are in the same place except the board is rotated.
If you imagine a 4x4 board labeled like a chessboard (letters on bottom, numbers on side) then this holds true:
0 | 90 | 180 | 270
__________________
a1 = d1 = d4 = a4
b1 = d2 = c4 = a3
c1 = d3 = b4 = a2
b2 = c2 = c3 = b3Where the 1st column are the squares when the board is rotated 0 degrees, the 2nd column is the corresponding squares when the board is rotated 90 degrees, and so on.
This means the # of actual positions you must search is on 25% of the total number of possible positions!
$\endgroup$
