1
$\begingroup$

I've seen perfect solvers of the game Connect 4 using various methods. The one that I saw uses alpha beta pruning. Is it possible for a human to learn to play Connect 4 perfectly like these solvers do? Using alpha beta pruning specifically isn't necessary.

$\endgroup$
3
$\begingroup$

It really isn't possible for two reasons.

First, yes, it is theoretically possible to construct the whole tree. You could then trim the tree to just show the "good" moves. But the tree would be enormous and much too large for a human to memorize (except for some trivially small version). The tree is so large that you couldn't move the "book" around with a wheelbarrow. ;-)

As a side note the fact that computer programs use alpha-beta pruning is a testament to how large the tree is. If the tree were "small" the computer program would just examine the whole tree and select only "good moves."

Second the branching at any node in the tree is far too complicated to derive some simple heuristic to derive the correct move. So there isn't some kind of parity function for example where you could "easily" calculate what the next move should be like you can calculate for Nim.

$\endgroup$
  • 1
    $\begingroup$ Can you give a source for these claims? ("The tree would be enormous and much too large for a human to memorize", "The branching is far too complicated to derive some simple heuristic to derive the correct move.") $\endgroup$ – Travis Willse Apr 11 '16 at 22:30
  • $\begingroup$ Look up the Wikipedia article. It gives a good starting point. en.wikipedia.org/wiki/Connect_Four $\endgroup$ – MaxW Apr 11 '16 at 22:37
  • $\begingroup$ @Travis : if you know how to program the solver based on alpha beta for this game, you will also be able to run it on a paper. and alpha beta is cool because when the tree is too big, you can still select randomly one of the best moves you found (as people do when playing chess) $\endgroup$ – reuns Apr 11 '16 at 22:39
  • $\begingroup$ The OP asked about playing "perfectly" not well. If you use alpha beta pruning then you can't play perfectly since the "bad" move might not be discovered till the next ply. $\endgroup$ – MaxW Apr 11 '16 at 22:41
  • $\begingroup$ @MaxW Perhaps you can edit your answer to say more. I certainly believe the claims, but as it stands your answer is a verbose "no" and contains no justification for why that's the case. $\endgroup$ – Travis Willse Apr 11 '16 at 22:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.