Game-tree complexity of Connect Four

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

Eebster the Great
Posts: 3170
Joined: Mon Nov 10, 2008 12:58 am UTC
Location: Cleveland, Ohio

Game-tree complexity of Connect Four

So the total number of legal Connect Four positions (including incomplete games) is known to be 4,531,985,219,092, but is the game-tree complexity (i.e. total number of legal complete games) known even approximately? I can't seem to find it online. I know game-tree complexity is impossible to estimate for very complicated games, but Connect Four seems just simple enough that it might be calculable with modern processors.

Flumble
Yes Man
Posts: 2109
Joined: Sun Aug 05, 2012 9:35 pm UTC

Re: Game-tree complexity of Connect Four

https://en.wikipedia.org/wiki/Game_comp ... nown_games
Based on the branching factor (don't ask me) and the average game length, it's in the order of 436, which is about 109 larger than the number of valid states.

Eebster the Great
Posts: 3170
Joined: Mon Nov 10, 2008 12:58 am UTC
Location: Cleveland, Ohio

Re: Game-tree complexity of Connect Four

So 5 × 1021. But I think that might just be a lower bound. It's based on a branching factor of 4, which assumes that columns fill up quicker than I think they do in the majority of possible games.

flownt
Posts: 70
Joined: Sat Feb 09, 2013 5:24 pm UTC

Re: Game-tree complexity of Connect Four

Quite quickly you have columns you cannot play because it means an immediate loss, and columns you have to play because not playing gives an immediate loss. Maybe 5 would be a better estimate, but it definately has to be less then 7

Eebster the Great
Posts: 3170
Joined: Mon Nov 10, 2008 12:58 am UTC
Location: Cleveland, Ohio

Re: Game-tree complexity of Connect Four

flownt wrote:Quite quickly you have columns you cannot play because it means an immediate loss, and columns you have to play because not playing gives an immediate loss. Maybe 5 would be a better estimate, but it definately has to be less then 7

I'm talking about the entire game tree, not just the subtree of non-losing moves.

lorb
Posts: 405
Joined: Wed Nov 10, 2010 10:34 am UTC
Location: Austria

Re: Game-tree complexity of Connect Four

The principle behind that thought still applies though, but in reverse. There will be columns that can't be played because it would be an immediate win. Winning ends the game and thus the branch of the game tree, so the column can never go higher.
Please be gracious in judging my english. (I am not a native speaker/writer.)
http://decodedarfur.org/

SuicideJunkie
Posts: 354
Joined: Sun Feb 22, 2015 2:40 pm UTC

Re: Game-tree complexity of Connect Four

If you're not worried about sub-optimal play, most columns that "can't be played" like that are less than half-dead.
If red declines to make the winning move by playing the column, black could play it for the block on the next move. Red would then have the column available as a non-winning option again.

Only if the column would give either player the win (whomever plays it first), would that column be taken out of consideration permanently.

mfb
Posts: 947
Joined: Thu Jan 08, 2009 7:48 pm UTC

Re: Game-tree complexity of Connect Four

A hard upper bound: If every player could randomly pick one out of 42 spots and the whole board is filled (don't stop with a winner), we get 42! possible games. For all 7 columns we can check the order of the moves, there are 6! permutations and only one leads to a valid game. Therefore, there are 42!/(6!)^7 possible ways to fill the whole board, about 1.4*10^31. Most of them are not legal games as they should have stopped when the first player gets 4 in a row.