Is there it possible to create a function that checks for the best next move in this Connect N game?

Input:

M = [0,0,0,0,0,0,0;0,0,0,1,0,0,0;0,2,1,2,0,0,0;0,1,1,1,0,0,0;2,2,1,1,2,0,0;1,2,1,2,1,1,2]

Visualized:

0	0	0	0	0	0	0
0	0	0	1	0	0	0
0	2	0	2	0	0	0
0	1	1	1	0	0	0
2	2	1	1	2	0	0
1	2	1	2	1	1	2

Is there it possible to create a function that checks for the best next move in this Connect N game (in this case N = 4)

A connect N occurs when N pieces line up horizontally, vertically or diagonally.

This is the function that I'm using to check for victories, this might help, but I wouldn't know how to use this for that purpose myself:

function victory = checkVictory(M, N);
    victory = 0;
    checkWin = @(x)conv2(x,eye(N),'same')>=N | conv2(x,flipud(eye(N)),'same')>=N | conv2(x,ones(N,1),'same')>=N | conv2(x,ones(1,N),'same')>=N;
    teamOne = checkWin(M == 1);
    teamTwo = checkWin(M == 2);
    
    if any(teamOne(:)) == 1
        victory = 1;
    elseif any(teamTwo(:)) == 1
        victory = 2;
    end
    
end

Answer 1

[John D'Errico]

Of course it is possible. You simply generate a tree of all possible moves, checking to see if a win occurs. A forced win arises if player 2 has no countermoves that prevent an eventual win by player 1 (or vice versa.) The problem is, said tree of moves might become rather unwieldy, since there may be many moves at each turn for each player. But this is completely possible, at least in theory. The nub comes in terms of your skill in programming (something I would not do for you anyway, since this is your homework after all.)

A more intelligent scheme might come up with a rating algorithm whereby the board is evaluated in terms of its "goodness" for player 1 or 2. This is not much different than in chess. Until you get to the point where a forced win in a short period of time can be foreseen, you simply optimize the positional evaluation. (At each turn, you would probably check for a forced win on the next turn. Arguably, a good evaluation tool would put that into the positional evaluation.)

The above scheme will depend on how good is your algorithm. Of course, that has nothing to do with MATLAB, but is entirely your skill at developing a good positional evaluation algorithm.

But you asked if it is possible. OF COURSE IT IS. The game has finite length, and a finite tree size.

Just note that chess has the same attributes - any game has a finite number of possible moves at ay point in time, and it cannot go forever. Therefore, chess can theoretically be analyzed to see if a forced line exists to win for white or black starting from the initial setup. That this has never yet been done, despite the huge computers that can be thrown at the problem points out the difficulty of a complete tree search. So you need to consider if something is practically possible, as opposed to theoretically so. Again, skill at programming is of huge importance, and the size and speed of the computer you would throw at the problem.

The above argument points out that the best chess playing computers out there now seem to be using an AI tool to learn how to play the game, from scratch. They try moves, seeing if it results in a win, playing against themselves. The application of machine learning techniques now allows the creation of a tool that learns how to play the game in question. This would be the perfect solution for the game you want to solve. Again, skill at programming is an important thing, as is understanding how to set up and implement the learning. Your problem, not mine. :)

[The Legend]

Wow. Thank's for typing all this.

[John D'Errico]

It depends on how much you want to solve the problem, how much you want to put into the solution. I'd suggest that a simple scheme that checks a SHORT tree for all possible moves by player 1 and 2, looking for forced wins would be not that hard to do. If you keep the depth of the tree small, then you can now come up with a simple scheme to evaluate any board position, lacking a forced quick win. This should be doable. Would it beat a world class connect-4 player? Probably not.