I am creating a connect 4 negamax ai/engine in JavaScript and want to make it as fast as possible, that is search highest depth in shortest amount of time. Here is the current approach and implemented strategies:
- Using 2 32-bit bitboards for each player since JS don’t have 64 bit version and BigInt is slower:
this.bitboards = { 1: [0, 0], 2: [0, 0] }; // Bottom 32 bits, top 10 bits.
- Negamax engine to recursively go through moves.
- Alpha/beta pruning.
- Ordered moves according to immediate wins first and then as close as center as second sorting.
- Transposition table with Zobrist Hash to not search already searched positions.
- Evaluation is just checking for wins, all other scores are 0
I let it run over night and it solved the game (depth 42) in around 8 hours. Benchmarking is done according to Pascal Pons blog using “Test_L2_R1” and result is like this at my current state:
Total cases: 1 000
Total nodes evaluated: 76 571 560
Average nodes per case: 76 572
Total time: 00:00:40.299
Average time per case: 00:00:00.040
Nodes per second: 1 900 086
Nodes per second is somewhere between 2 and 4 million depending on my computers current state. I think this is decent for JS but my main concern is that I get around 10-100 times more nodes searched than the blog with the same strategies implemented.
What I tried to make it faster or search deeper
- Implement killer moves or history moves for better move ordering but it gives more explored nodes which tells me it is not a good strategy for connect 4.
- Better evaluation with e.g. 3 in a row but this is too slow and doesn’t seem to improve pruning that much either.
- Using BigInt for board representation but that slowed the nodes/second down.
Question
How can I make a JS connect 4 engine reach high depths in a shorter amount of time? What strategies could work other than what I tried?
Reference
Here is my ai code for reference:
import { COLS, ROWS } from '../utils/constants.js';
let tt;
const boardSize = COLS * ROWS;
const CENTER_ORDER = [3, 2, 4, 1, 5, 0, 6];
// TT flags semantics
const FLAG_EXACT = 1;
const FLAG_LOWER = 2; // lower bound: true score >= stored score
const FLAG_UPPER = 3; // upper bound: true score <= stored score
class TranspositionTable {
constructor(size = 1 << 24) {
this.size = size;
this.keys = new Uint32Array(size);
this.scores = new Int16Array(size);
this.depths = new Int8Array(size);
this.flags = new Uint8Array(size); // FLAG_EXACT, FLAG_LOWER, FLAG_UPPER
}
put(hash, score, depth, flag) {
const index = hash & (this.size - 1);
this.keys[index] = hash;
this.scores[index] = score;
this.depths[index] = depth;
this.flags[index] = flag;
}
get(hash, depth, alpha, beta) {
const index = hash & (this.size - 1);
if (this.keys[index] === hash && this.depths[index] >= depth) {
const score = this.scores[index];
const flag = this.flags[index];
if (flag === FLAG_EXACT) return { score, flag };
if (flag === FLAG_LOWER && score >= beta) return { score, flag };
if (flag === FLAG_UPPER && score <= alpha) return { score, flag };
}
return null;
}
}
// Move ordering
function getOrderedMoves(board) {
const moves = [];
const heights = board.colHeights;
// 2. Center-priority moves
for (const col of CENTER_ORDER) {
if (heights[col] >= ROWS) continue;
board.makeMove(col);
if (board.checkWin()) {
board.unmakeMove();
return [col]; // Immediate win
}
board.unmakeMove();
moves.push(col);
}
return moves;
}
// Negamax
export function negamax(board, depth, alpha, beta) {
let nodes = 1;
const originalAlpha = alpha;
const cached = tt.get(board.zobristHash, depth, alpha, beta);
if (cached) {
return { score: cached.score, nodes: 1, move: null };
}
// Terminal checks
if (board.checkWin()) {
return { score: Math.ceil(board.moveCount / 2) - 22, nodes, move: null };
} else if (board.moveCount >= boardSize || depth === 0) {
return { score: 0, nodes, move: null };
}
let bestScore = -100;
let bestMove = null;
let flag = FLAG_UPPER;
for (const col of getOrderedMoves(board)) {
board.makeMove(col);
const child = negamax(board, depth - 1, -beta, -alpha);
board.unmakeMove();
nodes += child.nodes;
const score = -child.score;
if (score >= beta) {
bestScore = score;
bestMove = col;
flag = FLAG_LOWER;
break;
}
if (score > bestScore) {
bestScore = score;
bestMove = col;
}
if (score > alpha) alpha = score;
}
if (bestScore <= originalAlpha) flag = FLAG_UPPER;
else if (bestScore >= beta) flag = FLAG_LOWER;
else flag = FLAG_EXACT;
tt.put(board.zobristHash, bestScore, depth, flag);
return { score: bestScore, nodes, move: bestMove };
}
// Entry point
export function findBestMove(board, depth) {
tt = new TranspositionTable();
const result = negamax(board, depth, -100, 100);
return { move: result.move, score: result.score, nodes: result.nodes };
}
