有没有可能暴力破解这个 5*5 的 Tic-Tac-Toe 游戏？
Is it possible to brute force this 5*5 Tic-Tac-Toe game?
所以我编了这个游戏，但是我找不到一个永远赢的好策略。
它与 original 3×3 Tic-Tac-Toe 非常相似；但有变化。
所以你画了一个 5×5 的棋盘。然后每位玩家轮流画十字和圆圈。然后我们计算“分数”。
This is a completed game那是我画的。分数是通过计算每 3 连胜来计算的。因此，例如在顶行，交叉玩家获得 1 分。
然后你在水平方向、垂直方向和对角线方向都进行计数；对于每一行、每一列和对角线。
对于 4 连胜，您会得到两分，因为您可以将其视为 2 个不同的 3 连胜。同样，5 连胜得 3 分。
在示例游戏中，交叉获得 9 点获胜，而圆形仅获得 7 点。
我经常玩这个；但总是很难说出下一步该往哪里走。我注意到先开始会给你带来显着的优势。为了补偿这一点，我将先开始的玩家的分数降低了一个。
是否有可能强制计算机学习每场比赛的最佳着法？
提前致谢！
旁注：如果有人可以将其编程为具有随机计算机移动的简单游戏，那就太好了。我刚开始编程，我很难弄清楚如何去做。
暴力破解
下面的代码片段将暴力破解玩家 X 和玩家 O 的所有结束游戏
有 33,542,145 个排列可供测试，其中约 5,000,000 个是有效的残局。为了防止页面锁定，它将任务分成 250,000 个排列的组
X 的最佳得分为 16，O 的最佳得分为 14。运行 用于查看示例最终游戏布局和其他详细信息的代码段。
我没有包括任何障碍。
这只能做最后的游戏，因为它使用位字段来保持高性能。但是位域没有空板位置的空间。
可以通过反转每个游戏排列的位来优化同时进行两个玩家
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>
要为比赛得分，下一个片段将这样做。有点 hack，将游戏输入输入字段并吐出分数。
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>
所以我编了这个游戏，但是我找不到一个永远赢的好策略。
它与 original 3×3 Tic-Tac-Toe 非常相似；但有变化。
所以你画了一个 5×5 的棋盘。然后每位玩家轮流画十字和圆圈。然后我们计算“分数”。
This is a completed game那是我画的。分数是通过计算每 3 连胜来计算的。因此，例如在顶行，交叉玩家获得 1 分。
然后你在水平方向、垂直方向和对角线方向都进行计数；对于每一行、每一列和对角线。
对于 4 连胜，您会得到两分，因为您可以将其视为 2 个不同的 3 连胜。同样，5 连胜得 3 分。
在示例游戏中，交叉获得 9 点获胜，而圆形仅获得 7 点。
我经常玩这个；但总是很难说出下一步该往哪里走。我注意到先开始会给你带来显着的优势。为了补偿这一点，我将先开始的玩家的分数降低了一个。
是否有可能强制计算机学习每场比赛的最佳着法？
提前致谢！
旁注：如果有人可以将其编程为具有随机计算机移动的简单游戏，那就太好了。我刚开始编程，我很难弄清楚如何去做。
暴力破解
下面的代码片段将暴力破解玩家 X 和玩家 O 的所有结束游戏
有 33,542,145 个排列可供测试，其中约 5,000,000 个是有效的残局。为了防止页面锁定，它将任务分成 250,000 个排列的组
X 的最佳得分为 16，O 的最佳得分为 14。运行 用于查看示例最终游戏布局和其他详细信息的代码段。
我没有包括任何障碍。
这只能做最后的游戏，因为它使用位字段来保持高性能。但是位域没有空板位置的空间。
可以通过反转每个游戏排列的位来优化同时进行两个玩家
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>
要为比赛得分，下一个片段将这样做。有点 hack，将游戏输入输入字段并吐出分数。
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>