Javascript 中的 TicTacToe minimax AI
TicTacToe minimax AI in Javascript
我在实现这个 I found here 的 TicTacToe AI 时遇到了问题。我对 javascript 比较陌生,所以我确定我在变量作用域方面做错了。
代码片段中不会 运行 但 heres my codepen
choices = {
0: '#ul',
1: '#um',
2: '#ur',
3: '#ml',
4: '#mm',
5: '#mr',
6: '#ll',
7: '#lm',
8: '#lr'
}
function getGrid() {
var divs = []
for (var i = 0; i < 9; i++) {
divs.push($(choices[i]).html())
}
return divs
}
function getGame() {
var divs = []
for (var i = 0; i < 9; i++) {
divs.push([$(choices[i]).html(), i])
}
return divs
}
function convertGameToGrid(game) {
var divs = []
for (var i = 0; i < game.length; i++) {
divs.push(game[i][0])
}
return divs
}
function checkGrid(divs) {
var options = [
[divs[0], divs[1], divs[2]],
[divs[3], divs[4], divs[5]],
[divs[6], divs[7], divs[8]],
[divs[0], divs[3], divs[6]],
[divs[1], divs[4], divs[7]],
[divs[2], divs[5], divs[8]],
[divs[0], divs[4], divs[8]],
[divs[2], divs[4], divs[6]]
]
for (var i = 0; i < options.length; i++) {
if (options[i][0] == 'X' && options[i][1] == 'X' && options[i][2] == 'X') {
return 'X'
} else if (options[i][0] == 'O' && options[i][1] == 'O' && options[i][2] == 'O') {
return 'O'
}
}
for (var i = 0; i < 9; i++) {
if (divs[i] == '') {
return false //still moves
}
}
return 'Tie' //no winner and no moves
}
var player = 'O'
var ai = 'X'
$(document).ready(function() {
function playerTurn(i) {
return function() {
var g = getGrid()
var cG = checkGrid(g)
if (!cG) {
if ($(choices[i]).html() == '') {
$(choices[i]).html(player)
var g = getGrid()
var cG = checkGrid(g)
if (cG == player) {
console.log('You win')
} else if (cG == 'Tie') {
console.log('Tie')
} else {
aiTurn()
}
}
}
}
}
for (var i = 0; i < 9; i++) {
$(choices[i]).on('click', playerTurn(i));
}
function score(g, depth) {
var cG = checkGrid(g)
console.log(cG, g)
if (cG == ai) {
return 10 - depth
} else if (cG == player) {
return depth - 10
} else {
return 0
}
}
function minimax(game, depth) {
var g = convertGameToGrid(game)
if (checkGrid(g)) {
return score(g, depth)
}
depth += 1
var scores = []
var moves = []
var availMoves = getAvailMoves(game)
console.log('moves', availMoves)
for (var i = 0; i < availMoves.length; i++) {
var possibleGame = game
if (depth % 2 == 0) {
possibleGame[availMoves[i]][0] = ai
} else {
possibleGame[availMoves[i]][0] = player
}
var m = minimax(possibleGame, depth)
scores.push(m)
console.log('mm: ', depth, i, scores)
moves.push(availMoves[i])
}
//even depths are ai, odd are player
if (depth % 2 == 0) {
var max_score_index = 0
var max_score = -100000000
for (var i = 0; i < scores.length; i++) {
if (scores[i] > max_score) {
max_score_index = i
max_score = scores[i]
}
}
if (depth == 0) { //we need the best move
return moves[max_score_index]
} else { //otherwise this function needs scores
return scores[max_score_index]
}
} else {
var min_score_index = 0
var min_score = 100000000
for (var i = 0; i < scores.length; i++) {
if (scores[i] < min_score) {
min_score_index = i
min_score = scores[i]
}
}
return scores[max_score_index]
}
}
function getAvailMoves(game) {
var moves = []
for (var i = 0; i < game.length; i++) {
if (game[i][0] == '') {
moves.push(game[i][1])
}
}
return moves
}
function aiTurn() {
//Dumb ai
// c = Math.floor(Math.random()*9)
// while ($(choices[c]).html()) {
// c = Math.floor(Math.random()*9)
// }
//new strategy taken from http://neverstopbuilding.com/minimax
console.log('ai')
var c;
game = getGame()
c = minimax(game, -1)
$(choices[c]).html('X')
var g = getGrid()
var cG = checkGrid(g)
if (cG == ai) {
console.log('You lose')
} else if (cG == 'Tie') {
console.log('Tie')
}
}
})
#ttt-box {
position: relative;
height: 304px;
width: 304px;
margin: 30px auto;
background-color: #bbb;
border: solid #000 4px;
border-radius: 20%;
}
#l1,
#l2,
#l3,
#l4 {
position: absolute;
background-color: #000;
}
#l1 {
left: 99px;
width: 3px;
height: 296px;
}
#l2 {
left: 199px;
width: 3px;
height: 296px;
}
#l3 {
top: 99px;
width: 296px;
height: 3px;
}
#l4 {
top: 199px;
width: 296px;
height: 3px;
}
#ul,
#um,
#ur,
#ml,
#mm,
#mr,
#ll,
#lm,
#lr {
cursor: pointer;
position: absolute;
width: 99px;
height: 99px;
font-size: 70px;
text-align: center;
}
#ul {
top: 0;
left: 0;
}
#um {
top: 0;
left: 101px;
}
#ur {
top: 0;
left: 201px;
}
#ml {
top: 101px;
left: 0;
}
#mm {
top: 101px;
left: 101px;
}
#mr {
top: 101px;
left: 201px;
}
#ll {
top: 201px;
left: 0;
}
#lm {
top: 201px;
left: 101px;
}
#lr {
top: 201px;
left: 201px;
}
<body>
<div class="container">
<div id="content">
<div id="ttt-box">
<div id="l1"></div>
<div id="l2"></div>
<div id="l3"></div>
<div id="l4"></div>
<div id="boxes">
<div id="ul"></div>
<div id="um"></div>
<div id="ur"></div>
<div id="ml"></div>
<div id="mm"></div>
<div id="mr"></div>
<div id="ll"></div>
<div id="lm"></div>
<div id="lr"></div>
</div>
</div>
</div>
</div>
</body>
我认为特别破坏的代码是下面的部分。在第一个玩家移动之后,我认为 console.log 应该打印出 8!由于应该采用所有不同的路径,因此它只打印 8 次,就好像它沿着一条路径走一样。
var availMoves = getAvailMoves(game)
console.log('moves',availMoves)
for (var i=0;i<availMoves.length;i++) {
var possibleGame = game
if (depth%2==0) {
possibleGame[availMoves[i]][0] = ai
} else {
possibleGame[availMoves[i]][0] = player
}
var m = minimax(possibleGame,depth)
scores.push(m)
console.log('mm: ', depth,i, scores)
moves.push(availMoves[i])
}
编辑:我注意到有时 minimax 递归返回未定义。我试过找出原因(请参阅我的代码笔)但一直没有成功。
Edit2:它似乎返回未定义,因为它完全跳过了这些递归。不过我还是找不到解决这个问题的方法。
首先是一个建议,因为您才刚刚起步:学习如何使用调试器。在像这样的情况下,这将是无价的,而且大多数现代浏览器都内置了它们。
关于你的问题,我没有跟踪你的所有代码,但我确实注意到一件事可能导致你的 minmax
函数出现问题。在该函数的底部,您有以下代码:
//even depths are ai, odd are player
if (depth % 2 == 0) {
var max_score_index = 0
// snip...
} else {
var min_score_index = 0
// snip...
return scores[max_score_index]
}
请注意,您在 if
块中声明和分配 max_score_index
,但也在 else
块中使用它(不分配)。这将导致它在 else
块中 return 未定义。
我在实现这个 I found here 的 TicTacToe AI 时遇到了问题。我对 javascript 比较陌生,所以我确定我在变量作用域方面做错了。
代码片段中不会 运行 但 heres my codepen
choices = {
0: '#ul',
1: '#um',
2: '#ur',
3: '#ml',
4: '#mm',
5: '#mr',
6: '#ll',
7: '#lm',
8: '#lr'
}
function getGrid() {
var divs = []
for (var i = 0; i < 9; i++) {
divs.push($(choices[i]).html())
}
return divs
}
function getGame() {
var divs = []
for (var i = 0; i < 9; i++) {
divs.push([$(choices[i]).html(), i])
}
return divs
}
function convertGameToGrid(game) {
var divs = []
for (var i = 0; i < game.length; i++) {
divs.push(game[i][0])
}
return divs
}
function checkGrid(divs) {
var options = [
[divs[0], divs[1], divs[2]],
[divs[3], divs[4], divs[5]],
[divs[6], divs[7], divs[8]],
[divs[0], divs[3], divs[6]],
[divs[1], divs[4], divs[7]],
[divs[2], divs[5], divs[8]],
[divs[0], divs[4], divs[8]],
[divs[2], divs[4], divs[6]]
]
for (var i = 0; i < options.length; i++) {
if (options[i][0] == 'X' && options[i][1] == 'X' && options[i][2] == 'X') {
return 'X'
} else if (options[i][0] == 'O' && options[i][1] == 'O' && options[i][2] == 'O') {
return 'O'
}
}
for (var i = 0; i < 9; i++) {
if (divs[i] == '') {
return false //still moves
}
}
return 'Tie' //no winner and no moves
}
var player = 'O'
var ai = 'X'
$(document).ready(function() {
function playerTurn(i) {
return function() {
var g = getGrid()
var cG = checkGrid(g)
if (!cG) {
if ($(choices[i]).html() == '') {
$(choices[i]).html(player)
var g = getGrid()
var cG = checkGrid(g)
if (cG == player) {
console.log('You win')
} else if (cG == 'Tie') {
console.log('Tie')
} else {
aiTurn()
}
}
}
}
}
for (var i = 0; i < 9; i++) {
$(choices[i]).on('click', playerTurn(i));
}
function score(g, depth) {
var cG = checkGrid(g)
console.log(cG, g)
if (cG == ai) {
return 10 - depth
} else if (cG == player) {
return depth - 10
} else {
return 0
}
}
function minimax(game, depth) {
var g = convertGameToGrid(game)
if (checkGrid(g)) {
return score(g, depth)
}
depth += 1
var scores = []
var moves = []
var availMoves = getAvailMoves(game)
console.log('moves', availMoves)
for (var i = 0; i < availMoves.length; i++) {
var possibleGame = game
if (depth % 2 == 0) {
possibleGame[availMoves[i]][0] = ai
} else {
possibleGame[availMoves[i]][0] = player
}
var m = minimax(possibleGame, depth)
scores.push(m)
console.log('mm: ', depth, i, scores)
moves.push(availMoves[i])
}
//even depths are ai, odd are player
if (depth % 2 == 0) {
var max_score_index = 0
var max_score = -100000000
for (var i = 0; i < scores.length; i++) {
if (scores[i] > max_score) {
max_score_index = i
max_score = scores[i]
}
}
if (depth == 0) { //we need the best move
return moves[max_score_index]
} else { //otherwise this function needs scores
return scores[max_score_index]
}
} else {
var min_score_index = 0
var min_score = 100000000
for (var i = 0; i < scores.length; i++) {
if (scores[i] < min_score) {
min_score_index = i
min_score = scores[i]
}
}
return scores[max_score_index]
}
}
function getAvailMoves(game) {
var moves = []
for (var i = 0; i < game.length; i++) {
if (game[i][0] == '') {
moves.push(game[i][1])
}
}
return moves
}
function aiTurn() {
//Dumb ai
// c = Math.floor(Math.random()*9)
// while ($(choices[c]).html()) {
// c = Math.floor(Math.random()*9)
// }
//new strategy taken from http://neverstopbuilding.com/minimax
console.log('ai')
var c;
game = getGame()
c = minimax(game, -1)
$(choices[c]).html('X')
var g = getGrid()
var cG = checkGrid(g)
if (cG == ai) {
console.log('You lose')
} else if (cG == 'Tie') {
console.log('Tie')
}
}
})
#ttt-box {
position: relative;
height: 304px;
width: 304px;
margin: 30px auto;
background-color: #bbb;
border: solid #000 4px;
border-radius: 20%;
}
#l1,
#l2,
#l3,
#l4 {
position: absolute;
background-color: #000;
}
#l1 {
left: 99px;
width: 3px;
height: 296px;
}
#l2 {
left: 199px;
width: 3px;
height: 296px;
}
#l3 {
top: 99px;
width: 296px;
height: 3px;
}
#l4 {
top: 199px;
width: 296px;
height: 3px;
}
#ul,
#um,
#ur,
#ml,
#mm,
#mr,
#ll,
#lm,
#lr {
cursor: pointer;
position: absolute;
width: 99px;
height: 99px;
font-size: 70px;
text-align: center;
}
#ul {
top: 0;
left: 0;
}
#um {
top: 0;
left: 101px;
}
#ur {
top: 0;
left: 201px;
}
#ml {
top: 101px;
left: 0;
}
#mm {
top: 101px;
left: 101px;
}
#mr {
top: 101px;
left: 201px;
}
#ll {
top: 201px;
left: 0;
}
#lm {
top: 201px;
left: 101px;
}
#lr {
top: 201px;
left: 201px;
}
<body>
<div class="container">
<div id="content">
<div id="ttt-box">
<div id="l1"></div>
<div id="l2"></div>
<div id="l3"></div>
<div id="l4"></div>
<div id="boxes">
<div id="ul"></div>
<div id="um"></div>
<div id="ur"></div>
<div id="ml"></div>
<div id="mm"></div>
<div id="mr"></div>
<div id="ll"></div>
<div id="lm"></div>
<div id="lr"></div>
</div>
</div>
</div>
</div>
</body>
我认为特别破坏的代码是下面的部分。在第一个玩家移动之后,我认为 console.log 应该打印出 8!由于应该采用所有不同的路径,因此它只打印 8 次,就好像它沿着一条路径走一样。
var availMoves = getAvailMoves(game)
console.log('moves',availMoves)
for (var i=0;i<availMoves.length;i++) {
var possibleGame = game
if (depth%2==0) {
possibleGame[availMoves[i]][0] = ai
} else {
possibleGame[availMoves[i]][0] = player
}
var m = minimax(possibleGame,depth)
scores.push(m)
console.log('mm: ', depth,i, scores)
moves.push(availMoves[i])
}
编辑:我注意到有时 minimax 递归返回未定义。我试过找出原因(请参阅我的代码笔)但一直没有成功。
Edit2:它似乎返回未定义,因为它完全跳过了这些递归。不过我还是找不到解决这个问题的方法。
首先是一个建议,因为您才刚刚起步:学习如何使用调试器。在像这样的情况下,这将是无价的,而且大多数现代浏览器都内置了它们。
关于你的问题,我没有跟踪你的所有代码,但我确实注意到一件事可能导致你的 minmax
函数出现问题。在该函数的底部,您有以下代码:
//even depths are ai, odd are player
if (depth % 2 == 0) {
var max_score_index = 0
// snip...
} else {
var min_score_index = 0
// snip...
return scores[max_score_index]
}
请注意,您在 if
块中声明和分配 max_score_index
,但也在 else
块中使用它(不分配)。这将导致它在 else
块中 return 未定义。