my question is about how to compute a database with initial moves for Connect Four, where each board constellation is classified as leading to a win, draw or lose.

John Tromp already has done this for the standard 7x6 sized board (https://tromp.github.io/c4/c4.html) and all board configurations with 8 tiles. Since I'm going to try to make up an AI for a larger board, these are not usable at all. Moreover I'd like to know more about the theory behind: How is it possible to determine the outcome of an initial position with e.g. 8 placed tiles, while not searching the whole game tree (which shouldn't be feasible i guess)?

  • 1
    $\begingroup$ This is highly nontrivial. You have to do a lot of optimization, take advantage of symmetries, etc... to limit the size of the search space you have to consider. But ultimately you do end up looking at a lot of positions. $\endgroup$ – Tom van der Zanden Jul 29 '16 at 12:11
  • 2
    $\begingroup$ Wikipedia (en.wikipedia.org/wiki/Connect_Four#Mathematical_solution) gives several references on this, which have complete details. Have you looked at these references? $\endgroup$ – Yuval Filmus Jul 29 '16 at 12:34
  • $\begingroup$ Thanks Tom, so it's really like "ignore some cases, but check the rest" in an efficient manner? @YuvalFilmus Actually i did not have a look at english wikipedia, and german entry didnt provide that many refs! Thanks as well! :D $\endgroup$ – hello_darkness Jul 29 '16 at 13:29

Your Answer

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

Browse other questions tagged or ask your own question.