Bei der Entwicklung des Browsergames Gomoku (5 in einer Reihe) in JavaScript sah ich mich mit der Notwendigkeit konfrontiert, einen Computergegner (AI) zu implementieren. Dieser Artikel beschreibt kurz die Hauptkomponenten von AI und vergleicht auch die Suchalgorithmen: NegaMax, NegaScout und MTD-F.
Die Hauptkomponenten der KI: eine Funktion zur Beurteilung des Spielzustands, ein Bewegungsgenerator, ein Suchalgorithmus, ein Algorithmus zur Bestimmung eines Sieges.
Algorithmus zur Bestimmung des Sieges
. . , , . , , .
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 , )
(Gute verwandte Artikel: 1 , 2 )