3
1
Write a 3D version (the game logic being 3D, not the visual representation) of the popular Connect Four game ( http://en.wikipedia.org/wiki/Connect_Four ) where the user can play against the computer. The user may freely chose the dimensions of the game board (width, height, depth) up to a limit of 10 x 10 x 10.
The computer must play an intelligent (probably even optimal) game, apart from its first move which should be random. Ideally a solution will be optimal and never lose. Like tic-tac-toe, perfect play should always result in a draw.
The first player to place four pieces in a row (vertically, horizontally, diagonally, .. (23 combinations in 3D)) wins.
Winner is shortest code.
lightxx
Posted 2013-03-20T05:59:21.997
Reputation: 131
people are talking about the search space but no one seems to have mentioned an even more fundamental issue. Shortest code and "intelligent probably optimal" do not go together. There is almost certainly no known way to demonstrate the play is optimal, which means that scoring by shortest code cannot be fair. This challenge could perhaps lend itself to a king-of-the-hill scoring (possibly with a restriction of code to say around 600 bytes.) – Level River St – 2015-02-05T09:25:31.833
Wow this question is old, what was it doing in the review queue? I think it has potential, its a shame that the scoring is problematic – Level River St – 2015-02-05T09:29:37.700
For what it's worth, 4x4x4 is probably the most interesting variant, and has already been manufactured under the name Score Four. It may also make it easier to develop an optimal AI.
– primo – 2013-03-20T07:13:19.963There was already a question about standard connect 4, which deserves more attention and answers: http://codegolf.stackexchange.com/q/5496/7486
– None – 2013-03-20T13:02:34.147so why would this other question "deserve more attention and answers"? my question has nothing to do with standard plain vanilla 2D Connect Four. – lightxx – 2013-03-20T13:04:33.900
There are only on the order of 9! = 362880 possible tic-tac-toe games, which is a trivial number to search for a computer. On the other hand, for an n x n x n board, there are on the order of pow(n, 2 n) possible 3D Connect Four games. Granted, those are loose upper bounds, but it gives one idea of the size of the search space. Is optimally solving a 10 x 10 x 10 3D Connect Four game feasible on today's hardware? – ESultanik – 2013-03-20T13:21:21.220
@lightxx, this question has everything to do with standard Connect 4. It is the exact same problem put in a larger, more generalized space. I think the 2D version is a better fit for golfing because it is not quite so complex. – None – 2013-03-20T15:19:02.410
@dan1111 I still think you are wrong. The 2D version of this game has been solved mathematically by Victor Allis (see his master's thesis here http://www.connectfour.net/Files/connect4.pdf ) and James Allen (http://homepages.cwi.nl/~tromp/c4.html ). So creating a shorter or more compact version is just a matter of code refactoring. However, none of their approaches scales well - or at all in case of Allis' approach) to 3D. So it is NOT the exact same problem.
– lightxx – 2013-03-20T18:55:59.247