Recursion does not seem to work in my minimax implementation

The miniMax function returns an object consisting of an index and score as intended, but it does not visit as many states as expected.

Here is the code:

<!-- begin snippet: js hide: false console: true babel: false -->

<!-- language: lang-js -->

const human = 'X'
const ai = 'O'
const winOptions = [[0, 1, 2], [3, 4, 5], [6, 7, 8], [0, 3, 6], [1, 4, 7], [2, 5, 8], [0, 4, 8], [2, 4, 6]]
const emptyCells = (layout) => {
return layout.map((item, index) => {
return (item === '' ? index : null)
}).filter((item) => item !== null)
}
const checkWin = (layout) => {
for (let i = 0; i < winOptions.length; i += 1) {
const [a, b, c] = winOptions[i]
if (layout[a] === 'X' && layout[a] === layout[b] && layout[b] === layout[c]) {
return -1
}
if (layout[a] === 'O' && layout[a] === layout[b] && layout[b] === layout[c]) {
return 1
}
}
return false
}
function miniMax (gameLayout, player) {
const empty = emptyCells(gameLayout)
if (checkWin(gameLayout) === 1) {
return { score: 10 }
} else if (checkWin(gameLayout) === -1) {
return { score: -10 }
} else if (empty.length === 0) {
return { score: 0 }
}
const moves = []
for (let i = 0; i < empty.length; i++) {
const move = {}
move.index = empty[i]
player === 'O' ? gameLayout[empty[i]] = 'O' : gameLayout[empty[i]] = 'X'
player === 'O' ? move.score = miniMax(gameLayout, human).score : move.score = miniMax(gameLayout, ai).score
moves.push(move)
}
let bestMove
if (player === 'O') {
bestMove = moves.reduce((acc, curr, i) => moves[acc].score > curr.score ? acc : i, 0)
} else {
bestMove = moves.reduce((acc, curr, i) => moves[acc].score < curr.score ? acc : i, 0)
}
console.log(JSON.stringify(moves))
return moves[bestMove]
}
// Example run:
const layout = ["X", "", "" , 
"" , "", "" ,
"" , "", "O"]
miniMax(layout, "X")

<!-- end snippet -->

Here is how it looks, with the console output as produced in the above snippet:

Clearly my minimax implementation for Tic Tac Toe doesn't work as expected. The console should be flooded with output, since there are many options for enumeration. But it displays only 6 lines of output, as if the recursion does not work and does not go into every possible option.

I've been trying to find a bug for days... What is wrong with this implementation?

The problem is that the played moves are not taken back. The function is called recursively as intended, but then the board is full and it never changes after that. By consequence empty.length will be 0 for all execution contexts, and the recursion will unwind without making other moves.

To fix this, add this line after the push:

gameLayout[empty[i]] = ''; // take back