So I made up this game, but I'm not able to find a good strategy to always win.
It's very similar to the original 3×3 Tic-Tac-Toe; but with changes.
So you draw a 5×5 board. Then each player takes turns putting a cross and circle. We then count the "scores".
This is a completed game that I drew. The scores are made by counting every 3-in-a-row strike. So for example in the top row, cross player gets 1 point.
You then do the counting horizontally, vertically, and both ways diagonally; for each row, column and diagonal.
For a 4-in-a-row, you get two points, as you can look at it as 2 different 3-in-a-rows. Similarly, a 5-in-a-row would get 3 points.
In the example game, cross wins as it get 9 whereas circle gets only 7.
I play this a lot; but it's always hard to tell where to put your next move. I've noticed that starting first gives you a significant advantage. To compensate for this, I lower the points of the player who started first by one.
Is it possible to brute force a computer to learn the best move for every game?
Thanks in advance!
Side note: If someone can program this as a simple game with random computer moves, that'd be great. I'm just getting into programming and I'm having a hard time figuring how to do it.
The snippet below will brute force all end games for player X and player O
There are 33,542,145 permutations to test of which ~ 5,000,000 are valid end games. To prevent the page locking up it splits the task into groups of 250,000 permutations
Best score for X is 16 and for O is 14. Run the snippet to see example end game layout and other details.
I did not include any handicap.
This can only do end games as it uses bit fields to keep performance high. However bit fields have no room of empty board positions.
It can be optimized to do both players at the same time by inverting the bits for each game permutation
const tag = (tag, props = {}) => Object.assign(document.createElement(tag), props);
const append = (par, ...sibs) => sibs.reduce((p, sib) => (p.appendChild(sib), p), par);
const log = (el, data, add = true) => add ? append(el, tag("div", {textContent: data.toString()})) : el.textContent = data.toString();
const scores = {
[0b00111] : 1,
[0b01110] : 1,
[0b11100] : 1,
[0b11101] : 1,
[0b10111] : 1,
[0b01111] : 2,
[0b11110] : 2,
[0b11111] : 3,
};
const rotateMat = [
0, 5, 10, 15, 20,
1, 6, 11, 16, 21,
2, 7, 12, 17, 22,
3, 8, 13, 18, 23,
4, 9, 14, 19, 24
];
const diagonMat = [
2, 8, 14, -1, -1,
1, 7, 13, 19, -1,
0, 6, 12, 18, 24,
5, 11, 17, 23, -1,
10, 16, 22, -1, -1,
];
const diagonMatUp = [
10, 6, 2, -1, -1,
15, 11, 7, 3, -1,
20, 16, 12, 8, 4,
21, 17, 13, 9, -1,
22, 18, 14,-1, -1,
];
function transform(board, matrix) {
var i = 25, b = 0;
while (i--) { matrix[i] > -1 && (board & (1 << matrix[i])) && (b |= 1 << i) }
return b;
}
function scoreLines(board) {
var i = 5, score = 0, l = 0;
while (i--) { score += scores[(board >> (i * 5)) & 0b11111] ?? 0 }
return score;
}
function score(board) {
return scoreLines(board) +
scoreLines(transform(board, rotateMat)) +
scoreLines(transform(board, diagonMat)) +
scoreLines(transform(board, diagonMatUp));
}
function isValidGame(board, side) {
var c = 0, i = 25, bits = side + 1;
while (i-- && c < bits) { (board & (1 << i)) && c++ }
return c === side;
}
function showBoard(board, score, side) {
var i = 5;
log(games, "------------------------");
log(games, "End game score: " + score + " player: " + (side===13 ? "X" : "O"));
log(games, "Example end game");
while (i--) {
const line = ((board >> (i * 5)) & 0b11111).toString(2).padStart(5, "0");
const lined = side === 13 ?
line.replace(/1/g,"X").replace(/0/g,"O") :
line.replace(/1/g,"O").replace(/0/g,"X");
log(games, lined);
}
}
function brute(side = 13) {
function doSet(i) {
var ii = 251357;
while (i >= min && ii--) {
if (isValidGame(i, side)) {
gameCount ++;
const s = score(i);
if (s >= maxScore) {
if (s > maxScore) {
bestEndGames.length = 0
game = i;
}
maxScore = s;
bestEndGames.push(i);
}
}
i--;
}
if (i >= min) {
setTimeout(doSet, 8, i);
log(progress, status + " is: " + maxScore + " tested: " + ((max - min) - (i - min)) + " of " + (max - min) + " permutations", false);
} else {
log(games, status + " is: " + maxScore + " of " + gameCount + " end games");
log(games, "Number of end games with best score: " + bestEndGames.length);
showBoard(game, maxScore, side);
if (side === 13) { setTimeout(brute, 1000, 12) }
else { log(progress, "Done", false) }
}
}
var game, gameCount = 0;
var maxScore = 0;
const bestEndGames = [];
const status = "Best score player: " + (side===13 ? "X" : "O");
const [min, max] = side === 13 ? [0b1111111111111, 0b1111111111111000000000000] : [0b111111111111, 0b1111111111110000000000000];
doSet(max)
}
brute(13);<div id="progress"></div>
<div id="games"></div>To score a game the next snippet will do so. A bit of a hack, enter game into input fields and will spit out scores.
const tag = (tag, props = {}) => Object.assign(document.createElement(tag), props);
const append = (par, ...sibs) => sibs.reduce((p, sib) => (p.appendChild(sib), p), par);
const log = (el, data, add = true) => add ? append(el, tag("div", {textContent: data.toString()})) : el.textContent = data.toString();
const scores = {
[0b00111] : 1,
[0b01110] : 1,
[0b11100] : 1,
[0b11101] : 1,
[0b10111] : 1,
[0b01111] : 2,
[0b11110] : 2,
[0b11111] : 3,
};
const rotateMat = [
0, 5, 10, 15, 20,
1, 6, 11, 16, 21,
2, 7, 12, 17, 22,
3, 8, 13, 18, 23,
4, 9, 14, 19, 24
];
const diagonMat = [
2, 8, 14, -1, -1,
1, 7, 13, 19, -1,
0, 6, 12, 18, 24,
5, 11, 17, 23, -1,
10, 16, 22, -1, -1,
];
const diagonMatUp = [
10, 6, 2, -1, -1,
15, 11, 7, 3, -1,
20, 16, 12, 8, 4,
21, 17, 13, 9, -1,
22, 18, 14,-1, -1,
];
function transform(board, matrix) {
var i = 25, b = 0;
while (i--) { matrix[i] > -1 && (board & (1 << matrix[i])) && (b |= 1 << i) }
return b;
}
function scoreLines(board) {
var i = 5, score = 0, l = 0;
while (i--) { score += scores[(board >> (i * 5)) & 0b11111] ?? 0 }
return score;
}
function score(board) {
return scoreLines(board) +
scoreLines(transform(board, rotateMat)) +
scoreLines(transform(board, diagonMat)) +
scoreLines(transform(board, diagonMatUp));
}
function isValidGame(board, side, asStr) {
var c = 0, i = 25, bits = side + 1;
while (i-- && c < bits) { (
(asStr[24-i] !== "-" && asStr[24-i] !== " ") && board & (1 << i)) && c++
}
return [c <= side, c];
}
function showBoard(board, asStr) {
var i = 0;
var j = 0;
while (i < 5) {
const line = ((board >> ((4-i) * 5)) & 0b11111).toString(2).padStart(5, "0");
const lined = line.replace(/1/g,"X").replace(/0/g,"O");
var str = "";
j = 0;
while (j < 5) {
str += (asStr[i * 5 + j] !== "-" && asStr[i * 5 + j] !== " ") ? lined[j] : ".";
j++;
}
log(games, str);
i++;
}
}
gameVal1.addEventListener("input", testGame);
gameVal2.addEventListener("input", testGame);
gameVal3.addEventListener("input", testGame);
gameVal4.addEventListener("input", testGame);
gameVal5.addEventListener("input", testGame);
function testGame() {
var board = gameVal1.value.slice(0,5).padEnd(5, "-");
board += gameVal2.value.slice(0,5).padEnd(5, "-");
board += gameVal3.value.slice(0,5).padEnd(5, "-");
board += gameVal4.value.slice(0,5).padEnd(5, "-");
board += gameVal5.value.slice(0,5).padEnd(5, "-");
board = board.replace(/[^OX\- ]/gi,"-");
const X = eval("0B" + board.replace(/X/gi,"1").replace(/O|-| /gi,"0"));
const O = eval("0B" + board.replace(/X|-| /gi,"0").replace(/O/gi,"1"));
const [vx, movesX] = isValidGame(X, 13, board);
const [vo, movesY] = isValidGame(O, 12, board);
vx && log(resultX, "Player X score: " + score(X) + " moves: " + movesX, false);
vo && log(resultO, "Player O score: " + score(O) + " moves: " + movesY, false);
games.innerHTML = "";
showBoard(X, board);
}
testGame()input {
font-family: monospace;
font-size: large;
}
.fixFont {
font-family: monospace;
font-size: large;
}
#games {
position: absolute;
top: 28px;
left: 80px;
border: 1px solid black;
padding: 0px 3px;
letter-spacing: 3px;
}
#resultX {
position: absolute;
top: 40px;
left: 160px;
}
#resultO {
position: absolute;
top: 60px;
left: 160px;
}<div class="fixFont">
Enter "x" "x" "O" or "o". Empty slots "-" or space<br>
<input type="text" id="gameVal1" value="XXXXX" size="5"><br>
<input type="text" id="gameVal2" value="XXXXO" size="5"><br>
<input type="text" id="gameVal3" value="XXXXO" size="5"><br>
<input type="text" id="gameVal4" value="OOOOO" size="5"><br>
<input type="text" id="gameVal5" value="OOOOO" size="5"><br>
<div id="resultX"></div>
<div id="resultO"></div>
<div id="games"></div>
</div>