К сожалению нет компа под рукой.
Не могу проверить для Делфи.
Посетила такая мысль.
Если спуститься на глубину 6 только строго по одной ветви в каждом дочернем узле, начиная с корневого узла.
Затем сравнить результаты.
Достаточно в исходный код добавить только одну строку, чтобы проверить идею
if (depth!=1) return;
long nodes;
// perft driver
static inline void perft_driver(int depth)
{
// reccursion escape condition
if (depth == 0)
{
// increment nodes count (count reached positions)
nodes++;
return;
}
// create move list instance
moves move_list[1];
// generate moves
generate_moves(move_list);
// loop over generated moves
for (int move_count = 0; move_count < move_list->count; move_count++)
{
// preserve board state
copy_board();
// make move
if (!make_move(move_list->moves[move_count], all_moves))
// skip to the next move
continue;
// call perft driver recursively
perft_driver(depth - 1);
// take back
take_back();
if (depth!=1) return;
}
}
Warning: Spoiler![ Click to expand ][ Click to hide ]
Искусственный интеллект рулит!
Сегодня узнал, что в Яндекс браузер встроен перевод видео.
Можно смотреть Ютуб с озвучкой на русском языке и не заморачиваться с этим)))
Warning: Spoiler![ Click to expand ][ Click to hide ]
Warning: Spoiler![ Click to expand ][ Click to hide ]
// generate king attacks
function mask_king_attacks(square:TBoard_squares):U64;
var
attacks,bitboard:U64;
begin
// result attacks bitboard
attacks := 0;
// piece bitboard
bitboard := 0;
// set piece on board
set_bit(bitboard, square);
// generate king attacks
if (bitboard shr 8)>0 then attacks:=attacks or (bitboard shr 8);
if ((bitboard shr 9) and not_h_file)>0 then attacks:=attacks or (bitboard shr 9);
if ((bitboard shr 1) and not_h_file)>0 then attacks:=attacks or (bitboard shr 1);
if ((bitboard shr 7) and not_a_file)>0 then attacks:=attacks or (bitboard shr 7);
if (bitboard shl 8)>0 then attacks:=attacks or (bitboard shl 8);
if ((bitboard shl 9) and not_a_file)>0 then attacks:=attacks or (bitboard shl 9);
if ((bitboard shl 1) and not_a_file)>0 then attacks:=attacks or (bitboard shl 1);
if ((bitboard shl 7) and not_h_file)>0 then attacks:=attacks or (bitboard shl 7);
// return attack map
mask_king_attacks:=attacks;
end;
Собака зарыта скорее всео здесь
bitboard shl 8
Самый старший бит должен быть установлен в 1, но он этого не происходит.
Может ли это гдето вылезти еще, большой вопрос.
Уроки
44.Bitboard CHESS ENGINE in C: connecting to the GUI (parse move string)
45.Bitboard CHESS ENGINE in C: connecting to the GUI (parse "position" command)
46.Bitboard CHESS ENGINE in C: connecting to the GUI (parse "go" command)
47.Bitboard CHESS ENGINE in C: connecting to the GUI (main loop) + BONUS (TSCP vs BBC blitz game).
Warning: Spoiler![ Click to expand ][ Click to hide ]
Удалось подключиться по протоколу UCI.
К Arena Chess GUI 1.1 и к WinBoard-4.8.0
Warning: Spoiler![ Click to expand ][ Click to hide ]
{/**********************************\
==================================
UCI
==================================
\**********************************/}
// parse user/GUI move string input (e.g. "e7e8q")
function parse_move(move_string:string):integer;
var
source_square,target_square:byte;
j,moveInt:integer;
promoted_piece:char;
begin
// parse source square
source_square:=(ord(move_string[1])-ord('a')) + (8 - (ord(move_string[2]) - ord('0'))) * 8;
// parse target square
target_square:=(ord(move_string[3])-ord('a')) + (8 - (ord(move_string[4]) - ord('0'))) * 8;
// create move list instance
New(add_move);
// generate moves
generate_moves();
// loop over the moves within a move list
for j := 0 to add_move.count-1 do begin
// init move
moveInt:=add_move.move[j];
result:=moveInt;
// make sure source & target squares are available within the generated move
if ((source_square=get_source(moveInt,get_move_source)) and (target_square=get_source(moveInt,get_move_target))) then begin
// init promoted piece
promoted_piece := promoted_pieces[get_source(moveInt,get_move_promoted)];
if (( length(move_string)>4) and (promoted_piece<>'')) then begin
// promoted to queen
if (((move_string[5] = 'Q') or (move_string[5] = 'q')) and (promoted_piece = 'q')) then begin
// return legal move
//Writeln('promoted to queen');
exit;
end else
// promoted to rook
if (((move_string[5] = 'R') or (move_string[5] = 'r')) and (promoted_piece = 'r')) then begin
// return legal move
//Writeln('promoted to rook');
exit;
end else
// promoted to bishop
if (((move_string[5] = 'B') or (move_string[5] = 'b')) and (promoted_piece = 'b')) then begin
// return legal move
//Writeln('promoted to bishop');
exit;
end else
// promoted to knight
if (((move_string[5] = 'N') or (move_string[5] = 'n')) and (promoted_piece = 'n')) then begin
// return legal move
//Writeln('promoted to knight');
exit;
end else
// continue the loop on possible wrong promotions (e.g. "e7e8f")
continue;
end;
// return legal move
//Writeln('return legal move');
exit;
end;
end;//for
// return illegal move
// Writeln('return illegal move');
result:=0;
end;
Warning: Spoiler![ Click to expand ][ Click to hide ]
{/*
Example UCI commands to init position on chess board
// init start position
position startpos
// init start position and make the moves on chess board
position startpos moves e2e4 e7e5
// init position from FEN string
position fen r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq - 0 1
// init position from fen string and make moves on chess board
position fen r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq - 0 1 moves e2a6 e8g8
*/ }
// parse UCI "position" command
procedure parse_position(commandUCI:string);
var
startpos:string;
fen_str,moves_str,moves_make:string;
pos_fen,pos_moves,legal_parse_move:integer;
begin
startpos:='rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1';
pos_moves:=pos('moves',commandUCI);
pos_fen:=pos('fen',commandUCI);
// parse UCI "startpos" command
if pos('startpos',commandUCI)>0 then
// init chess board with start position
parse_fen(startpos)
// parse UCI "fen" command
else begin
// if no "fen" command is available within command string
if pos_fen=0 then parse_fen(startpos)
// found "fen" substring
else begin
// init chess board with position from FEN string
if pos_moves>0 then fen_str:=copy(commandUCI,pos_fen+4,pos_moves-pos_fen-4)
else fen_str:=copy(commandUCI,pos_fen+4,length(commandUCI)-pos_fen-1);
//Writeln('fen_str=',fen_str);
if parse_fen(fen_str)=false then Writeln('Ошибка FEN строки ...');
end;
end;//if pos('startpos'
// parse moves after position
// moves available
if pos_moves>0 then begin
moves_str:=copy(commandUCI,pos_moves+6,length(commandUCI)-pos_moves-1);
//Trim — удаление пробелов в начале строки и в конце
moves_str:=Trim(moves_str)+' ';
//Writeln('moves_str=',moves_str);
while pos(' ',moves_str)>0 do begin
moves_make:=copy(moves_str,1,pos(' ',moves_str)-1);
if length(moves_make)<4 then break;
//Writeln(moves_make);
legal_parse_move:=parse_move(moves_make);
if (legal_parse_move>0) then begin
// make it on board
make_move(legal_parse_move, all_moves);
//print_board();
end else begin
Writeln('return illegal move');
end;
moves_str:=copy(moves_str,pos(moves_make,moves_str)+length(moves_make)+1,length(moves_str)-length(moves_make));
//Writeln(moves_str);
end;
end;
print_board();
end;
Warning: Spoiler![ Click to expand ][ Click to hide ]
{/*
Example UCI commands to make engine search for the best move
// fixed depth search
go depth 64
*/ }
// parse UCI "go" command
procedure parse_go(commandUCI:string);
var
depth:integer;
depth_str:string;
pos_depth:integer;
begin
depth:=-1;
pos_depth:=pos('depth',commandUCI);
// handle fixed depth search
if pos_depth>0 then begin
depth_str:=copy(commandUCI,pos_depth+6,length(commandUCI)-pos_depth-5);
depth:=StrToInt(Trim(depth_str));
end else depth:=6;
//Writeln('depth_str=',depth);
print_board();
Writeln('bestmove b7b6');
end;
Warning: Spoiler![ Click to expand ][ Click to hide ]
{/*
GUI -> isready
Engine -> readyok
GUI -> ucinewgame
*/}
// main UCI loop
procedure uci_loop();
var
Input_char:Array[0..2000] of char;
Input_str:widestring;
begin
Writeln('id name BBC_Alex');
Writeln('id name alexlaw');
Writeln('uciok');
// main loop
while true do begin
// reset user /GUI input
FillChar(Input_char, SizeOf(Input_char), 0);
FillChar(Input_str, SizeOf(Input_str), 0);
// make sure output reaches the GUI
Flush(Output);
Readln(Input_str);
if Input_str=#13#10 then continue else
// parse UCI "isready" command
if pos('isready',Input_str)>0 then begin
Writeln('readyok');
continue;
end else
// parse UCI "position" command
if pos('position',Input_str)>0 then begin
// call parse position function
parse_position(Input_str);
end else
// parse UCI "ucinewgame" command
if pos('ucinewgame',Input_str)>0 then begin
// call parse position function
parse_position('position startpos');
end else
// call parse go function
if pos('go',Input_str)>0 then begin
parse_go(Input_str);
end else
// parse UCI "quit" command
if pos('quit',Input_str)>0 then begin
// quit from the chess engine program execution
break;
end else
// parse UCI "uci" command
if pos('uci',Input_str)>0 then begin
// print engine info
Writeln('id name BBC_Alex');
Writeln('id name alexlaw');;
Writeln('uciok');
end;
end;
end;
Warning: Spoiler![ Click to expand ][ Click to hide ]
begin
//Переключение окна консоли на кодовую страницу CP1251 (Win-1251).
//Если после переключения русские буквы показываются неверно,
//следует открыть системное меню консольного окна - щелчком мыши в левом
//верхнем углу окна консоли. И выбрать:
//Свойства - закладка "Шрифт" - выбрать шрифт: "Lucida Console".
SetConsoleCP(1251);
SetConsoleOutputCP(1251);
// SetConsoleOutputCP(CP_UTF8);
// ==================================
// init all
init_all();
uci_loop();
exit;
//Writeln('Нажмите <ENTER>, чтобы выйти ...');
//Readln;
end.
Arena Engine Debug
Warning: Spoiler![ Click to expand ][ Click to hide ]
Arena 1.1
1516**
NewGame!!!
66781*1*
Starting engine 1 Bbc
66781*1*Configured Engine 1 Type: UCI
66922*1*Engine 1 dir: C:\Users\Àëåêñåé\Videos\bbc\bbc_delphi\UCI
66953*1*Engine 1 commandline: C:\Users\Àëåêñåé\Videos\bbc\bbc_delphi\UCI\bbc.exe
67219<1:id name BBC_Alex
67219<1:id name alexlaw
67219<1:uciok
67516>1:uci
67562<1:id name BBC_Alex
67562>1:isready
68094<1:id name alexlaw
68094<1:uciok
68094<1:readyok
68547*1*Start calc, move no: 1
68547>1:ucinewgame
68547>1:isready
68578<1:8 r n b q k b n r
68578<1:7 # # # # # # # #
68578<1:6 . . . . . . . .
68578<1:5 . . . . . . . .
68578<1:4 . . . . . . . .
68594<1:3 . . . . . . . .
68594<1:2 P P P P P P P P
68594<1:1 R N B Q K B N R
68594<1: a b c d e f g h
68594<1:side = white
68594<1:castle = KQkq
68609<1:enpassant = no
68609<1:readyok
68687>1:position startpos moves e2e4
68687>1:go wtime 300000 btime 300000 winc 0 binc 0
68687<1:8 r n b q k b n r
68703<1:7 # # # # # # # #
68703<1:6 . . . . . . . .
68703<1:5 . . . . . . . .
68703<1:4 . . . . P . . .
68703<1:3 . . . . . . . .
68703<1:2 P P P P . P P P
68703<1:1 R N B Q K B N R
68719<1: a b c d e f g h
68719<1:side = black
68719<1:castle = KQkq
68719<1:enpassant = e3
68719<1:depth 6
68719<1:bestmove b7b6
68719*1*Found move:b7-b6
На самом деле еще не все моменты освещены на данном этапе.
- шах, мат, пат
- троекратное повторение
- правило 50 ходов
Еще важный момент
Если на вход bbc поступает один из видов нелегетимных ходов (ход короля под шах),
bbc игнорирует этот ход (не делает его в makemove), но не сообщает, что это illegal move.
enum это именованные последовательные константы (для полей в данном случае)
mirror_score их и пользует.
Для чего зарезервировали 128 без контекста не понять
mirror_score[h8] это извращение. Так делать никогда нельзя. Весь смысл enum в том, чтобы конкретное значение константы было неважно.
Иначе будет memory corruption при случае
Но с данным enum h8 = 7 (a8 = 0 по умолчанию)
То бишь mirror_score[h8] вернет h1
Но потом не надо огорчаться, что при таком стиле кодинга все вдруг упадет.
==================================
\**********************************/}
// material scrore
{/*
пешка = 100 = p
конь = 300 = p * 3
слон = 350 = p * 3 + p * 0.5
ладья = 500 = p * 5
ферзь = 1000 = p * 10
король = 10000 = p * 100
*/}
var
material_score:array[0..11] of integer = (
Warning: Spoiler![ Click to expand ][ Click to hide ]
100, // white pawn score
300, // white knight scrore
350, // white bishop score
500, // white rook score
1000, // white queen score
10000, // white king score
-100, // black pawn score
-300, // black knight scrore
-350, // black bishop score
-500, // black rook score
-1000, // black queen score
-10000 // black king score
Warning: Spoiler![ Click to expand ][ Click to hide ]
function evaluate():integer;
var
score,int_piece:integer;
bb:U64;
bb_piece:Tencode_pieces;
bb_square:TBoard_squares;
begin
// static evaluation score
score:=0;
// loop over piece bitboards
for bb_piece := P_ to k do begin
// init piece bitboard copy
bb:=bitboards_12[bb_piece];
// loop over pieces within a bitboard
while bb>0 do begin
// init piece
int_piece:=integer(bb_piece);
// init square
bb_square := TBoard_squares(get_ls1b_index(bb));
score:=score + material_score[int_piece];
case bb_piece of
// evaluate white pieces
P_:score:=score + pawn_score[integer(bb_square)];
N_:score:=score + knight_score[integer(bb_square)];
B_:score:=score + bishop_score[integer(bb_square)];
R_:score:=score + rook_score[integer(bb_square)];
K_:score:=score + king_score[integer(bb_square)];
// evaluate black pieces
//integer(TBoard_squares(mirror_score[bb_square]))
p:score:=score - pawn_score[integer(TBoard_squares(mirror_score[bb_square]))];
n:score:=score - knight_score[integer(TBoard_squares(mirror_score[bb_square]))];
b:score:=score - bishop_score[integer(TBoard_squares(mirror_score[bb_square]))];
r:score:=score - rook_score[integer(TBoard_squares(mirror_score[bb_square]))];
k:score:=score - king_score[integer(TBoard_squares(mirror_score[bb_square]))];
end;//case
// pop ls1b
pop_bit(bb, bb_square);
end;
end;
// return final evaluation based on side
if side=white then evaluate:=score else evaluate:=-score;
end;
1. Вылезла проблема - хода короля под шах
Движок пока еще не знает, что такое мат, пат, шах.
Посчитал лучшим ходом - ход под шах, естественно makemove ход не сделала, но очередь хода была передана.
Вобщем я доволен)))
Прошел ровно 50 уроков.
Я думаю благодаря этому форуму у меня получились две вещи.
- Генератор ходов без ошибок (perft test пройден).
- Понял базовые принципы шахматных движков.
- Удалось подключиться по протоколу UCI к оболочке.
Кстати попробовал изменить метод подсчета бит (ссылка выше)
Мне кажется это дает неплохой результат
// https://habr.com/ru/post/276957/
// Комбинированный метод
function count_bits(bb:U64):integer;
var
n:U64;
a1,a2,a3,a4:U64;
begin
a1:=$5555555555555555;
a2:=$3333333333333333;
a3:=$0F0F0F0F0F0F0F0F;
a4:=$0101010101010101;
n:=bb-(bb shr 1) and a1;
n:=((n shr 2) and a2) + (n and a2);
n:=((((n shr 4) + n) and a3) * a4) shr 56;
result:=n;
end;
Warning: Spoiler![ Click to expand ][ Click to hide ]
Warning: Spoiler![ Click to expand ][ Click to hide ]
Вроде тесты прошел и скорость прибавилась, но надо еще тестить.
Попробовал даже сыграть с движком при depth=6
Сыграл вничью
И это еще практически не реализовано кроме negamax с alfabeta обрезкой.
Правда во время игры вылезла ошибка - код исключения 0xc0000005.
Доигрывал перезапустив движок.
Както так.
Провел еще один perft test с функцией подсчета бит комбинированным методом, просто, чтобы быть уверенным в этом методе и его реализации в коде.
Метод однозначно лучший.
Warning: Spoiler![ Click to expand ][ Click to hide ]
Правда сначала я был ошарашен, результат не совпал.
Потом догадался, у меня размерность - Cardinal 4294967295 беззнаковый, 32-бит, а результат вышел за пределы числа.
Короче результат ОК
Warning: Spoiler![ Click to expand ][ Click to hide ]
Нашел решение очень важного момента.
Важный момент - это утечка памяти.
Обнаружил так
//https://stackoverflow.com/questions/437683/how-to-get-the-memory-used-by-a-delphi-program?utm_source=pocket_saves
function GetMemoryUsed: UInt64;
var
st: TMemoryManagerState;
sb: TSmallBlockTypeState;
begin
GetMemoryManagerState(st);
result := st.TotalAllocatedMediumBlockSize
+ st.TotalAllocatedLargeBlockSize;
for sb in st.SmallBlockTypeStates do begin
result := result + sb.UseableBlockSize * sb.AllocatedBlockCount;
end;
end;
Решение такое, на каждое New(add_move);
Dispose(add_move); и вместо
FillChar(Input_str, SizeOf(Input_str), 0);
просто Input_str:='';
Warning: Spoiler![ Click to expand ][ Click to hide ]
Warning: Spoiler![ Click to expand ][ Click to hide ]
procedure search_position(depth:integer);
var
score:integer;
begin
// half move counter
ply:=0;
// best move
best_move:=0;
// nodes count
nodes:=0;
New(add_move);
// find best move within a given position
score := negamax(-50000, 50000, depth);
if best_move>0 then begin
//printf("info score cp %d depth %d nodes %ld\n", score, depth, nodes);
Writeln(Format('info score cp %d depth %d nodes %u',[score, depth, nodes]));
// best move placeholder
Write('bestmove ');
print_move(best_move);
Writeln('');
Dispose(add_move);
end;
end;
Warning: Spoiler![ Click to expand ][ Click to hide ]
// parse user/GUI move string input (e.g. "e7e8q")
function parse_move(move_string:string):integer;
var
source_square,target_square:byte;
j,moveInt:integer;
promoted_piece:char;
begin
// parse source square
source_square:=(ord(move_string[1])-ord('a')) + (8 - (ord(move_string[2]) - ord('0'))) * 8;
// parse target square
target_square:=(ord(move_string[3])-ord('a')) + (8 - (ord(move_string[4]) - ord('0'))) * 8;
// create move list instance
New(add_move);
// generate moves
generate_moves();
// loop over the moves within a move list
for j := 0 to add_move.count-1 do begin
// init move
moveInt:=add_move.move[j];
result:=moveInt;
// make sure source & target squares are available within the generated move
if ((source_square=get_source(moveInt,get_move_source)) and (target_square=get_source(moveInt,get_move_target))) then begin
// init promoted piece
promoted_piece := promoted_pieces[get_source(moveInt,get_move_promoted)];
if (( length(move_string)>4) and (promoted_piece<>'')) then begin
// promoted to queen
if (((move_string[5] = 'Q') or (move_string[5] = 'q')) and (promoted_piece = 'q')) then begin
// return legal move
//Writeln('promoted to queen');
Dispose(add_move);
exit;
end else
// promoted to rook
if (((move_string[5] = 'R') or (move_string[5] = 'r')) and (promoted_piece = 'r')) then begin
// return legal move
//Writeln('promoted to rook');
Dispose(add_move);
exit;
end else
// promoted to bishop
if (((move_string[5] = 'B') or (move_string[5] = 'b')) and (promoted_piece = 'b')) then begin
// return legal move
//Writeln('promoted to bishop');
Dispose(add_move);
exit;
end else
// promoted to knight
if (((move_string[5] = 'N') or (move_string[5] = 'n')) and (promoted_piece = 'n')) then begin
// return legal move
//Writeln('promoted to knight');
Dispose(add_move);
exit;
end else
// continue the loop on possible wrong promotions (e.g. "e7e8f")
continue;
end;
// return legal move
//Writeln('return legal move');
Dispose(add_move);
exit;
end;
end;//for
// return illegal move
// Writeln('return illegal move');
Dispose(add_move);
result:=0;
end;
Warning: Spoiler![ Click to expand ][ Click to hide ]
// main UCI loop
procedure uci_loop();
var
Input_str:AnsiString;
begin
Writeln('id name BBC_Alex');
Writeln('id name alexlaw');
Writeln('uciok');
// main loop
while true do begin
Input_str:='';
// reset user /GUI input
//FillChar(Input_str, SizeOf(Input_str), 0);
Writeln(Format('Memory=%u',[GetMemoryUsed]));
// make sure output reaches the GUI
Flush(Output);
Readln(Input_str);
if Input_str=#13#10 then continue else
// parse UCI "isready" command
if pos('isready',Input_str)>0 then begin
Writeln('readyok');
continue;
end else
// parse UCI "position" command
if pos('position',Input_str)>0 then begin
// call parse position function
parse_position(Input_str);
end else
// parse UCI "ucinewgame" command
if pos('ucinewgame',Input_str)>0 then begin
// call parse position function
parse_position('position startpos');
end else
// call parse go function
if pos('go',Input_str)>0 then begin
parse_go(Input_str);
end else
// parse UCI "quit" command
if pos('quit',Input_str)>0 then begin
// quit from the chess engine program execution
break;
end else
// parse UCI "uci" command
if pos('uci',Input_str)>0 then begin
// print engine info
Writeln('id name BBC_Alex');
Writeln('id name alexlaw');;
Writeln('uciok');
end;
end;
end;
Хотел подвести какой то итог шагов разработки шахматного движка
1. Атаки прыгающих фигур (король,конь,пешка)
2. Атаки скользящих фигур (слон,ладья,ферзь)
3. Представление данных о позиции в памяти компа.
- 12 битбоардов (тип и цвет фигур)
- 3 битбоарда (белые, черные, все)
- сторона хода
- состояние рокеровки
- поле взятия на проходе
4. Интерфейс (взаимодействие с человеком) для наглядного представления работы движка.
5. Функции
- подсчет битов в числе
- нахождение первого установленного бита в числе
- проверка установлен ли бит в любой позиции числа
- сброс любого бита в числе
- нахождение для каждого поля доски всех атак на это поле со стороны фигур, принадлежащих белым или черным
6. Генератор ходов
- тихие ходы пешек
- ходы взятие пешек
- рокеровка
- ходы прыгающих и скользящих фигур с помощью таблиц атак
- сформировать список ходов в соответствии с алгоритмом сжатия инфы о ходе
7.Сжатие информации о ходе в одно число
- откуда
- куда
- кто
- превращение пешки
- ? взятие
- ? ход пешки на 2 поля
- битое поле
- рокеровка
8.Сделать ход
- запомнить позицию из п.3
- проверить короля на предмет атаки
- восстановить поз при атаке на короля или применить ход
9. проверить все с помощью теста perft
Итак, после если тесты perft пройдены без ошибок, это значит можно работать над силой движка, используя накопленные за десятилетия алгоритмы.
В основе всего используется алгоритм nega max.
nega max основан на методе минимакс, который ищет лучший ход, учитывая, что оппонент будет делать свой лучший ответ на каждый ход. Однако, в отличие от минимакса, который рассматривает только собственные ходы, nega max рассматривает ходы обоих игроков, при этом считая, что оппонент всегда будет делать наилучший ход
alphabeta
function integer alphabeta (node,player,alpha,beta,depth)
if depth <= 0 :
return the heuritic value of node for player A
if (player is A)
for child in node
alpha = max(alpha,alphabeta(child,not(player),alpha,beta,depth −1))
if (beta<=alpha)
return beta
next for
return alpha
end
if (player is B)
for child in node
beta = min(beta,alphabeta(child,not(player),alpha,beta,depth −1))
if (beta<=alpha)
return alpha
next for
return beta
end
end function
nega max
function integer alphabeta (node,alpha,beta,depth)
if depth <= 0 :
return the heuristic value of node for current player
for child in node :
alpha = max(alpha,−alphabeta(child,−beta,−alpha,depth −1))
if (alpha>=beta)
return beta;
next for
return alpha
end function
Главное новшество этого алгоритма это полная симметрия кода для каждой из сторон, что позволяет исключить лишние проверки. Оценочная функция вызывается на любой глубине не с точки зрения игрока А, а со стороны игрока,чья очередь ходить на данной глубине.
Предположим, функция на определенной глубине вернула оценку для своей стороны.
Вернувшись на уровень выше, этой оценке будет добавлен «минус» и будет найден максимум всех этих «минусовых» позиций, что эквивалентно нахождению минимума для оценок без «минуса» таких какие были получены на следующей глубине. Мы все еще неявно проводим чередования поиска.
максимума с поиском минимума, но делаем это более элегантно.
Таким образом nega max полностью эквивалентен минимаксу и это ясно из следующего математического тождества.
max(a,b) = −min(−a,−b)
В результате выполнения nega max, мы получаем наилучший ход для текущего игрока, который, как предполагается, позволит ему выиграть при оптимальной игре оппонента.
Ну а дальше идут различные эвристики, чтобы сократить дерево перебора, т.е. как можно раньше и больше отрезать не нужных ветвей дерева.
Человечество накопило большой опыт в этом.
Пришлось повозится с уроком
66.Bitboard CHESS ENGINE in C: handling TIME CONTROLS (forked from VICE by BluefeverSoftware)
Дальнейшая реализация протокола UCI
Пришлось привлечь интеллект искуственный
Он помог
function input_waiting(): boolean;
var
ReadFds: TFDSet;
TimeVal: TTimeVal;
InputHandle: THandle;
BytesAvail: DWORD;
begin
FD_ZERO(ReadFds);
InputHandle := GetStdHandle(STD_INPUT_HANDLE);
FD_SET(InputHandle, ReadFds);
TimeVal.tv_sec := 0;
TimeVal.tv_usec := 0;
if PeekNamedPipe(InputHandle, nil, 0, nil, @BytesAvail, nil) then
Result := (BytesAvail > 0);
end;
// read GUI/user input
procedure read_input;
var
Bytes: DWORD;
Input: array[0..255] of Char;
EndChar: PChar;
begin
// "listen" to STDIN
if input_waiting then begin
// tell engine to stop calculating
stopped := 1;
repeat
Bytes := 0;
if not ReadFile(GetStdHandle(STD_INPUT_HANDLE), Input, SizeOf(Input), Bytes, nil) then
Break;
until Bytes > 0;
EndChar := StrScan(Input, #10);
if Assigned(EndChar) then
EndChar^ := #0;
if StrLen(Input) > 0 then
begin
if StrLIComp(Input, 'quit', 4) = 0 then begin
Writeln('Quit OK');
// tell engine to terminate exacution
quit := 1;
end
else if StrLIComp(Input, 'stop', 4) = 0 then begin
Writeln('Stop OK');
// tell engine to terminate exacution
quit := 1;
end;
end;
end;
end;
// a bridge function to interact between search and GUI input
procedure communicate();
begin
// if time is up break here
if((timeset = 1) and (get_time_ms() > stoptime)) then begin
// tell engine to stop calculating
stopped := 1;
end;
// read GUI input
read_input();
end;
Суть в том, что если во время анализа в консоле обнаружатся команды, движок среагирует.
Короче теперь он умеет играть блиц и другой контроль времени
Вот сам с собой сыграл в блиц
Машины уже играют в шахматы лучше человека. Скоро они будут играть лучше него в футбол, бильярд и теннис... И это правильно, пусть играют, а человек должен работать!
Ну не...
Пешка на е4 должна быть черной для связки.
Связывающая фигура одного цвета, первая в тройке.
За ней связанная и объект связки. Оба противоположного
Сейчас я использую такой алгоритм
1. Убираем свои фигуры
2. Ставим ферзя на место своего короля
3. Находим атаки этого ферзя (из таблиц атак)
4. Находим атакуемых врагов.
5. Подставляем на место своего ферзя (короля) тип врага
6. Находим его атаки
7. Пересечение атак - это луч атаки между врагом и своим королем
8. Ставим свои фигуры на место
9. Если на зтом луче есть одна своя фигура, то она связана
Ну не...
Пешка на е4 должна быть черной для связки.
Связывающая фигура одного цвета, первая в тройке.
За ней связанная и объект связки. Оба противоположного
А как назвать такую позицию, если это не связка?
PS ход черных тут