4x4 tic-tac-toe is played on a board with four rows (numbered 0 to 3 from top to bottom) and 4 columns (numbered 0 to 3 from left to right). X is always going to make the first move.
The game is won by the first player to get four of their pieces on the same row, column, or diagonal(2 main diagonals only). If the board is full and neither player has won then the game is a draw.
Assuming that it is X's turn to move, X is said to have a forced win if X can make a move such that no matter what move O makes for the rest of the game, X can win. This does not necessarily mean that X will win on the very next move, although that is a possibility. It means that X has a winning strategy that will guarantee an eventual victory regardless of what O does.
Given partially-completed game with X to move next I have to determine whether X has a forced win. The game will represent a real world game and no errors are present (like number of x's more than o's etc). If there is such a forced win, the first such forced win found should be reported. For this problem, the first forced win is determined by board position.
Searching for a forced win is done by examining positions (0,0), (0, 1), (0, 2), (0, 3),(1, 0), (1, 1), ..., (2, 2),...(3, 3) in that order, and output the first forced win found. Note that there could be many moves for X that could cause a forced win - so find the first such forced win in this manner.
Example:
....
.xo.
.ox.
....
Here, X does not have a forced win. But this another example:
o...
.ox.
.xxx
xooo
(0, 1) by X is a forced win. (Even though marking x at (0, 3) and (2, 0) will make x win in the same move, we are not allowed to make a jump to any specific position. A sequential scan must be performed for each position and the order is mentioned above.)
My Approach:
So, suppose for the second example mentioned above, if i make a move by x at (0, 1) {which is the first vacant place where a move can be made}, i'll recursively call this method to determine if by marking this place as x and checking for the following under 3 different subroutines,
- Has
xwon? - Is there a draw?
- Has
owon?
These 3 conditions will be evaluated in a separate methods, each returning a Boolean value. If the return value for 1 is true, i'll return it as an answer straightaway. But if 2 is true then for the current board where x made a move at (0, 1), i'll make a move by o that prevents x from winning. The turn alteration can be made based upon the current bool value passed as a parameter to the function. To determine this move, i'll have to scan the whole board (4 rows, 4 cols and 2 diagonals) and see, if there are any places on the board where x has 3 markers out of 4.
I'm not able to figure out the next steps and i strongly feel i'm going in the wrong direction. I know that it involves recursion and backtracking.(If not then please correct me). Any sort of guidance will be appreciated.
Update:
I tried to figure out a few things on my own.
- If there are less than 6 markers in the game, then it's a draw.
- Hence, even if brute force is used for a game with 6 markers already present, complexity will be 9! for each game analysed(if simulated till the end. But once we know that it's a force win for
x, we can instantaneously return). - If marking x generates more than 2 lines with a score of 3 or more and there is no line with a score of -3 or more for o, than it's forced win for
x(On the board, i'm using 1 to denote marked asx,-1to denote marked asoand0to represent empty space). - If marking 0 generates more than 2 lines with a score of -3 or more, than it's forced for
oandxlooses. - No need to check beyond these points.
- Perform a draw check before every move.
Update2:
Tricont suggested me use minmax algorithmic approach here. But i believe it can be an overkill for this problem. It's not human vs AI game. I just need to determine the position which causes a forced win for x.If no such position exists, then it's definitely no forced win (which can be losing the game for x or a draw).
CodePudding user response：
Each field is covered by player 1, by player 2, or empty. That’s $3^{16}$ possibilities, that’s much less than 100 million.
Mark each position as X, Y or “Not allowed” depending on the number of fields covered by X vs Y: same numbers -> x is playing, one X field more -> Y is playing, everything else -> not allowed.
Mark each allowed position as won, lost, drawn or unknown: Four of the opponent colour = lost, four of your own Color = not allowed, everything filled = draw, else unknown.
Now iterate through all unknown positions: Any move to a “lost” (for the opponent) position -> won. Any move to “unknown” position -> unknown. Any move to “drawn” -> drawn. Otherwise all moves are won for the opponent -> lost.
CodePudding user response：
Minimax is the solution for this problem.
The most important idea here is that player O can be happy with a draw, and that it can be sure of at least a draw when it has put an o in at least one cell of any possible line-of-four on the grid. There are 10 such lines (4 horizontal, 4 vertical and 2 diagonal). It is not so difficult for O to get a presence in all 10 those lines. For instance, if O has occupied these 4 positions, there is no way that X could win:
...o
.o..
..o.
o...
This means it is quite easy for O to block X from ever winning, and so it is expected that a search does not have to play moves until the board is completely filled, as one of both players would already have reached their goal much earlier in the game.
Evaluation function
A minimax implementation needs an evaluation function. In this case it could decide whether the player that last played a move, has reached their goal.
- The goal for X is to win.
- The goal for O is to win or draw.
So the evaluation function could check all 10 lines-of-four and see if the last-playing player has fully occupied such a line. If found, the evaluation function should return 1 -- indicating that player has reached their goal.
Next, the evaluation function should check if O was the last player to play. If so, it could again check all 10 lines-of-four and see if O has at least one presence in each line. If that is the case, it should also return 1 -- indicating that O has reached their goal.
In all other cases, the evaluation function could return 0 -- indicating there is no clear answer yet.
As the only outcomes are 0 or 1, the evaluation function could also return a boolean. I will call that function happy.
Minimax
A minimax function returns a value. In this case we will support values -1, 0 or 1:
- -1: the player that last played cannot reach their goal
- 0: undecided
- 1: the player that last played can forcefully reach their goal.
Minimax will perform all opponent moves and find which one gives the "best" result, in this case, which evaluates to a value of 1. If such a move is found, then the previous player will get the negated evaluation back for their last move, i.e. -1. A similar logic happens for the other evaluation values that can come back from recursive calls of minimax.
Board representation
There are many ways to represent the game. I have chosen to use a bit map for both players, with one bit per position. So each player has a 16-bit bitmap, where each 1-bit in their bitmap represents a move they did. The order of moves that led to a certain state is not relevant.
The lines-of-four can also be represented as bitmaps so that a win can easily be detected by overlaying the player's bitmap with them.
Moves are represented as numbers, from 0 to 15.
Memoization
Minimax can benefit from memoization so that it does not need to go through the same search tree for evaluating the same board state twice. As I opted to represent the board with two 16-bit numbers, it is easy to identify (hash) a state by a 32 bit number.
Implementation
Here is a JavaScript implementation. You can run it here, and it will output the result for the two examples you have given. An output of a non-negative integer, means that that move is a forced win. An output of -1 means there is no forced win possible.
class TicTacToe {
static memo = new Map; // For memoization
constructor(str) {
str = str.toLowerCase().replace(/[^.xo]/gi, "");
if (str.length !== 16) throw "Invalid board size";
this.players = [0x0000, 0x0000]; // bitmaps for both players
this.lines = [ // bitmaps of winning lines
0xF000, 0x0F00, 0x00F0, 0x000F,
0x1111, 0x2222, 0x4444, 0x8888,
0x1248, 0x8421
];
this.turn = 0; // 0 or 1
// collect moves into bitmaps
let bit = 1;
let balance = 0;
for (let ch of str) {
let player = "xo".indexOf(ch);
if (player >= 0) {
this.players[player] ^= bit;
balance = player || -1;
}
bit *= 2;
}
if (balance != 0) throw "Number of X and O should be equal";
}
doMove(move) {
this.players[this.turn] ^= 1 << move;
this.turn ^= 1;
}
undoMove(move) {
this.turn ^= 1;
this.players[this.turn] ^= 1 << move;
}
happy() {
// Returns whether the player (that last moved) has reached their goal (boolean)
// For "X" this means they have 4-in-a-row.
// For "O" this means they have 4-in-a-row OR have a presence in all 10 lines
let mask = this.players[1 - this.turn];
for (let line of this.lines) {
if ((line & mask) === line) return true; // Game over. Last move was winner.
}
if (this.turn == 1) return false;
// Check whether last player ("O") cannot lose:
for (let line of this.lines) {
if ((line & mask) == 0) return false; // Opponent could still win here
}
return true; // Second player is happy with draw
}
getMoveList() {
let occupied = this.players[0] ^ this.players[1];
let moveList = [];
for (let move = 0; move < 16; move ) {
if (((occupied >> move) & 1) == 0) moveList.push(move);
}
return moveList;
}
minimax() { // Return value for player that just played (-1, 0 or 1).
let key = (this.players[0] << 16) this.players[1];
let value = TicTacToe.memo.get(key); // Using memoization
if (value === undefined) { // Not encountered before
value = 1;
if (!this.happy()) { // Undecided?
for (let move of this.getMoveList()) {
this.doMove(move);
// What is good for opponent is bad for current player:
value = Math.min(value, -this.minimax());
this.undoMove(move);
if (value == -1) break; // Opponent can reach their goal
}
}
TicTacToe.memo.set(key, value); // Memoize...
}
return value;
}
bestMove() { // Returns winning move (0..15) for X or -1 if none found
if (this.happy()) return -1; // "O" already ensured at least a draw.
for (let move of this.getMoveList()) {
this.doMove(move);
let value = this.minimax();
this.undoMove(move);
if (value == 1) return move; // forced win: return this winning move
}
return -1; // no forced win found
}
toString() { // To ease printing...
let str = "";
for (let bit = 1; bit < 0x10000; bit *= 2) {
if (this.players[0] & bit) str = "x";
else if (this.players[1] & bit) str = "o";
else str = ".";
if (bit & 0x8888) str = "\n";
}
return str;
}
}
let game;
// Test case 1:
game = new TicTacToe(`
o...
.ox.
.xxx
xooo`);
console.log(game.toString());
console.log("bestMove() returned", game.bestMove());
// Test case 2:
game = new TicTacToe(`
....
.ox.
.xo.
....`);
console.log(game.toString());
console.log("bestMove() returned", game.bestMove());There are many optimisations one could think of, but as this already runs in acceptable time, I left it like this.