While developing the browser game Gomoku (5 in a row) in JavaScript, I was faced with the need to implement a computer adversary (AI). This article briefly describes the main components of AI, and also compares the search algorithms: NegaMax, NegaScout, and MTD-F.
The main components of AI: a function for assessing the state of the game, a generator of moves, a search algorithm, an algorithm for determining a victory.
Algorithm for determining victory
. . , , . , , .
function negamax(newBoard, player, depth, a, b, hash, restrictions, last_i, last_j) {
...
if (checkwin(newBoard, last_i, last_j)) {
return -2000000 + (MaximumDepth - depth) // , /
}
...
}
function checkwin(Board, x, y) {
const Directions = get_directions(Board, x, y)
for (let i = 0; i < 4; i++) { // 4
if (check_directions(Directions[i])) {
return true
}
}
}
function get_directions(Board, x, y) { //
const Directions = [[], [], [], []];
for (let i = -4; i < 5; i++) {
if (x + i >= 0 && x + i <= Rows - 1) {
Directions[0].push(Board[x + i][y])
if (y + i >= 0 && y + i <= Columns - 1) {
Directions[2].push(Board[x + i][y + i])
}
}
if (y + i >= 0 && y + i <= Columns - 1) {
Directions[1].push(Board[x][y + i])
if (x - i >= 0 && x - i <= Rows - 1) {
Directions[3].push(Board[x - i][y + i])
}
}
}
return Directions
}
, 5 4 .
function check_directions(arr) {
for (let i = 0; i < arr.length - 4; i++) {
if (arr[i] !== 0) {
if (arr[i] === arr[i + 1] && arr[i] === arr[i + 2] && arr[i] === arr[i + 3] && arr[i] === arr[i + 4]) {
return true
}
}
}
}
JS, . ( TypedArray, ).
1 - , -1 - .
(Transposition Table)
— . , . (Zobrist hashing).
Zobrist hashing
:
1. , N , N= * *
2. xor ,
– c , .
function Table_init() {
for (let i = 0; i < Rows; i++) {
Table[i] = [];
for (let j = 0; j < Columns; j++) {
Table[i][j] = []
Table[i][j][0] = random32(); //1
Table[i][j][1] = random32(); //2
}
}
function hash(board) { //
let h = 0;
let p;
for (let i = 0; i < Rows; i++) {
for (let j = 0; j < Columns; j++) {
const Board_value = board[i][j];
if (Board_value !== 0) { //
if (Board_value === -1) {
p = 0 // 0
} else {
p = 1 // 1
}
h = h ^ Table[i][j][p];
}
}
}
return h;
}
function update_hash(hash, player, row, col) { //
if (player === -1) {
player = 0
} else {
player = 1
}
hash = hash ^ Table[row][col][player];
return hash
}
function BoardGenerator(restrictions, Board, player) {
const availSpots_score = []; //c is j r is i;
const min_r = restrictions[0];
const min_c = restrictions[1];
const max_r = restrictions[2];
const max_c = restrictions[3];;
for (let i = min_r - 2; i <= max_r + 2; i++) {
for (let j = min_c - 2; j <= max_c + 2; j++) {
if (Board[i][j] === 0 && !remoteCell(Board, i, j)) {
const move = {}
move.i = i;
move.j = j;
move.score = evaluate_move(Board, i, j, player) // , score.
if (move.score === WIN_DETECTED) {
return [move]
}
availSpots_score.push(move)
}
}
}
availSpots_score.sort(compare) // score
// return availSpots_score.slice(0,10)
return availSpots_score;
}
:
1. ( )
2. ( )
3. , ( )
Move ordering
- , , . score , 4 : , , . score - score .
function evaluate_move(Board, x, y, player) {
let score = 0;
const Directions = get_directions(Board, x, y);
let temp_score;
for (let i = 0; i < 4; i++) {
temp_score = evaluate_direction(Directions[i], player);
if (temp_score === WIN_DETECTED) { // ,
return WIN_DETECTED
} else {
score += temp_score
}
}
return score;
}
function evaluate_direction(direction_arr, player) {
let score = 0;
for (let i = 0; (i + 4) < direction_arr.length; i++) {
let you = 0;
let enemy = 0;
for (let j = 0; j <= 4; j++) {
if (direction_arr[i + j] === player) {
you++
} else if (direction_arr[i + j] === -player) {
enemy++
}
}
score += evalff(get_seq(you, enemy));
if ((score >= 800000)) {
return WIN_DETECTED;
}
}
return score
}
function evalff(seq) {
switch (seq) {
case 0:
return 7;
case 1:
return 35;
case 2:
return 800;
case 3:
return 15000;
case 4:
return 800000;
case -1:
return 15;
case -2:
return 400;
case -3:
return 1800;
case -4:
return 100000;
case 17:
return 0;
}
}
function get_seq(y, e) {
if (y + e === 0) {
return 0;
}
if (y !== 0 && e === 0) {
return y
}
if (y === 0 && e !== 0) {
return -e
}
if (y !== 0 && e !== 0) {
return 17
}
}
, - , . - , . , , .
function evaluate_state(Board, player, hash, restrictions) {
const black_score = eval_board(Board, -1, restrictions);
const white_score = eval_board(Board, 1, restrictions);
let score = 0;
if (player == -1) {
score = (black_score - white_score);
} else {
score = (white_score - black_score);
}
StateCache.set(hash,score);
StateCachePuts++;
return score;
}
eval_board . score, (Live) (Dead) .
: _xx_ - , _oxx_ - .
const LiveOne = 10;
const DeadOne = 1;
const LiveTwo = 100;
const DeadTwo = 10;
const LiveThree = 1000;
const DeadThree = 100;
const LiveFour = 10000;
const DeadFour = 1000;
const Five = 100000;
Iterative Deepening
, . - N, N+2. ( 2, . ). (, , ), . , .
NegaMax, NegaScout, MTDF
, chessprogramming.org, . , .
Negamax -
, .
- - , . Best case - (
move ordering).
n b( ) = 40
(n) |
Minimax(Alpha-beta pruning worst case) |
Alpha-beta pruning(best case) |
0 |
1 |
1 |
|---|---|---|
1 |
40 |
40 |
2 |
1,600 |
79 |
3 |
64,000 |
1,639 |
4 |
2,560,000 |
3,199 |
5 |
102,400,000 |
65,569 |
6 |
4,096,000,000 |
127,999 |
7 |
163,840,000,000 |
2,623,999 |
8 |
6,553,600,000,000 |
5,119,999 |
NegaScout
NegaScout – --, . Deep Blue.
MTD-F
MTD(F) - , -. , NegaScout, ( , MTD-F NegaScout)
:
function MTDF(root : node_type; f : integer; d : integer) : integer;
g := f;
upperbound := +INFINITY;
lowerbound := -INFINITY;
repeat
if g == lowerbound then beta := g + 1 else beta := g;
g := AlphaBetaWithMemory(root, beta - 1, beta, d);
if g < beta then upperbound := g else lowerbound := g;
until lowerbound >= upperbound;
return g;
, .
// return availSpots_score.slice(0,10)
, Move ordering 10 , (.. , 10).
(=8)
MTD(f) 10 - 10 .
StateCache - .
(bo3) (60 s)
.
c Iterative Deepening.
1 – , 0.5 –
|
|
Negamax |
NegaScout |
MTD(f) |
MTD(f) 10 |
Negamax |
|
0:2 |
0:2 |
0:2 |
NegaScout |
2:0 |
|
1:2 |
0:2 |
MTD(f) |
2:0 |
2:1 |
|
0:2 |
MTD(f) 10 |
2:0 |
2:0 |
2:0 |
|
MTD(f) 10 1.5:0.5 NegaScout 10
mtdf(10)
|
, |
2 |
0.032 |
4 |
0.11 |
6 |
0.428 |
8 |
3.286 |
10 |
22.787 |
, . , 3-7 .
(js)
|
(MTD(f) 10 - ) |
|
|
2:0 (10s ) |
https://github.com/lihongxun945/gobang |
2:0 (10s ) |
https://logic-games.spb.ru/gomoku/ |
2:0 (10s ) |
https://ixjamesyoo.github.io/Gomoku/ |
2:0 (10s ) |
( , 10 )
( )
1d (, )
bitboards ( , js)
/Move ordering
, . , . , . ( )
, . . (+ , tensorflow.js )
(), ( ) javascript.
2 : MCTS - .
MCTS , . AlphaZero/MuZero , MCTS + NN , , , , NN.
ai(mtdf10, 21x21) - https://4battle.ru/play_offline
, , .
:
++ ( C++, js . C++ 2-2.5 , )
(Good Related Articles: 1 , 2 )