Created
March 16, 2023 15:19
-
-
Save sdkfz181tiger/6ef2d3b07c06dd3c986154debbabfd81 to your computer and use it in GitHub Desktop.
リバーシ4x4_AlphaBeta法
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
"use strict"; | |
//========== | |
// JavaScript | |
let canvas, ctx, rMng; | |
// Window | |
window.onload = (e)=>{ | |
// Canvas | |
canvas = document.getElementById("canvas"); | |
canvas.width = WIDTH; | |
canvas.height = HEIGHT; | |
// Context | |
ctx = canvas.getContext("2d"); | |
ctx.font = "18px Arial"; | |
ctx.textAlign = "center"; | |
ctx.strokeStyle = "#ffffff"; | |
ctx.lineWidth = 2; | |
// ReversiManager | |
const sX = WIDTH/2 - COLS*T_SIZE/2; | |
const sY = HEIGHT/2 - ROWS*T_SIZE/2; | |
rMng = new ReversiManager(sX, sY); | |
update();// Update | |
} | |
// Update | |
function update(){ | |
// Clear | |
ctx.fillStyle = "#333333"; | |
ctx.fillRect(0, 0, WIDTH, HEIGHT); | |
// ReversiManager | |
rMng.update(); | |
setTimeout(update, 400); | |
} | |
document.addEventListener("click", (e)=>{ | |
rMng.thinkPlayer(e.x, e.y);// Player | |
}); |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
"use strict"; | |
//========== | |
// Utility | |
const WIDTH = 320; | |
const HEIGHT = 320; | |
const ROWS = 4; | |
const COLS = 4; | |
const T_NONE = 0; | |
const T_WHITE = 1; | |
const T_BLACK = 2; | |
const T_SIZE = 30; | |
const T_DIRS = [[-1,-1],[-1,0],[-1,1],[0,-1],[0,1],[1,-1],[1,0],[1,1]]; | |
const T_DEPTH = 12; | |
const T_WAIT = 3000; | |
class ReversiManager{ | |
constructor(sX, sY){ | |
// Board | |
this._board = Array.from(new Array(ROWS), ()=>new Array(COLS).fill(0)); | |
this._board[ROWS/2-1][COLS/2-1] = T_WHITE;// 1, 1 | |
this._board[ROWS/2][COLS/2] = T_WHITE;// 2, 2 | |
this._board[ROWS/2][COLS/2-1] = T_BLACK;// 2, 1 | |
this._board[ROWS/2-1][COLS/2] = T_BLACK;// 1, 2 | |
// Turn | |
this._turn = T_WHITE;// First | |
this._you = (Math.random() < 0.5) ? T_WHITE:T_BLACK; | |
this._com = this.nextTurn(this._you); | |
// Message | |
this._msgTurn = ""; | |
this._msgResult = ""; | |
// Checker | |
this._bdManager = new BoardManager(sX, sY); | |
this._availables = this._bdManager.getAvailables(this._board, this._turn); | |
//this._bdManager.trace(this._board);// Trace | |
// Pass | |
this.checkPass(this._board, this._turn); | |
} | |
checkPass(board, turn){ | |
console.log("checkPass:", turn); | |
// Available | |
if(this._bdManager.isAvailable(board, turn)){ | |
if(turn != this._com) return; | |
setTimeout(()=>{// Timeout | |
this.thinkCom(board, this._turn, this._availables); | |
}, T_WAIT); | |
}else{ | |
if(this._bdManager.isFinished(board)){ | |
console.log("Finished!!"); | |
const result = this._bdManager.judgeBoard(board); | |
this._msgResult = "Result:"; | |
if(result == T_NONE){ | |
}else if(result == this._you){ | |
this._msgResult += "You win!!"; | |
}else if(result == this._com){ | |
this._msgResult += "You lose..."; | |
}else{ | |
this._msgResult += "Even..."; | |
} | |
console.log(this._msgResult); | |
return; | |
} | |
// Pass | |
console.log("Pass:", turn); | |
const nextTurn = this.nextTurn(turn); | |
const nextAvailables = this._bdManager.getAvailables(board, nextTurn); | |
this._turn = nextTurn; | |
this._availables = nextAvailables; | |
if(this._turn != this._com) return; | |
setTimeout(()=>{// Timeout | |
this.thinkCom(board, this._turn, this._availables); | |
}, T_WAIT); | |
} | |
} | |
thinkPlayer(x, y){ | |
if(this._turn != this._you) return; | |
const pos = this._bdManager.getRC(this._availables, x, y); | |
if(!pos) return; | |
console.log("thinkPlayer"); | |
const nextBoard = this._bdManager.putDisk(this._board, this._turn, pos.r, pos.c); | |
const nextTurn = this.nextTurn(this._turn); | |
const nextAvailables = this._bdManager.getAvailables(nextBoard, nextTurn); | |
// Change | |
this._board = nextBoard; | |
this._turn = nextTurn; | |
this._availables = nextAvailables; | |
//this._bdManager.trace(this._board); | |
// Pass | |
this.checkPass(this._board, this._turn); | |
} | |
thinkCom(board, turn, availables){ | |
if(turn != this._com) return; | |
console.log("thinkCom"); | |
let bestScore = Infinity * -1; | |
let choise = {r: -1, c: -1}; | |
for(let available of availables){ | |
const r = available[0]; | |
const c = available[1]; | |
const nextBoard = this._bdManager.putDisk(board, turn, r, c); | |
const nextTurn = this.nextTurn(turn); | |
const nextAvailables = this._bdManager.getAvailables(nextBoard, nextTurn); | |
// MinMax | |
const score = this.alphabeta(nextBoard, nextTurn, nextAvailables, 1, -Infinity, Infinity); | |
if(bestScore < score){ | |
bestScore = score; | |
choise.r = r; | |
choise.c = c; | |
} | |
} | |
console.log("Choise:", choise.r, choise.c, "Score:", bestScore); | |
const nextBoard = this._bdManager.putDisk(board, this._turn, choise.r, choise.c); | |
const nextTurn = this.nextTurn(this._turn); | |
const nextAvailables = this._bdManager.getAvailables(nextBoard, nextTurn); | |
// Change | |
this._board = nextBoard; | |
this._turn = nextTurn; | |
this._availables = nextAvailables; | |
//this._bdManager.trace(this._board); | |
// Pass | |
this.checkPass(this._board, this._turn); | |
} | |
alphabeta(board, turn, availables, depth, alpha, beta){ | |
if(T_DEPTH < depth) return 0;// Strength | |
//console.log("alphabeta[" + turn + "]", "Depth:", depth); | |
// Not available | |
if(!this._bdManager.isAvailable(board, turn)){ | |
// Finished or Pass | |
if(!this._bdManager.isAvailable(board, this.nextTurn(turn))){ | |
// Finished | |
const result = this._bdManager.judgeBoard(board); | |
const score = 100 - depth;// Score | |
if(result == 0) return 0; | |
if(result == this._you) return -score; | |
if(result == this._com) return score; | |
}else{ | |
// Pass | |
const nextTurn = this.nextTurn(turn); | |
const nextAvailables = this._bdManager.getAvailables(board, nextTurn); | |
return this.alphabeta(board, nextTurn, nextAvailables, depth, alpha, beta); | |
} | |
} | |
// Com or You | |
if(turn == this._com){ | |
for(let available of availables){ | |
const r = available[0]; | |
const c = available[1]; | |
const nextBoard = this._bdManager.putDisk(board, turn, r, c); | |
const nextTurn = this.nextTurn(turn); | |
const nextAvailables = this._bdManager.getAvailables(nextBoard, nextTurn); | |
// MinMax | |
const score = this.alphabeta(nextBoard, nextTurn, nextAvailables, depth+1, alpha, beta); | |
alpha = Math.max(alpha, score);// Max | |
if(beta <= alpha) break;// Alpha cut!! | |
} | |
return alpha; | |
}else{ | |
for(let available of availables){ | |
const r = available[0]; | |
const c = available[1]; | |
const nextBoard = this._bdManager.putDisk(board, turn, r, c); | |
const nextTurn = this.nextTurn(turn); | |
const nextAvailables = this._bdManager.getAvailables(nextBoard, nextTurn); | |
// MinMax | |
const score = this.alphabeta(nextBoard, nextTurn, nextAvailables, depth+1, alpha, beta); | |
beta = Math.min(beta, score);// Min | |
if(beta <= alpha) break;// Beta cut!! | |
} | |
return beta; | |
} | |
} | |
nextTurn(turn){ | |
return (turn == T_WHITE) ? T_BLACK:T_WHITE; | |
} | |
update(){ | |
this._bdManager.drawBoard(this._board);// Board | |
this._bdManager.drawAvailables(this._availables, (this._turn==this._you));// Availables | |
this.drawMsg();// Message | |
} | |
drawMsg(){ | |
// Title | |
ctx.fillStyle = "white"; | |
ctx.textAlign = "center"; | |
ctx.font = "22px Arial"; | |
ctx.fillText("Reversi4x4", WIDTH/2, 28); | |
// Turn | |
this._msgTurn = (this._turn == this._you) ? "Turn:you":"Turn:com"; | |
ctx.textAlign = "left"; | |
ctx.font = "16px Arial"; | |
ctx.fillText(this._msgTurn, 24, HEIGHT - 20); | |
// Result | |
const msgResult = "Result:***"; | |
ctx.textAlign = "right"; | |
ctx.font = "16px Arial"; | |
ctx.fillText(this._msgResult, WIDTH-24, HEIGHT - 20); | |
} | |
} | |
class BoardManager{ | |
constructor(sX, sY){ | |
this._sX = sX; | |
this._sY = sY; | |
} | |
judgeBoard(board){ | |
let cntWhite = 0; | |
let cntBlack = 0; | |
for(let r=0; r<ROWS; r++){ | |
for(let c=0; c<COLS; c++){ | |
if(board[r][c] == T_WHITE) cntWhite++; | |
if(board[r][c] == T_BLACK) cntBlack++; | |
} | |
} | |
if(cntBlack < cntWhite) return T_WHITE;// White win | |
if(cntWhite < cntBlack) return T_BLACK;// Black win | |
return 0;// Even | |
} | |
isFinished(board){ | |
if(this.isAvailable(board, T_WHITE)) return false;// not finished | |
if(this.isAvailable(board, T_BLACK)) return false;// not finished | |
return true; | |
} | |
isAvailable(board, turn){ | |
return 0 < this.getAvailables(board, turn).length; | |
} | |
getAvailables(board, turn){ | |
const availables = []; | |
for(let r=0; r<ROWS; r++){ | |
for(let c=0; c<COLS; c++){ | |
if(board[r][c] != T_NONE) continue; | |
let flg = false; | |
for(let dir of T_DIRS){ | |
const cnt = this.checkDisk(board, turn, r, c, dir, 0); | |
if(cnt <= 0) continue; | |
flg = true; | |
} | |
if(flg) availables.push([r, c]);// Push | |
} | |
} | |
return availables; | |
} | |
putDisk(board, turn, r, c){ | |
if(r < 0 || c < 0) return board; | |
if(ROWS-1 < r || COLS-1 < c) return board; | |
// Copy | |
const nextBoard = JSON.parse(JSON.stringify(board)); | |
for(let r=0; r<ROWS; r++){ | |
for(let c=0; c<COLS; c++){ | |
nextBoard[r][c] = board[r][c]; | |
} | |
} | |
// Put | |
nextBoard[r][c] = turn; | |
for(let dir of T_DIRS){ | |
const cnt = this.checkDisk(nextBoard, turn, r, c, dir, 0); | |
if(cnt <= 0) continue; | |
for(let i=0; i<cnt; i++){ | |
const oR = r + dir[0] * (i+1); | |
const oC = c + dir[1] * (i+1); | |
nextBoard[oR][oC] = turn;// Turn | |
} | |
} | |
return nextBoard; | |
} | |
checkDisk(board, turn, r, c, dir, cnt){ | |
const oR = r + dir[0]; | |
const oC = c + dir[1]; | |
if(oR < 0 || ROWS-1<oR) return 0; | |
if(oC < 0 || COLS-1<oC) return 0; | |
const type = board[oR][oC]; | |
if(type == T_NONE) return 0; | |
if(type != turn){ | |
return this.checkDisk(board, turn, oR, oC, dir, cnt+1); | |
} | |
if(type == turn && 0 < cnt) return cnt; | |
return 0; | |
} | |
trace(board){ | |
// Trace | |
let str = "== Board ==\n"; | |
for(let r=0; r<ROWS; r++){ | |
str += "| "; | |
for(let c=0; c<COLS; c++) str += board[r][c] + " "; | |
str += "|\n"; | |
} | |
str += "==========="; | |
console.log(str); | |
} | |
getRC(availables, x, y){ | |
if(x < this._sX) return null; | |
if(y < this._sY) return null; | |
if(this._sX + COLS*T_SIZE < x) return null; | |
if(this._sY + ROWS*T_SIZE < y) return null; | |
const r = Math.floor((y-this._sY)/T_SIZE); | |
const c = Math.floor((x-this._sX)/T_SIZE); | |
for(let available of availables){ | |
if(available[0] != r) continue; | |
if(available[1] != c) continue; | |
return {r: r, c: c}; | |
} | |
return null; | |
} | |
drawBoard(board){ | |
// Board | |
for(let r=0; r<ROWS; r++){ | |
for(let c=0; c<COLS; c++){ | |
const x = this._sX + T_SIZE * c; | |
const y = this._sY + T_SIZE * r; | |
ctx.fillStyle = "#008800"; | |
ctx.fillRect(x, y, T_SIZE-2, T_SIZE-2); | |
if(board[r][c] == T_NONE) continue; | |
ctx.fillStyle = (board[r][c] == T_WHITE) ? "#ffffff":"#000000"; | |
ctx.beginPath(); | |
ctx.arc(x+T_SIZE/2, y+T_SIZE/2, T_SIZE/4, 0, Math.PI*2, false); | |
ctx.fill(); | |
ctx.closePath(); | |
} | |
} | |
} | |
drawAvailables(availables, flg){ | |
// Availables | |
for(let available of availables){ | |
const x = this._sX + T_SIZE * available[1]; | |
const y = this._sY + T_SIZE * available[0]; | |
ctx.fillStyle = (flg) ? "#dddd00":"#99cc99"; | |
ctx.fillRect(x, y, T_SIZE-2, T_SIZE-2); | |
} | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
<!DOCTYPE html> | |
<html> | |
<head> | |
<meta charset="UTF-8"> | |
<link rel="shortcut icon" href="./images/favicon.ico"> | |
<!-- Stylesheet --> | |
<link href="./css/custom.css" rel="stylesheet" type="text/css"/> | |
<!-- JavaScript --> | |
<script src="./js/custom_utility.js" defer></script> | |
<script src="./js/custom_sketch.js" defer></script> | |
</head> | |
<body> | |
<canvas id="canvas"></canvas> | |
</body> | |
</html> |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment