 |
-
alexlaw
-
-
OFFLINE
-
Стольник
-
- Posts: 107
- Thank you received: 2
-
Karma: 0
-
|
К сожалению нет компа под рукой.
Не могу проверить для Делфи.
Посетила такая мысль.
Если спуститься на глубину 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;
}
}
|
Last Edit: 11 Фев 2023 10:56 by alexlaw.
|
-
alexlaw
-
-
OFFLINE
-
Стольник
-
- Posts: 107
- Thank you received: 2
-
Karma: 0
-
|
Сегодня проверю критическую ветку, где присутствует шах и установлено битое поле.
Рассмотрена строго одна ветка дерева без ветвлений.
Проверил.
Разницы нет
|
Last Edit: 12 Фев 2023 08:13 by alexlaw.
|
-
alexlaw
-
-
OFFLINE
-
Стольник
-
- Posts: 107
- Thank you received: 2
-
Karma: 0
-
|
Искусственный интеллект рулит!
Сегодня узнал, что в Яндекс браузер встроен перевод видео.
Можно смотреть Ютуб с озвучкой на русском языке и не заморачиваться с этим)))
|
|
-
alexlaw
-
-
OFFLINE
-
Стольник
-
- Posts: 107
- Thank you received: 2
-
Karma: 0
-
|
Наконец то я понял методику поиска ошибки
1. Позиция, где не пройден тест perft
8/2p5/3p4/KP5r/1R3p1k/8/4P1P1/8 w - -
2.Ищем в каком случае разница
depth=5 - нет разницы
depth=6 - есть разница
3. Делаем ход, в котором есть разница в значениях и уменьшаем глубину на 1
В данном случае я выбрал ход b4a4
8/2p5/3p4/KP5r/R4p1k/8/4P1P1/8 b - - 0 1
4.Ищем разницу при depth=5
5.Делаем ход h4g3 и уменьшаем глубину на 1
8/2p5/3p4/KP5r/R4p2/6k1/4P1P1/8 w - - 0 1
e2e3
8/2p5/3p4/KP5r/R4p2/4P1k1/6P1/8 b - - 0 1
Вот он
Теперь искать, почему?
|
Last Edit: 12 Фев 2023 16:11 by alexlaw.
|
-
alexlaw
-
-
OFFLINE
-
Стольник
-
- Posts: 107
- Thank you received: 2
-
Karma: 0
-
|
Нашел.
// 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, но он этого не происходит.
Может ли это гдето вылезти еще, большой вопрос.
|
|
-
alexlaw
-
-
OFFLINE
-
Стольник
-
- Posts: 107
- Thank you received: 2
-
Karma: 0
-
|
Вот и решение вопроса
if (bitboard shl 8)<>0 then attacks:=attacks or (bitboard shl 8);
if (bitboard shl 8) <>0
8/2p5/3p4/KP5r/1R3p1k/8/4P1P1/8 w - -
Perft=7
Все OK
|
Last Edit: 12 Фев 2023 18:31 by alexlaw.
|
-
alexlaw
-
-
OFFLINE
-
Стольник
-
- Posts: 107
- Thank you received: 2
-
Karma: 0
-
|
Уроки
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).
Удалось подключиться по протоколу UCI.
К Arena Chess GUI 1.1 и к WinBoard-4.8.0
{/**********************************\
==================================
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;
{/*
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;
{/*
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;
{/*
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;
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
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
PS
Изменил 2 строчки кода
Input_str:widestring;
---
FillChar(Input_str, SizeOf(Input_str), 0);
|
Last Edit: 19 Фев 2023 04:48 by alexlaw.
|
-
alexlaw
-
-
OFFLINE
-
Стольник
-
- Posts: 107
- Thank you received: 2
-
Karma: 0
-
|
На самом деле еще не все моменты освещены на данном этапе.
- шах, мат, пат
- троекратное повторение
- правило 50 ходов
Еще важный момент
Если на вход bbc поступает один из видов нелегетимных ходов (ход короля под шах),
bbc игнорирует этот ход (не делает его в makemove), но не сообщает, что это illegal move.
|
|
-
alexlaw
-
-
OFFLINE
-
Стольник
-
- Posts: 107
- Thank you received: 2
-
Karma: 0
-
|
Кто из знатоков СИ может обЪяснить это enum {
a8, b8, c8, d8, e8, f8, g8, h8,
a7, b7, c7, d7, e7, f7, g7, h7,
a6, b6, c6, d6, e6, f6, g6, h6,
a5, b5, c5, d5, e5, f5, g5, h5,
a4, b4, c4, d4, e4, f4, g4, h4,
a3, b3, c3, d3, e3, f3, g3, h3,
a2, b2, c2, d2, e2, f2, g2, h2,
a1, b1, c1, d1, e1, f1, g1, h1, no_sq
}; const int mirror_score[128] =
{
a1, b1, c1, d1, e1, f1, g1, h1,
a2, b2, c2, d2, e2, f2, g2, h2,
a3, b3, c3, d3, e3, f3, g3, h3,
a4, b4, c4, d4, e4, f4, g4, h4,
a5, b5, c5, d5, e5, f5, g5, h5,
a6, b6, c6, d6, e6, f6, g6, h6,
a7, b7, c7, d7, e7, f7, g7, h7,
a8, b8, c8, d8, e8, f8, g8, h8
};
Что вернет mirror_score[h8] и почему размер массива 128, а элементов 64?
|
|
-
Vladimirovich
-
-
NOW ONLINE
-
Инквизитор
-
- Posts: 100819
- Thank you received: 1842
-
Karma: 101
-
|
enum это именованные последовательные константы (для полей в данном случае)
mirror_score их и пользует.
Для чего зарезервировали 128 без контекста не понять
mirror_score[h8] это извращение. Так делать никогда нельзя. Весь смысл enum в том, чтобы конкретное значение константы было неважно.
Иначе будет memory corruption при случае
Но с данным enum h8 = 7 (a8 = 0 по умолчанию)
То бишь mirror_score[h8] вернет h1
Но потом не надо огорчаться, что при таком стиле кодинга все вдруг упадет.
|
|
-
alexlaw
-
-
OFFLINE
-
Стольник
-
- Posts: 107
- Thank you received: 2
-
Karma: 0
-
|
Не стал заморачиваться, сделал функцию оценки (материал и расположение).
Протестировал, результы совпадают с Максом.
{/**********************************\
==================================
Evaluation
==================================
\**********************************/}
// 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 = (
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
);
const
// pawn positional score
pawn_score:array[0..63] of integer =
(
90, 90, 90, 90, 90, 90, 90, 90,
30, 30, 30, 40, 40, 30, 30, 30,
20, 20, 20, 30, 30, 30, 20, 20,
10, 10, 10, 20, 20, 10, 10, 10,
5, 5, 10, 20, 20, 5, 5, 5,
0, 0, 0, 5, 5, 0, 0, 0,
0, 0, 0, -10, -10, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0
);
// knight positional score
knight_score:array[0..63] of integer =
(
-5, 0, 0, 0, 0, 0, 0, -5,
-5, 0, 0, 10, 10, 0, 0, -5,
-5, 5, 20, 20, 20, 20, 5, -5,
-5, 10, 20, 30, 30, 20, 10, -5,
-5, 10, 20, 30, 30, 20, 10, -5,
-5, 5, 20, 10, 10, 20, 5, -5,
-5, 0, 0, 0, 0, 0, 0, -5,
-5, -10, 0, 0, 0, 0, -10, -5
);
// bishop positional score
bishop_score:array[0..63] of integer =
(
0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 10, 10, 0, 0, 0,
0, 0, 10, 20, 20, 10, 0, 0,
0, 0, 10, 20, 20, 10, 0, 0,
0, 10, 0, 0, 0, 0, 10, 0,
0, 30, 0, 0, 0, 0, 30, 0,
0, 0, -10, 0, 0, -10, 0, 0
);
// rook positional score
rook_score:array[0..63] of integer =
(
50, 50, 50, 50, 50, 50, 50, 50,
50, 50, 50, 50, 50, 50, 50, 50,
0, 0, 10, 20, 20, 10, 0, 0,
0, 0, 10, 20, 20, 10, 0, 0,
0, 0, 10, 20, 20, 10, 0, 0,
0, 0, 10, 20, 20, 10, 0, 0,
0, 0, 10, 20, 20, 10, 0, 0,
0, 0, 0, 20, 20, 0, 0, 0
);
// king positional score
king_score:array[0..63] of integer =
(
0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 5, 5, 5, 5, 0, 0,
0, 5, 5, 10, 10, 5, 5, 0,
0, 5, 10, 20, 20, 10, 5, 0,
0, 5, 10, 20, 20, 10, 5, 0,
0, 0, 5, 10, 10, 5, 0, 0,
0, 5, 5, -5, -5, 0, 5, 0,
0, 0, 5, 0, -15, 0, 10, 0
);
// mirror positional score tables for opposite side
mirror_score:array[TBoard_squares] of TBoard_squares =
(
a1, b1, c1, d1, e1, f1, g1, h1,
a2, b2, c2, d2, e2, f2, g2, h2,
a3, b3, c3, d3, e3, f3, g3, h3,
a4, b4, c4, d4, e4, f4, g4, h4,
a5, b5, c5, d5, e5, f5, g5, h5,
a6, b6, c6, d6, e6, f6, g6, h6,
a7, b7, c7, d7, e7, f7, g7, h7,
a8, b8, c8, d8, e8, f8, g8, h8
);
// position evaluation
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;
|
Last Edit: 18 Фев 2023 10:22 by alexlaw.
|
-
alexlaw
-
-
OFFLINE
-
Стольник
-
- Posts: 107
- Thank you received: 2
-
Karma: 0
-
|
Сыграл первую игру с движком
Depth=4
1. Вылезла проблема - хода короля под шах
Движок пока еще не знает, что такое мат, пат, шах.
Посчитал лучшим ходом - ход под шах, естественно makemove ход не сделала, но очередь хода была передана.
Вобщем я доволен)))
Прошел ровно 50 уроков.
|
|
-
alexlaw
-
-
OFFLINE
-
Стольник
-
- Posts: 107
- Thank you received: 2
-
Karma: 0
-
|
Я думаю благодаря этому форуму у меня получились две вещи.
- Генератор ходов без ошибок (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;
Вроде тесты прошел и скорость прибавилась, но надо еще тестить.
Попробовал даже сыграть с движком при depth=6
Сыграл вничью
И это еще практически не реализовано кроме negamax с alfabeta обрезкой.
Правда во время игры вылезла ошибка - код исключения 0xc0000005.
Доигрывал перезапустив движок.
Както так.
|
Last Edit: 19 Фев 2023 17:52 by alexlaw.
|
-
alexlaw
-
-
OFFLINE
-
Стольник
-
- Posts: 107
- Thank you received: 2
-
Karma: 0
-
|
Провел еще один perft test с функцией подсчета бит комбинированным методом, просто, чтобы быть уверенным в этом методе и его реализации в коде.
Метод однозначно лучший.
Правда сначала я был ошарашен, результат не совпал.
Потом догадался, у меня размерность - Cardinal 4294967295 беззнаковый, 32-бит, а результат вышел за пределы числа.
Короче результат ОК
Performance test
move:d5d6 nodes:151133066
move:d5e6 nodes:203255191
move:a2a3 nodes:197413067
move:a2a4 nodes:183872225
move:b2b3 nodes:153953689
move:g2g3 nodes:141076301
move:g2g4 nodes:135208177
move:g2h3 nodes:158328615
move:e5d7 nodes:193856446
move:e5f7 nodes:176070755
move:e5c6 nodes:169836097
move:e5g6 nodes:165477768
move:e5c4 nodes:145182844
move:e5g4 nodes:144264874
move:e5d3 nodes:140737072
move:c3b5 nodes:166970874
move:c3a4 nodes:191260040
move:c3b1 nodes:165673862
move:c3d1 nodes:165415976
move:d2h6 nodes:161319567
сумма 3310306506
move:d2g5 nodes:177883051
move:d2f4 nodes:165805784
move:d2e3 nodes:184114087
move:d2c1 nodes:158801466
move:e2a6 nodes:130642863
move:e2b5 nodes:158033152
move:e2c4 nodes:170094798
move:e2d3 nodes:167737155
move:e2d1 nodes:131348645
move:e2f1 nodes:174218453
move:a1b1 nodes:160413321
move:a1c1 nodes:159720218
move:a1d1 nodes:149265033
move:h1f1 nodes:154273720
move:h1g1 nodes:166086672
move:f3f6 nodes:146338070
move:f3f5 nodes:226135507
move:f3h5 nodes:197839051
move:f3f4 nodes:181938761
move:f3g4 nodes:189789456
move:f3d3 nodes:164583144
move:f3e3 nodes:189120807
move:f3g3 nodes:198078522
move:f3h3 nodes:210100865
move:e1g1 nodes:172063416
move:e1c1 nodes:148701308
move:e1d1 nodes:148612404
move:e1f1 nodes:139601450
сумма 4721341179
Итого: 8031647685
Depth:6
Nodes:
Время: Часы:0, Минуты: 1, Секунды: 0, Миллисекунды: 453
perft:6
nodes:
Время: Часы:0, Минуты: 59, Секунды: 20, Миллисекунды: 484
Нажмите <ENTER>, чтобы выйти ...
Скорость порадовала, по сравнению с другими методами подсчета бит.
Вывод: Метод нужно брать на вооружение
|
|
-
alexlaw
-
-
OFFLINE
-
Стольник
-
- Posts: 107
- Thank you received: 2
-
Karma: 0
-
|
Нашел решение очень важного момента.
Важный момент - это утечка памяти.
Обнаружил так //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:='';
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;
{/**********************************\
==================================
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');
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;
// 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;
|
|
-
alexlaw
-
-
OFFLINE
-
Стольник
-
- Posts: 107
- Thank you received: 2
-
Karma: 0
-
|
Движок сыграл сам с собой.
Глубина перебора всего 4
Неплохо
|
|
-
Andralex
-
-
OFFLINE
-
Боярин
-
-
на уровне 2 разряда
- Posts: 2029
- Thank you received: 53
-
Karma: 12
-
|
Какие-то симметричные построения с конями к центру. 8... Be7
|
...не мы первые, не мы последние...
|
-
alexlaw
-
-
OFFLINE
-
Стольник
-
- Posts: 107
- Thank you received: 2
-
Karma: 0
-
|
Хотел подвести какой то итог шагов разработки шахматного движка
1. Атаки прыгающих фигур (король,конь,пешка)
2. Атаки скользящих фигур (слон,ладья,ферзь)
3. Представление данных о позиции в памяти компа.
- 12 битбоардов (тип и цвет фигур)
- 3 битбоарда (белые, черные, все)
- сторона хода
- состояние рокеровки
- поле взятия на проходе
4. Интерфейс (взаимодействие с человеком) для наглядного представления работы движка.
5. Функции
- подсчет битов в числе
- нахождение первого установленного бита в числе
- проверка установлен ли бит в любой позиции числа
- сброс любого бита в числе
- нахождение для каждого поля доски всех атак на это поле со стороны фигур, принадлежащих белым или черным
6. Генератор ходов
- тихие ходы пешек
- ходы взятие пешек
- рокеровка
- ходы прыгающих и скользящих фигур с помощью таблиц атак
- сформировать список ходов в соответствии с алгоритмом сжатия инфы о ходе
7.Сжатие информации о ходе в одно число
- откуда
- куда
- кто
- превращение пешки
- ? взятие
- ? ход пешки на 2 поля
- битое поле
- рокеровка
8.Сделать ход
- запомнить позицию из п.3
- проверить короля на предмет атаки
- восстановить поз при атаке на короля или применить ход
9. проверить все с помощью теста perft
|
Last Edit: 23 Фев 2023 19:32 by alexlaw.
|
-
Andralex
-
-
OFFLINE
-
Боярин
-
-
на уровне 2 разряда
- Posts: 2029
- Thank you received: 53
-
Karma: 12
-
|
- сторона хода
- состояние рокеровки
- поле взятия на проходе Так и есть. Это прописывается в формате FEN.
Ещё есть число ходов, прошедших без взятия пешки, или движения пешки.
- превращение пешки Всегда в ферзя, или также выборочно в другие фигуры?
|
...не мы первые, не мы последние...
|
-
alexlaw
-
-
OFFLINE
-
Стольник
-
- Posts: 107
- Thank you received: 2
-
Karma: 0
-
|
Итак, после если тесты perft пройдены без ошибок, это значит можно работать над силой движка, используя накопленные за десятилетия алгоритмы.
В основе всего используется алгоритм nega max.
nega max основан на методе минимакс, который ищет лучший ход, учитывая, что оппонент будет делать свой лучший ответ на каждый ход. Однако, в отличие от минимакса, который рассматривает только собственные ходы, nega max рассматривает ходы обоих игроков, при этом считая, что оппонент всегда будет делать наилучший ход
alphabetafunction 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 maxfunction 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, мы получаем наилучший ход для текущего игрока, который, как предполагается, позволит ему выиграть при оптимальной игре оппонента.
Ну а дальше идут различные эвристики, чтобы сократить дерево перебора, т.е. как можно раньше и больше отрезать не нужных ветвей дерева.
Человечество накопило большой опыт в этом.
|
|
-
alexlaw
-
-
OFFLINE
-
Стольник
-
- Posts: 107
- Thank you received: 2
-
Karma: 0
-
|
Andralex wrote:
- сторона хода
- состояние рокеровки
- поле взятия на проходе Так и есть. Это прописывается в формате FEN.
Ещё есть число ходов, прошедших без взятия пешки, или движения пешки.
- превращение пешки Всегда в ферзя, или также выборочно в другие фигуры? parse_fen('rnbqkb1r/pp1p1pPp/8/2p1pP2/1P1P4/3P3P/P1P1P3/RNBQKBNR w KQkq e6 0 1');
print_board();
New(add_move);
generate_moves(add_move);
print_move_list();
Генератор ходов - генерирует все возможные ходы, в том числе и превращения пешек во все фигуры
rnbqkb1r/pp1p1pPp/8/2p1pP2/1P1P4/3P3P/P1P1P3/RNBQKBNR w KQkq e6 0 1
8 r n b q k b . r
7 # # . # . # P #
6 . . . . . . . .
5 . . # . # P . .
4 . P . P . . . .
3 . . . P . . . P
2 P . P . P . . .
1 R N B Q K B N R
a b c d e f g h
side = white
castle = KQkq
enpassant = e6
move piece capture double enpass castling |
g7g8q P_ 0 0 0 0 |
g7g8r P_ 0 0 0 0 |
g7g8b P_ 0 0 0 0 |
g7g8n P_ 0 0 0 0 |
g7f8q P_ 1 0 0 0 |
g7f8r P_ 1 0 0 0 |
g7f8b P_ 1 0 0 0 |
g7f8n P_ 1 0 0 0 |
g7h8q P_ 1 0 0 0 |
g7h8r P_ 1 0 0 0 |
g7h8b P_ 1 0 0 0 |
g7h8n P_ 1 0 0 0 |
f5f6 P_ 0 0 0 0 |
f5e6 P_ 1 0 1 0 |
b4b5 P_ 0 0 0 0 |
b4c5 P_ 1 0 0 0 |
d4d5 P_ 0 0 0 0 |
d4c5 P_ 1 0 0 0 |
d4e5 P_ 1 0 0 0 |
h3h4 P_ 0 0 0 0 |
a2a3 P_ 0 0 0 0 |
a2a4 P_ 0 1 0 0 |
c2c3 P_ 0 0 0 0 |
c2c4 P_ 0 1 0 0 |
e2e3 P_ 0 0 0 0 |
e2e4 P_ 0 1 0 0 |
b1a3 N_ 0 0 0 0 |
b1c3 N_ 0 0 0 0 |
b1d2 N_ 0 0 0 0 |
g1f3 N_ 0 0 0 0 |
c1h6 B_ 0 0 0 0 |
c1g5 B_ 0 0 0 0 |
c1f4 B_ 0 0 0 0 |
c1a3 B_ 0 0 0 0 |
c1e3 B_ 0 0 0 0 |
c1b2 B_ 0 0 0 0 |
c1d2 B_ 0 0 0 0 |
f1g2 B_ 0 0 0 0 |
h1h2 R_ 0 0 0 0 |
d1d2 Q_ 0 0 0 0 |
e1d2 K_ 0 0 0 0 |
e1f2 K_ 0 0 0 0 |
Количество ходов 42
Нажмите <ENTER>, чтоб
ы выйти ...
Затем нужно просто выбрать лучший ход
PS к сожалению табличка не получилась
|
Last Edit: 24 Фев 2023 06:55 by alexlaw.
|
-
alexlaw
-
-
OFFLINE
-
Стольник
-
- Posts: 107
- Thank you received: 2
-
Karma: 0
-
|
Пришлось повозится с уроком
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;
Суть в том, что если во время анализа в консоле обнаружатся команды, движок среагирует.
Короче теперь он умеет играть блиц и другой контроль времени
Вот сам с собой сыграл в блиц
Машины уже играют в шахматы лучше человека. Скоро они будут играть лучше него в футбол, бильярд и теннис... И это правильно, пусть играют, а человек должен работать!
|
Last Edit: 01 Март 2023 20:42 by alexlaw.
|
-
alexlaw
-
-
OFFLINE
-
Стольник
-
- Posts: 107
- Thank you received: 2
-
Karma: 0
-
|
Попытка создать алгоритм текущей реализации движка
|
|
|
|
|
 |