The working page is in GitHub.
Introduction
This time, I have two AI bots playing Connect Four against each other. The first AI bot uses Alpha-beta pruning, and the other one uses a Negamax with Alpha-beta pruning.
const ROWS = 6;
const COLUMNS = 7;
const MARGIN_RADIUS = 10;
const PROGRESS_BAR_HEIGHT = 15;
const O = 0;
const X = 1;
const EMPTY = -1;
const BOARD_FILL_STYLE = '#3879e0';
class ConnectFourHeuristicFunction {
static #TWO_BLOCKS_SCORE = 1.0;
static #THREE_BLOCKS_SCORE = 10.0;
static #MINIMIZING_PLAYER_VICTORY_SCORE = -10E6;
static #MAXIMIZING_PLAYER_VICTORY_SCORE = +10E6;
evaluate(state, depth) {
if (state.isWinningFor(X)) {
return ConnectFourHeuristicFunction.#MINIMIZING_PLAYER_VICTORY_SCORE - depth;
}
if (state.isWinningFor(O)) {
return ConnectFourHeuristicFunction.#MAXIMIZING_PLAYER_VICTORY_SCORE + depth;
}
return this.#evaluate2(state) +
this.#evaluate3(state);
}
#evaluate2(state) {
return this.#evaluate2Horizontal (state) +
this.#evaluate2Vertical (state) +
this.#evaluate2Ascending (state) +
this.#evaluate2Descending (state);
}
#evaluate3(state) {
return this.#evaluate3Horizontal (state) +
this.#evaluate3Vertical (state) +
this.#evaluate3Ascending (state) +
this.#evaluate3Descending (state);
}
#evaluate2Horizontal(state) {
let sum = 0.0;
for (let y = 0; y < ROWS; y++) {
for (let x = 0; x < COLUMNS - 1; x++) {
if (state.get(x, y) === O &&
state.get(x + 1, y) === O) {
sum += ConnectFourHeuristicFunction.#TWO_BLOCKS_SCORE;
} else if (state.get(x, y) === X &&
state.get(x + 1, y) === X) {
sum -= ConnectFourHeuristicFunction.#TWO_BLOCKS_SCORE;
}
}
}
return sum;
}
#evaluate2Vertical(state) {
let sum = 0.0;
for (let y = 0; y < ROWS - 1; y++) {
for (let x = 0; x < COLUMNS; x++) {
if (state.get(x, y) === O &&
state.get(x, y + 1) === O) {
sum += ConnectFourHeuristicFunction.#TWO_BLOCKS_SCORE;
} else if (state.get(x, y) === X &&
state.get(x, y + 1) === X) {
sum -= ConnectFourHeuristicFunction.#TWO_BLOCKS_SCORE;
}
}
}
return sum;
}
#evaluate2Ascending(state) {
let sum = 0.0;
for (let y = ROWS - 1; y > 0; y--) {
for (let x = 0; x < COLUMNS - 1; x++) {
if (state.get(x, y) === O &&
state.get(x + 1, y - 1) === O) {
sum += ConnectFourHeuristicFunction.#TWO_BLOCKS_SCORE;
} else if (state.get(x, y) === X &&
state.get(x + 1, y - 1) === X) {
sum -= ConnectFourHeuristicFunction.#TWO_BLOCKS_SCORE;
}
}
}
return sum;
}
#evaluate2Descending(state) {
let sum = 0.0;
for (let y = ROWS - 1; y > 0; y--) {
for (let x = 1; x < COLUMNS; x++) {
if (state.get(x, y) === O &&
state.get(x - 1, y - 1) === O) {
sum += ConnectFourHeuristicFunction.#TWO_BLOCKS_SCORE;
} else if (state.get(x, y) === X &&
state.get(x - 1, y - 1) === X) {
sum -= ConnectFourHeuristicFunction.#TWO_BLOCKS_SCORE;
}
}
}
return sum;
}
#evaluate3Horizontal(state) {
let sum = 0.0;
for (let y = 0; y < ROWS; y++) {
for (let x = 0; x < COLUMNS - 2; x++) {
if (state.get(x, y) === O &&
state.get(x + 1, y) === O &&
state.get(x + 2, y) === O) {
sum += ConnectFourHeuristicFunction.#THREE_BLOCKS_SCORE;
} else if (state.get(x, y) === X &&
state.get(x + 1, y) === X &&
state.get(x + 2, y) === X) {
sum -= ConnectFourHeuristicFunction.#THREE_BLOCKS_SCORE;
}
}
}
return sum;
}
#evaluate3Vertical(state) {
let sum = 0.0;
for (let y = 0; y < ROWS - 2; y++) {
for (let x = 0; x < COLUMNS; x++) {
if (state.get(x, y) === O &&
state.get(x, y + 1) === O &&
state.get(x, y + 2) === O) {
sum += ConnectFourHeuristicFunction.#THREE_BLOCKS_SCORE;
} else if (state.get(x, y) === X &&
state.get(x, y + 1) === X &&
state.get(x, y + 2) === X) {
sum -= ConnectFourHeuristicFunction.#THREE_BLOCKS_SCORE;
}
}
}
return sum;
}
#evaluate3Ascending(state) {
let sum = 0.0;
for (let y = ROWS - 1; y > 1; y--) {
for (let x = 0; x < COLUMNS - 2; x++) {
if (state.get(x, y) === O &&
state.get(x + 1, y - 1) === O &&
state.get(x + 2, y - 2) === O) {
sum += ConnectFourHeuristicFunction.#THREE_BLOCKS_SCORE;
} else if (state.get(x, y) === X &&
state.get(x + 1, y - 1) === X &&
state.get(x + 2, y - 2) === X) {
sum -= ConnectFourHeuristicFunction.#THREE_BLOCKS_SCORE;
}
}
}
return sum;
}
#evaluate3Descending(state) {
let sum = 0.0;
for (let y = ROWS - 1; y > 1; y--) {
for (let x = 2; x < COLUMNS; x++) {
if (state.get(x, y) === O &&
state.get(x - 1, y - 1) === O &&
state.get(x - 2, y - 2) === O) {
sum += ConnectFourHeuristicFunction.#THREE_BLOCKS_SCORE;
} else if (state.get(x, y) === X &&
state.get(x - 1, y - 1) === X &&
state.get(x - 2, y - 2) === X) {
sum -= ConnectFourHeuristicFunction.#THREE_BLOCKS_SCORE;
}
}
}
return sum;
}
}
class ConnectFourBoard {
static ROWS = 6;
static COLUMNS = 7;
static VICTORY_LENGTH = 4;
#boardData;
#getCellChar(cellCharacter) {
switch (cellCharacter) {
case X:
return "<span style='color: blue;'>X</span>";
case O:
return "<span style='color: red;'>O</span>";
case EMPTY:
return " ";
default:
throw "Should not get here.";
}
}
#getWinningCellChar(cellCharacter) {
switch (cellCharacter) {
case X:
return "<span style='color: white; background-color: black; font-weight: bold;'>X</span>";
case O:
return "<span style='color: white; background-color: black; font-weight: bold;'>O</span>";
case EMPTY:
return " ";
default:
throw "Should not get here.";
}
}
constructor(other) {
if (arguments.length === 1) {
this.#boardData = [...other.#boardData];
} else {
this.#boardData = Array(ConnectFourBoard.ROWS *
ConnectFourBoard.COLUMNS);
for (let i = 0, end = this.#boardData.length; i < end; i++) {
this.#boardData[i] = EMPTY;
}
}
}
expand() {
const children = new Array(ConnectFourBoard.COLUMNS);
for (let x = 0; x < COLUMNS; x++) {
if (makePly(x)) {
const child = new ConnectFourBoard(this);
children.push(child);
unmakePly(x);
}
}
return children;
}
get(x, y) {
return this.#boardData[y * ConnectFourBoard.COLUMNS + x];
}
set(x, y, playerType) {
this.#boardData[y * ConnectFourBoard.COLUMNS + x] = playerType;
}
toString() {
let str = "";
const winningPattern = this.getWinningPattern();
function isInWinningPattern(winningPattern, x, y) {
if (winningPattern === null) {
return false;
}
for (const p of winningPattern) {
if (p.x === x && p.y === y) {
return true;
}
}
return false;
}
for (let y = 0; y < ConnectFourBoard.ROWS; y++) {
for (let x = 0; x < ConnectFourBoard.COLUMNS; x++) {
str += "|";
const belongsToWinningPattern =
isInWinningPattern(winningPattern, x, y);
if (belongsToWinningPattern === false) {
str += this.#getCellChar(this.get(x, y));
} else {
str += this.#getWinningCellChar(this.get(x, y));
}
}
str += "|<br/>";
}
str += "+-+-+-+-+-+-+-+<br/>";
str += " 1 2 3 4 5 6 7";
return str;
}
isTie() {
for (let x = 0; x < COLUMNS; x++) {
if (this.get(x, 0) === EMPTY) {
return false;
}
}
return true;
}
makePly(x, playerType) {
for (let y = ROWS - 1; y >= 0; y--) {
if (this.get(x, y) === EMPTY) {
this.set(x, y, playerType);
return true;
}
}
return false;
}
unmakePly(x) {
for (let y = 0; y < ROWS; y++) {
if (this.get(x, y) !== EMPTY) {
this.set(x, y, EMPTY);
return;
}
}
}
isTerminal() {
return this.isWinningFor(O) ||
this.isWinningFor(X) ||
this.isTie();
}
getWinningPattern() {
if (!this.isWinningFor(X) &&
!this.isWinningFor(O)) {
return null;
}
let winningPattern = null;
for (let length = ROWS;
length >= ConnectFourBoard.VICTORY_LENGTH;
length--) {
// Try load the vertical winning pattern:
winningPattern =
this.tryLoadVerticalWinningPattern(X, length);
if (winningPattern !== null) {
return winningPattern;
}
winningPattern =
this.tryLoadVerticalWinningPattern(O, length);
if (winningPattern !== null) {
return winningPattern;
}
// Try to load the ascending winning pattern:
winningPattern =
this.tryLoadAscendingWinningPattern(X, length);
if (winningPattern !== null) {
return winningPattern;
}
winningPattern =
this.tryLoadAscendingWinningPattern(O, length);
if (winningPattern !== null) {
return winningPattern;
}
// Try to load the descending winning pattern:
winningPattern =
this.tryLoadDescendingWinningPattern(X, length);
if (winningPattern !== null) {
return winningPattern;
}
winningPattern =
this.tryLoadDescendingWinningPattern(O, length);
if (winningPattern !== null) {
return winningPattern;
}
}
for (let length = COLUMNS; length >= ConnectFourBoard.VICTORY_LENGTH; length--) {
winningPattern =
this.tryLoadHorizontalWinningPattern(X, length);
if (winningPattern !== null) {
return winningPattern;
}
winningPattern =
this.tryLoadHorizontalWinningPattern(O, length);
if (winningPattern !== null) {
return winningPattern;
}
}
throw "Should not get here.";
}
hasHorizontalStreak(playerType, length) {
const lastX = COLUMNS - length;
for (let y = ROWS - 1; y >= 0; y--) {
horizontalCheck:
for (let x = 0; x <= lastX; x++) {
for (let i = 0; i < length; i++) {
if (this.get(x + i, y) !== playerType) {
continue horizontalCheck;
}
}
return true;
}
}
return false;
}
hasVerticalStreak(playerType, length) {
const lastY = ROWS - length;
for (let x = 0; x < COLUMNS; x++) {
verticalCheck:
for (let y = 0; y <= lastY; y++) {
for (let i = 0; i < length; i++) {
if (this.get(x, y + i) !== playerType) {
continue verticalCheck;
}
}
return true;
}
}
return false;
}
hasAscendingDiagonalStreak(playerType, length) {
const lastX = COLUMNS - length;
const lastY = length - 1;
for (let y = ROWS - 1; y >= lastY; y--) {
diagonalCheck:
for (let x = 0; x <= lastX; x++) {
for (let i = 0; i < length; i++) {
if (this.get(x + i, y - i) !== playerType) {
continue diagonalCheck;
}
}
return true;
}
}
return false;
}
hasDescendingDiagonalStreak(playerType, length) {
const firstX = length - 1;
const lastY = length - 1;
for (let y = ROWS - 1; y >= lastY; y--) {
diagonalCheck:
for (let x = firstX; x < COLUMNS; x++) {
for (let i = 0; i < length; i++) {
if (this.get(x - i, y - i) !== playerType) {
continue diagonalCheck;
}
}
return true;
}
}
return false;
}
isWinningFor(playerType) {
return this.hasAscendingDiagonalStreak (playerType, ConnectFourBoard.VICTORY_LENGTH) ||
this.hasDescendingDiagonalStreak (playerType, ConnectFourBoard.VICTORY_LENGTH) ||
this.hasHorizontalStreak (playerType, ConnectFourBoard.VICTORY_LENGTH) ||
this.hasVerticalStreak (playerType, ConnectFourBoard.VICTORY_LENGTH);
}
tryLoadAscendingWinningPattern(playerType, length) {
const lastX = COLUMNS - length;
const lastY = length - 1;
let winningPattern = [];
for (let y = ROWS - 1; y >= lastY; y--) {
diagonalCheck:
for (let x = 0; x <= lastX; x++) {
for (let i = 0; i < length; i++) {
if (this.get(x + i, y - i) === playerType) {
winningPattern.push({x: x + i, y: y - i});
if (winningPattern.length === length) {
return winningPattern;
}
} else {
winningPattern = [];
continue diagonalCheck;
}
}
}
}
return null;
}
tryLoadDescendingWinningPattern(playerType, length) {
const firstX = length - 1;
const lastY = ROWS - length;
let winningPattern = [];
for (let y = ROWS - 1; y > lastY; y--) {
diagonalCheck:
for (let x = firstX; x < COLUMNS; x++) {
for (let i = 0; i < length; i++) {
if (this.get(x - i, y - i) === playerType) {
winningPattern.push({x: x - i, y: y - i});
if (winningPattern.length === length) {
return winningPattern;
}
} else {
winningPattern = [];
continue diagonalCheck;
}
}
}
}
return null;
}
tryLoadHorizontalWinningPattern(playerType, length) {
const lastX = COLUMNS - length;
let winningPattern = [];
for (let y = ROWS - 1; y >= 0; y--) {
horizontalCheck:
for (let x = 0; x <= lastX; x++) {
for (let i = 0; i < length; i++) {
if (this.get(x + i, y) === playerType) {
winningPattern.push({x: x + i, y: y});
if (winningPattern.length === length) {
return winningPattern;
}
} else {
winningPattern = [];
continue horizontalCheck;
}
}
}
}
return null;
}
tryLoadVerticalWinningPattern(playerType, length) {
const lastY = ROWS - length;
let winningPattern = [];
for (let x = 0; x < COLUMNS; x++) {
verticalCheck:
for (let y = 0; y <= lastY; y++) {
for (let i = 0; i < length; i++) {
if (this.get(x, y + i) === playerType) {
winningPattern.push({x: x, y: y + i});
if (winningPattern.length === length) {
return winningPattern;
}
} else {
winningPattern = [];
continue verticalCheck;
}
}
}
}
return null;
}
};
class ConnectFourAlphaBetaPruningSearchEngine {
#bestMoveState;
#heuristicFunction;
constructor(heuristicFunction) {
this.#heuristicFunction = heuristicFunction;
}
search(root, depth, playerType = O) {
this.#bestMoveState = null;
this.#alphaBetaPruningRootImpl(root,
depth,
playerType);
return this.#bestMoveState;
}
#alphaBetaPruningRootImpl(root, depth, playerType) {
if (playerType === O) {
// Try to maximize the value:
let alpha = Number.NEGATIVE_INFINITY;
let value = Number.NEGATIVE_INFINITY;
let tentativeValue = Number.NEGATIVE_INFINITY;
for (let x = 0; x < ConnectFourBoard.COLUMNS; x++) {
if (!root.makePly(x, O)) {
continue;
}
value = Math.max(value,
this.#alphaBetaPruningImpl(
root,
depth - 1,
alpha,
Number.POSITIVE_INFINITY,
X));
if (tentativeValue < value) {
tentativeValue = value;
this.#bestMoveState = new ConnectFourBoard(root);
}
root.unmakePly(x);
alpha = Math.max(alpha, value);
}
} else {
let beta = Number.POSITIVE_INFINITY;
let value = Number.POSITIVE_INFINITY;
let tentativeValue = Number.POSITIVE_INFINITY;
for (let x = 0; x < ConnectFourBoard.COLUMNS; x++) {
if (!root.makePly(x, X)) {
continue;
}
value = Math.min(value,
this.#alphaBetaPruningImpl(
root,
depth - 1,
Number.NEGATIVE_INFINITY,
beta,
O));
if (tentativeValue > value) {
tentativeValue = value;
this.#bestMoveState = new ConnectFourBoard(root);
}
root.unmakePly(x);
beta = Math.min(beta, value);
}
}
}
#alphaBetaPruningImpl(state,
depth,
alpha,
beta,
playerType) {
if (depth === 0 || state.isTerminal()) {
return heuristicFunction.evaluate(state, depth);
}
if (playerType === O) {
let value = Number.NEGATIVE_INFINITY;
for (let x = 0; x < ConnectFourBoard.COLUMNS; x++) {
if (!state.makePly(x, O)) {
continue;
}
value = Math.max(value,
this.#alphaBetaPruningImpl(state,
depth - 1,
alpha,
beta,
X));
state.unmakePly(x);
if (value > beta) {
break;
}
alpha = Math.max(alpha, value);
}
return value;
} else {
let value = Number.POSITIVE_INFINITY;
for (let x = 0; x < ConnectFourBoard.COLUMNS; x++) {
if (!state.makePly(x, X)) {
continue;
}
value = Math.min(value,
this.#alphaBetaPruningImpl(state,
depth - 1,
alpha,
beta,
O));
state.unmakePly(x);
if (value < alpha) {
break;
}
beta = Math.min(beta, value);
}
return value;
}
}
}
class ConnectFourNegamaxSearchEngine {
#heuristicFunction;
constructor(heuristicFunction) {
this.#heuristicFunction = heuristicFunction;
}
search(root, depth, playerType = O) {
if (playerType === O) {
return this.#negamaxRoot(root,
depth,
Number.NEGATIVE_INFINITY,
Number.POSITIVE_INFINITY,
+1);
} else {
return this.#negamaxRoot(root,
depth,
Number.NEGATIVE_INFINITY,
Number.POSITIVE_INFINITY,
-1);
}
}
#negamaxRoot(root,
depth,
alpha,
beta,
color) {
let value = Number.NEGATIVE_INFINITY;
let bestMoveState = null;
for (let x = 0; x < COLUMNS; x++) {
if (!root.makePly(x, color === 1 ? O : X)) {
continue;
}
const score =
-this.#negamax(root,
depth - 1,
-beta,
-alpha,
-color);
if (color === +1) {
if (value < score) {
value = score;
bestMoveState = new ConnectFourBoard(root);
}
} else {
if (value > score) {
value = score;
bestMoveState = new ConnectFourBoard(root);
}
}
root.unmakePly(x);
alpha = Math.max(alpha, value);
if (alpha >= beta) {
break;
}
}
return bestMoveState;
}
#negamax(root,
depth,
alpha,
beta,
color) {
if (depth === 0 || root.isTerminal()) {
return color * this.#heuristicFunction.evaluate(root, depth);
}
let value = Number.NEGATIVE_INFINITY;
for (let x = 0; x < COLUMNS; x++) {
if (!root.makePly(x, color === 1 ? O : X)) {
continue;
}
value = Math.max(
value,
-this.#negamax(root,
depth - 1,
-beta,
-alpha,
-color));
root.unmakePly(x);
alpha = Math.max(alpha, value);
if (alpha >= beta) {
break;
}
}
return value;
}
}#output-text-div {
font-family: monospace;
font-size: 15pt;
}<!DOCTYPE html>
<html>
<head>
<title>AI vs. AI playing Connect 4</title>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<link rel='stylesheet' type="text/css" href='css/connect4.css' />
</head>
<body>
<div id='output-text-div'></div>
<script src='js/connect4ai.js'></script>
<script>
function flipTurn(playerTurn) {
switch (playerTurn) {
case X:
return O;
case O:
return X;
default:
throw "Should not get here.";
}
}
const output = document.getElementById('output-text-div');
const heuristicFunction = new ConnectFourHeuristicFunction();
const engineX = new ConnectFourAlphaBetaPruningSearchEngine(
heuristicFunction);
const engineO = new ConnectFourNegamaxSearchEngine(
heuristicFunction);
const depth = 8;
let turnNumber = 1;
function getTurnNumberString() {
if (turnNumber % 10 === 1) {
return turnNumber + "st";
}
if (turnNumber % 10 === 2) {
return turnNumber + "nd";
}
if (turnNumber % 10 === 3) {
return turnNumber + "rd";
}
return turnNumber + "th";
}
let engine = engineX;
let state = new ConnectFourBoard();
output.innerHTML += state.toString() + "<br/>";
function millis() {
return new Date().valueOf();
}
let totalDurationX = 0;
let totalDurationO = 0;
let turn = X;
function getEngineName(engine) {
if (engine === engineX) {
return "Alpha-beta pruning engine (X)";
}
if (engine === engineO) {
return "Negamax engine (O)";
}
throw "Should not get here.";
}
function gameLoop() {
setTimeout(() => {
let ta = millis();
state = engine.search(state, depth, turn);
let tb = millis();
if (turn === X) {
totalDurationX += tb - ta;
} else {
totalDurationO += tb - ta;
}
output.innerHTML += state.toString();
output.innerHTML += "<br/>";
output.innerHTML +=
turn === X ?
getEngineName(engine)
+ " made the "
+ getTurnNumberString()
+ " turn, duration: "
+ (tb - ta)
+ " milliseconds.<br/>"
:
getEngineName(engine)
+ " made the "
+ getTurnNumberString()
+ " turn, duration: "
+ (tb - ta)
+ " milliseconds.<br/>";
turnNumber++;
if (state.isTie()) {
output.innerHTML += "RESULT: It's a tie.<br/>";
return;
}
if (turn === X) {
if (state.isWinningFor(X)) {
output.innerHTML += "RESULT: X won.<br/>";
output.innerHTML += "X AI total duration: " + totalDurationX + " milliseconds.<br/>";
output.innerHTML += "O AI total duration: " + totalDurationO + " milliseconds.<br/>";
window.scrollTo(0, document.body.scrollHeight);
return;
}
} else {
if (state.isWinningFor(O)) {
output.innerHTML += "RESULT: O won.<br/>";
output.innerHTML += "X AI total duration: " + totalDurationX + " milliseconds.<br/>";
output.innerHTML += "O AI total duration: " + totalDurationO + " milliseconds.<br/>";
window.scrollTo(0, document.body.scrollHeight);
return;
}
}
function flipEngine(engine) {
if (engine === engineX) {
return engineO;
}
if (engine === engineO) {
return engineX;
}
throw "Should not get here.";
}
turn = flipTurn(turn);
engine = flipEngine(engine);
if (!state.isTerminal()) {
// Run the next frame:
window.scrollTo(0, document.body.scrollHeight);
requestAnimationFrame(gameLoop);
} else {
}
}, 0);
}
gameLoop();
</script>
</body>
</html>Critique request
- First of all, I would like to receive general comments on my work.
- Also, I need your help to make my code snippets runnable from this very page so that people would not have to copy/save the files in order to run the actual battle.
if (makePly(x)) {in functionConnectFourBoard .expand()will throw an error, should be (my guess)if (this.makePly(x)) {. Please ensure that the code is working. \$\endgroup\$