Game-tree complexity of Connect Four

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

User avatar
Eebster the Great
Posts: 2926
Joined: Mon Nov 10, 2008 12:58 am UTC

Game-tree complexity of Connect Four

Postby Eebster the Great » Tue Dec 01, 2015 2:11 pm UTC

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.

User avatar
Flumble
Yes Man
Posts: 1990
Joined: Sun Aug 05, 2012 9:35 pm UTC

Re: Game-tree complexity of Connect Four

Postby Flumble » Tue Dec 01, 2015 2:32 pm UTC

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.

User avatar
Eebster the Great
Posts: 2926
Joined: Mon Nov 10, 2008 12:58 am UTC

Re: Game-tree complexity of Connect Four

Postby Eebster the Great » Tue Dec 01, 2015 5:28 pm UTC

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

Postby flownt » Wed Dec 02, 2015 3:58 pm UTC

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

User avatar
Eebster the Great
Posts: 2926
Joined: Mon Nov 10, 2008 12:58 am UTC

Re: Game-tree complexity of Connect Four

Postby Eebster the Great » Wed Dec 02, 2015 6:06 pm UTC

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: 404
Joined: Wed Nov 10, 2010 10:34 am UTC
Location: Austria

Re: Game-tree complexity of Connect Four

Postby lorb » Sun Dec 13, 2015 8:26 pm UTC

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: 220
Joined: Sun Feb 22, 2015 2:40 pm UTC

Re: Game-tree complexity of Connect Four

Postby SuicideJunkie » Wed Jan 06, 2016 11:40 pm UTC

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: 946
Joined: Thu Jan 08, 2009 7:48 pm UTC

Re: Game-tree complexity of Connect Four

Postby mfb » Sat Jan 09, 2016 2:51 pm UTC

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.


Return to “Mathematics”

Who is online

Users browsing this forum: No registered users and 6 guests