I made a TicTacToe game with minmax with alpha-beta optimization in Python, that can be played in a shell. Then I made the game in Javascript with React-native. The alpha-beta algo that I tried to translate from python to javascript doesnt work well : the result given is right but optimization doesnt work. I have counted when the function is called Python : 23825 for vanilla minmax and ~3000 for alpha-beta ; Javascript always 23825. The Javascript code is for react-native application but the code is not a react-native component, only a js class .
I can't made console.log() in js alpha-beta, its make the App crash
Python
def alphabeta(self, depth, maxDepth, grid, alpha, beta):
self.count += 1
maxPlayer = True if depth % 2 == 0 else False
if self.finish(grid) or depth == maxDepth:
return self.eval(grid)
if depth == 0:
res = {}
for m in self.getPossibleMoves(grid):
grid[m] = self.ia
res[m] = self.alphabeta(depth+1, maxDepth, grid, alpha, beta)
grid[m] = self.empty
max_val = max(res.values())
li_max = [a for a in res.items() if a[1] == max_val]
return li_max[randint(0, len(li_max) -1)]
else:
if maxPlayer:
v = -10
for m in self.getPossibleMoves(grid):
grid[m] = self.ia
v = max(v, self.alphabeta(depth+1, maxDepth, grid, alpha, beta))
grid[m] = self.empty
if v >= beta:
return v
alpha = max(alpha, v)
else:
v = 10
for m in self.getPossibleMoves(grid):
grid[m] = self.player
v = min(v, self.alphabeta(depth+1, maxDepth, grid, alpha, beta))
grid[m] = self.empty
if alpha >= v:
return v
beta = min(beta, v)
return v
JS
alpha2(depth, maxDepth, grid, alpha, beta) {
this.count += 1
let maxPlayer = (depth % 2 == 0) ? true : false
if (this.finish(grid) || depth == maxDepth) {
return this.eval(grid)
}
if (depth == 0) {
let res = {}
this.getPossibleMoves(grid).forEach(m => {
grid[m] = this.ia
res[m] = this.alpha2(depth + 1, maxDepth, grid, alpha, beta)
grid[m] = this.empty
})
let max_value = Math.max(...Object.values(res))
let li_max = Object.entries(res).filter(e => e[1] == max_value)
let choice = li_max[Math.floor(Math.random() * li_max.length)][0]
return choice
} else {
let v
if (maxPlayer) {
v = -10
this.getPossibleMoves(grid).forEach(m => {
grid[m] = this.ia
v = Math.max(v, this.alpha2(depth + 1, maxDepth, grid, alpha, beta))
grid[m] = this.empty
if (v >= beta) {
return v
}
alpha = Math.max(alpha, v)
})
} else {
v = 10
this.getPossibleMoves(grid).forEach(m => {
grid[m] = this.player
v = Math.min(v, this.alpha2(depth + 1, maxDepth, grid, alpha, beta))
grid[m] = this.empty
if (alpha >= v) {
return v
}
beta = Math.min(beta, v)
});
}
return v
}
}
