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,4
white goblets from the smallest to the greatest and
A,B,C,D
black 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 = 16
e.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.
Best Answer
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.