editing

approved

There are many more game variations than positions in the game Connect Four since almost all positions can be reached in many different ways. For the regular 7 X 6 board there are 4531985219092 (4.5 trillion) legal positions (see A212693). If we estimate the number of possible games with the formula (0.75*(n+1))^(n*(n+1)-1), i.e., on average the players have 75% free columns to choose from, there are about 3.0*10^29 (300 octillion) possible games. Unless a very clever algorithm is found, some 100 terabytes of computer memory will be required to count the games for the 7 X 6 board.

proposed

editing

editing

proposed

(Python)

def next_turn(player): # there are players 0 and 1

global total, position

ngames = 0

for i in range(n+1):

fill = int(column[i]) # height of column i

if fill < n: # throw a disc into column i

position = position + 2 ** (i + (n + 1) * fill + ntimesnplus1 * player) # unique identifier for this position

if position in games: # half of memory and cpu-time can be saved if you exploit symmetry of positions here

ngames = ngames + games[position]

else:

column[i] = column[i] + 1

total = total + 1

if position in setfinalpos: # we have reached a known final position

ngames = ngames + 1

else: # check if the new position is a win or if the board is full

if check4win(position, player, fill, i) or total == ntimesnplus1:

setfinalpos.add(position)

ngames = ngames + 1

else:

numbergames = next_turn(1 - player)

ngames = ngames + numbergames

column[i] = column[i] - 1

total = total - 1

position = position - 2 ** (i + (n + 1) * fill + ntimesnplus1 * player)

games[position] = ngames

return ngames

proposed

editing

editing

proposed

a(5) = 6961765466482521226 from Kester Habermann, Mar 09 2021

a(5) = 6961765466482521226 from Kester Habermann, Mar 9 09 2021.

proposed

editing

editing

proposed

a(5) = 6961765466482521226 from _Kester Haberman_, Habermann_, Mar 9 2021.

2, 90, 356232, 152505051772, 6961765466482521226