О сколько ты открытий чудных готовишь просвещенья дух!



Pdf просмотр
страница1/2
Дата14.02.2017
Размер1.38 Mb.
Просмотров408
Скачиваний0
  1   2

“О сколько ты открытий чудных
готовишь просвещенья дух!”
А.С.Пушкин
Шахматы
Машина играет в шахматы! Утверждение, казавшееся невероятным в середине 20го века, ни у кого не вызывает удивления сейчас. К хорошему быстро привыкают.
В этой книге, не претендуя на полноту и абсолютную точность, изложены основные принципы построения шахматной программы среднего уровня.
Корнилов Е.Н. 2012

Введение.
Взгляд на шахматную игру - Шахматы это высокоинтеллектуальная игра, развлечение, отдых для ума и способ организации мышления. Шахматы учат планировать будущее и соразмерять свои возможности. Капабланка учил шахматной игре начиная с эндшпиля. Малофигурные окончания помогают овладеть управлением фигурами и понять цели или эвристики для каждой фигуры (а также их ценность).
Шахматы отражают философию человека и его модель поведения. Вопрос как правильно играть видимо из категории вопросов "Как правильно жить"
У чемпиона мира Алехина всегда была ясная цель (цели) для каждого хода. Это помогало партии не распадаться на части, а сохранять внутреннюю напряженность.
Сейчас играют не так как в начале 20-го века. Главной становится фигурная активность в том смысле как кто ее понимает. Наверное - это правильно.
Компьютеры наступают. То, что раньше было прерогативой исключительно человека, теперь заменяется машинным интеллектом. На рисунке изображено 'чудо' 20-21 века - шахматный компьютер 'Каспаров-Chess'. Очень удобно. Можно выставлять различные уровни игры и не ломать глаза об монитор компьютера.
Действительно ли машига 'думает' или это удачная иммитация? В принципе - какая разница, если это выглядит как настоящее. Найти подходящего партнера для партии в шахматы бывает порой непросто или даже невозможно. С годами люди начинают очень обостренно воспринимать игру. А машина всегда под рукой. Если нет настоящего шахматного компьютера - можно и с ChessMaster сыграть.

'Houdini' - нынешний чемпион мира
Недавно смотрел фильм 'Револьвер'. Главный герой здорово наловчился играть в шахматы.
Всех обыгрывал по своей 'формуле'. Сыграли с ним раз, другой. Говорят - "Как ты это делаешь? Мы с тобой больше не играем".
В этом, видимо, основная проблемы многих современных движков - они слишком сильно играют. Их могут использовать профессионалы для анализа позиций или устраивать 'гладиаторские' бои с другими программами, но для обычного среднего пользователя они не представляют большого интереса. Кому нравится когда его бьют, душат и пр. фигурально выражаясь. Вот и приходится для развлечения откапывать старые программы или опять тот же ChessMaster использовать. В этом плане очень хорощо выглядят Kasparov-Chess версия для настольного ПК. Я лично выиграл и еще разок с удовольствием сыграл.

MinMax
MinMax есть основной переборный алгоритм поиска для 2х игроков. Он очень прост:
1. Мы получаем все ходы из данной позиции
2. Делаем по очереди все перемещения.
3. Оцениваем все позиции, полученные из исходной.
4. Запоминаем лучшую оценку и лучший ход.
5. Возвращаем лучшую оценку.
Основной неясный момент с функцией оценки – как она может точно оценить все промежуточные позиции в игре. До некоторой глубины поиска в качестве функции оценки используется вариант функции MinMax для оппонента. Затем вызывается функция статической оценки, приближенно подсчитываюшая все позиционные и материальные факторы.
Итак, нам нужно:
1. Функция MinMax для белых
2. Функция MinMax для черных
3. Оценочная функция
4. Функции генерации перемещений и изменения позиции.
5.
Вот, в принципе и все. Осталось сказать, что оценка берется разностная:
все преимущества белых – все преимущества черных
Этот алгоритм исследует все перемещения и общее кол-во узлов для глубины D и кол-ва перемещений в позиции N будет:
N^D
Рост дерева поиска носит экспоненциальный характер. Прошу запомнить этот очевидный, но такой неприятный факт.

NegaMax
Следующий шаг в развитии алгоритмов поиска называется NegaMax. В сущности это
MiniMax, только вместо 2х функций поиска (для 2х сторон) используется одна с инвертированной оценкой. Как мы помним, оценка в играх для 2х игроков инвертированная:
BLACK_SCORE = -WHITE_SCORE
Вот пример на некоторм несуществующем языке программирования, похожем на Pascal и Си:
/*
Ищет лучший ход и оценку
Исследует все узлы
*/
Function NegaMax(depth,side,xside:integer):integer;
Var
Score, best:integer;
Begin
If depth <= 0 then
Return Evaluate(side);
Generate_all_moves(side);
Best = -INFINITY;
For each move do
Begin
Make_Move(move);
Score = -NegaMax(depth-1,xside,side);
Un_Mack_Move(move);
If score > best then
Best = score;
End;
Return best;
End;
Function Evaluate(side:integer):integer;
Begin
If side = WHITE then
Return WhiteScore – BlackScore
Else
Return BlackScore – WhiteScore;
End;
Используемые термины:
1.
depth – оставшаяся глубина поиска
2.
side,xside – играющая сторона и сторона оппонента
3.
Evaluate – функция статической оценки позиции

4.
Generate_all_moves – ищет все перемещения для данной стороны
5.
Make_Move – делает изменения в позиции
6.
Un_Make_Move – отменяет изменения в позиции
7.
INFINITY – некоторая очень большая велечина, условно принимаемая за бесконечночть
Данный алгоритм как и MinMax исследует все перемещения в каждой позиции и является экспоненциальным:
Количесво_исследованных_позиций = N^D
N – среднее кол-во ходов в каждой позиции
D – глубина поиска
В качестве зарисовки рассмотрим пример алгоритма, исследующего не все перемещения. Он гарантированно рассматривает только один лучший ход в узле. Остальные ходы будут рассмотрены, только если прогнозируемая оценка лучше достигнутой.
/*выборочный поиск*/
Function Search_One_Move(depth,side,xside:integer):integer;
Var
Best,j:integer;
Begin
If depth <= 3 then
Return NegaMax(depth,side,xside);
Generate_all_moves(side);
//оценим все перемещения
For j = 0 to max_moves-1 do
Begin
Make_Move(moves[j]);
Moves_score[j] = -NegaMax(max(3,depth/2),xside,side);
Un_Make_Move(moves[j]);
End;
//отсортируем по убыванию оценки
Sort_Moves();
//поиск – пока приблизительная оценка
//лучше достигнутой
Best = -INFINITY;
For j = 0 to max_moves-1 do
Begin
If moves_score[j] <= best then
Break;
Make_Move(moves[j]);
Moves_score[j] = - Search_One_Move (depth-1,xside,side);
Un_Make_Move(moves[j]);
If moves_score[j] > best then

Best = moves_score[j];
End;
Return best;
End;
Данный алгоритм считает приблизительно в 2 раза глубже, чем NegaMax. Точность поиска не гарантирована.
На какую глубину считать от корня дерева поиска, сразу сказать трудно. Можно увеличивать глубину, пока не исчерпан лимит времени.
/* поиск от корня */
Function Root_Search(side,xside:integer):integer;
Begin
Timer.reset();
Depth = 3;
Score = -INFINITY;
While (depth < MAX_DEPTH) and
Not timer.timeout() and
(Score < WINE_SCORE) do
Begin
Score = Search_One_Move(depth,side,xside);
End;
Return best;
End;

AlphaBeta
Мы рассмотрели MinMax как полный перебор для определения лучшего хода в играх для 2х игроков. Он исследует все перемещения. Следующий шаг состоит в оптимизации этого алгоритма.
Казалось бы на первый взгляд, что нельзя досрочно прекратить поиск в узле без ухудшения качества поиска. Но это не так. В этом весь фокус-покус. Это похоже на функционирование клеток головного мозга (или во всяком случае, на то, как это понимают на данном этапе).
Существует порог срабатывания. Входной сигнал в каждом узле накапливается, пока не превысит некоторого значения. Потом подается сигнал на выход.
Дерево поиска, формируемое рекурсивно, можно представить как своеобразную нейронную сеть. Лучшая оценка увеличивается, пока не достигнет некоторого предела. Какого? В этом весь вопрос.
Представьте себе некоторый узел поиска в дереве перебора. Оценка в нем только увеличивается. Достигнутый максимум передается далее. Оппонент занижает оценку. Если он ее уже занизил до нашего максимума, то дальше искать нет смысла. Все равно меньшая оценка не будет использована. Кому не понятно, я затрудняюсь объяснить. Это несложно, но объяснить затруднительно.
/*
Ищет лучший ход и оценку
Исследует при лучшем порядке перемещений только SQRT( узлов)
*/
Function AlphaBeta(depth,alpha,beta,side,xside:integer):integer;
Var
Score, best:integer;
Begin
If depth <= 0 then
Return Evaluate(side);
Generate_all_moves(side);
Sort_moves();
Best = -INFINITY;
For each move do
Begin
Make_Move(move);
Score = -AlphaBeta(depth-1,-beta,-alpha,xside,side);

Un_Mack_Move(move);
If score > best then begin
Best = score;
Alpha = max(alpha,best);
If alpha >= beta then
Break;
End;
End;
Return best;
End;
Данная функция очень чувствительна к порядку перемещений. При лучшем порядке она может сосчитать в 2 раза глубже и исследует только SQRT(W) позиций, где W – число позиций при полном переборе.

Quies search
После того, как у AlphaBeta поиска исчерпана глубина перебора, у нас вызывалась функция статической оценки Evaluate. Она не учитывает размены фигур, что может приводить к серъезной погрешности. Традиционно принято в конце поиска считать только взятия при помощи специальной функции. Все ‘тихие’ перемещения не рассматриваются. Но может возникнуть ситуация, когда ‘тихий’ ход лучше взятия. Например, есть 2 взятия и оба ведут к потере материала. Для того, чтобы избежать серьезной погрешности в оценке, alpha завышается статической оценкой перед началом поиска. Этот трюк можно объяснить очень просто. Практически в любой позиции есть ход, не ухудшающий текущего положения и значит, оценка поиска не может быть хуже статической оценки позиции.
/*
Ищет только взятия и превращения пешек
*/
Function Quies(alpha,beta,side,xside:integer):integer;
Var
Score, best:integer;
Begin
If depth <= 0 then
Return Evaluate(side);
Alpha := max(alpha, Evaluate(side));
If Alpha >= Beta then
Return beta;
Generate_capture_moves(side);
Sort_moves();
Best = -INFINITY;
For each move do
Begin
Make_Move(move);
Score = - Quies (-beta,-alpha,xside,side);
Un_Mack_Move(move);
If score > best then begin
Best = score;
Alpha = max(alpha,best);
If alpha >= beta then
Break;
End;
End;
Return best;
End;
Обратите внимание, что параметра глубины поиска нет и все взятия рассматриваются до конца.

Взятия перед началом поиска должны быть отсортированы, например по принципу –
(наиболее ценное взятие – наименее ценный нападающий). Взятие последней ходившей фигуры противника тоже имеет высокий приоритет.
Под шахом уходить в статический поиск нельзя, так как надо дать возможность королю уйти.

Хеширование
Как мы помним, от корня дерева поиска увеличение глубины перебора происходит постепенно с шагом (как правило) 1. Делается это по причине того, что неизвестно сразу, на какую глубину сможет сосчитать программа за отведенное время. Кроме того, поиск на глубину d-1 как правило занимает мало времени по сравнению с поиском на глубину d.
Алгоритм AlphaBeta очень чуствителен к порядку ходов. Чтобы программа могла сосчитать на большую глубину необходимо сохранить проделанную работу.
Что есть хеширование? Хеш-таблица – это набор позиций, который для ускорения поиска разбит на несколько групп. Найти конкретную позицию становится намного легче, если мы знаем, где ее искать. Если у нас 1000000 позиций и 1000 групп, то для поиска нам необходимо проверить 1000000/1000 = 1000 позиций. Номер конкретной группы определяется хеш-ключом. Хеш ключ есть отображение большого объекта в число.
Естественно, могут возникать коллизии, когда 2 различных ключа указывают на одну позицию. Это неизбежно, но хорошая хеш-функция генерирует ключи с минимумом коллизий. Традиционно для генерации ключей используются простые числа. Например, чтобы получить ключ строки, можно сделать что-то вроде:
Var key: LongWord;
Key = 0;
For J = low(str) to high(str) do
Key = (key shl 1) hor ( 31 * str[j] );
Для шахматных позиций традиционно используется метод Z-Obrist ключей. Он подразумевает, что для каждого поля, цвета и фигуры существует случайное число. Ключ позиции представляет собой сумму этих ключей.
Var rnd_key:array[white..black, pawn..king, 0..63] of int64;
For c = white to black do
For p = pawn to king do
For sq = 0 to 63 do
Rnd_tbl[c,p,sq] = random64();
Procedure insert_piece(var pos:position; c,sq,p:integer);
Begin
Pos.board[sq] := p;
Pos.color[sq] := c;
Pos.hash_key = pos.hash_key hor rnd_tbl[c,p,sq];
End;
Procedure remove_piece(var pos:position; c,sq,p:integer);
Begin
Pos.board[sq] = empty_square;
Pos.color[sq] = no_color;
Pos.hash_key = pos.hash_key hor rnd_tbl[c,p,sq];
End;

Простейшая хеш-таблица в шахматах может хранить только лучшие ходы.
Var hash_tbl:array[0..SIZE-1] of record
Side,depth:integer;
Move:Move_Type;
Hash_key:int64;
End;
Procedure Insert_Position(_side:integer; _key:int64;
_move:Move_Type;
_depth:integer);
begin with hash_tbl[ key mod SIZE ] do begin if _depth >= depth then begin depth = _depth;
hash_key = _key;
side = _side;
move = _move;
end;
end;
end;
Как видите, все несложно. Как только найден ход, улучшающий alpha, его можно вставить в хеш. Перед началом функции поиска нужно посмотреть, нет ли лучшего хода в хеше. Ходы главных изменений (оценка больше alpha но меньше beta можно хранить в хеше подольше, так как это самые ценные узлы и не должны перезатираться). Если вышла коллизия и хеш- ключ неправильно определил позицию, то нет ничего страшного, только лучший ход будет неверен.
Наша упрощенная хеш-таблица не имеет групп, а только входы. Она будет эффективно, если хеш-ключ дает хорошее распределение.
Если мы хотим использовать оценки из хеша, то нужно учитывать, что это является поистине неисчерпаемым источником ошибок в шахматных программах. Даже если нет коллизий ключей и мы храним компактное битовое представление позиции для сравнения, нам нужно учитывать:
8. Позиции равны только тогда когда имеют одинаковое фигурное расположение и одинаковые перемещения. То есть нам придется хранить информацию о доступности рокировок и возможности взятия пешкой на проходе.
9. Нужно делать корректировку матовых оценок в зависимости от глубины.
10. Перед использованием результата из хеша должна вызываться функция, определяющая повторы в игре.
Хеширование позволяет значительно ускорить поиск (особенно в эндшпиле). Ведь мы имеем фактически не дерево игры а граф. В одну позицию можно прийти различными путями.

BitBoard
В настоящее время модной стала техника битового представления позиции. Она позволяет представить позицию более компактно и эффективно выполнять некоторые операции.
Основой BitBoard техники служит 64 битовое число, где 1 бит представляет 1 поле доски.
Так как и бита могут быть только 2 значения, то и обозначать он может лишь (занято, свободно).
/* Тип BitBoard - 64 битовое число без знака */
Type BitBoard = LongDword; // unsigned long long, unsigned int64
Основные битовые операции:
// установить бит с номером sq
W = w or ((BitBoard)1 shl sq);
// сбросить бит
W = w and not ((BitBoard)1 shl sq);
// сбросить младший бит
W = w and (w-1);
//получить номер первого бита
Asm
MOV EAX, DWORD PTR w
OR EAX,EAX
JZ @M1 // младшее слово (первые 32 бита числа)
BSF EAX,EAX // в EAX номер первого ненулевого бита
Return EAX
@M1:
MOV EAX, DWORD PTR (w+4) // старшее слово числа
BSF EAX,EAX
ADD EAX,32
Return EAX
End;
Белые пешки в битовой нотации будут выглядеть примерно так:
1222222223 4 + + + +5 4+ + + + 5 4 + + + +5 4+ + + + 5 4 + + + +5 4+ + + + 5 4pPpPpPpP5 4+ + + + 5 7888888889 00000000 00000000 00000000 00000000 00000000 00000000 11111111 00000000
После хода e2-e4:
00000000

00000000 00000000 00000000 00001000 00000000 11110111 00000000
Маска всех белых фигур:
00000000 00000000 00000000 00000000 00000000 00000000 11111111 11111111
Пример кода, получающего номера полей с белыми фигурами:
W = white_pieces;
While w <> 0 do
Begin
Sq = get_first(w);
W = w and (w-1);
End;

Сингулярная эвристика продлений.
Слово сингулярный значит странный или единственный. Данная эвристика предусматривает углубленный просмотр некоторых вариантов с единственным ответом.
Реализаций ее может быть множество.
В шахматах бывают позиции, когда несмотря на выигрыш в материале, игрок не может выправить положение некоторое время и вынужден защищаться. Это, как правило, бывает при глубокой угрозе королю.
Как реализовать подобную, чисто шахматную модель поведения средствами AlphaBeta поиска? Практика показывает, что речь идет как правило, об ожидании второй отсечки за бета. Если оценка поиска достигла beta предела и есть только один ход, дающий этот результат, то выполняется поиск на глубину +1 для уточнения результата.
Мы должны понимать, что значат alpha и beta пределы вообще. Представим себе некоторый вариант выборочного поиска, который использует специальную функцию для получения предполагаемой оценки.
Function main_search(...):integer;
For each move do
Begin
Score = -selective_search(...);
If score > alpha then
Score = -main_search(...);
End;
Это стандартный выборочный поиск. Все узлы, предварительная оценка которых больше alpha являются кандидатами для более подробного рассмотрения.
Теперь давайте себе представим, что мы получили оценку меньше или равную alpha и предположительно, существует только один ход противника, дающий ему столь высокий результат. Велика вероятность того, что этот единственный ход ошибочен и если рассмотреть ситуацию глубже, то оппонент теряет а не приобретает. Нам потребуется специальная функция, выполняющая поиск всех вариантов кроме одного и функция выборочного поиска, возвращающая кроме оценки и лучший ход. Реализация может выглядеть примерно так.
./* ищет выборочно + единственный ответ */
Function main_search(depth,alpha,beta:integer; first_move:Tmove ...):integer;
If depth <= 0 then return Quies(alpha,beta);
Generate_And_Sort_Moves();
For each move do
Begin
Best_move = 0;
If Check() or Pawn_Move_Rank7() then //расширения поиска
Ext = 1

Else
Ext = 0;
Score = -selective_search(depth-1+ext, &best_move, -beta,-alpha, ...); // выборочный поиск, возвращает результат и найденный ход
If depth > 4 then
If Ext == 0 then
If score <= alpha then //поиск без одного хода на меньшую глубину
Score = -singular_search((depth-1+ext)/2, best_move, -(alpha+1),
-alpha, ...);
If (score > alpha) or ext then
Score = -main_search(d-1, -beta, -alpha, best_move, ...);
If score > alpha then
Begin
Alpha = score;
If alpha >= beta then break;
End;
End;
Return alpha;
End;
Если мы вместо выражения
((depth-1+ext)/2) используем (depth-1+ext), то (возможно) программа будет играть очень осторожно и везде видеть возможную угрозу.
Впрочем, приведенная схема только демонстрирует основную идею и многое зависит от тонкой настройки программы.
Может, вам покажется интересной идея отслеживать только материальную грань легальных ходов. Тогда при поиске второго легального хода нужно использовать окно alpha+PAWN_VALUE/2.
Количество возможных ошибок при реализации сингулярной эвристики может уступать только реализации хеш-таблиц. Например :
11. Использует ли функция singular_search недействительное перемещение? Если да, то она явно не ищет второй ход.
12. Что делать если предварительный поиск вернул оценку <= alpha, а лучшего хода нет?
Это может быть по причине использования результата из хеша, повтора позиций, отсечки недействительного перемещения и мало ли чего еще 

Выборочный поиск.
Мы рассмотрим только один вариант выборочного поиска. Их существует множество.
Недействительное перемещение, статическое отсечение и пр., тоже относятся к выборочному поиску.
Выборочный поиск по определению просматривает не все варианты и поэтому порядок ходов становится принципиальным. Просмотр каждого узла лучше начинать с осмысленного перемещения, а лучше и двух. Дело в том, что осмысленный ход установит более реалистичный alpha предел и поиск пойдет по другому.
Основная общая схема выборочного поиска может быть представлена как следующая:
Function search(...):integer;
For each move do
Begin
Score = -selective_search(...);
If score > alpha then
Score = -search(...);
End;
End;
В зависимости от того, высока или низка alpha, многие перемещения будут рассмотрены или отвергнуты.
Как же устроена функция selective_search? В простейшем случае не нужно отдельной функции и это есть вызов search() с глубиной d-1.
Const Min_Depth = 2
Function search(depth,alpha,beta:integer):integer;
For each move do
Begin
If depth <= Min_Depth then
Score = alpha+1
else
Score = -search(depth-2,-beta,-alpha);
If score > alpha then
Score = -search(depth-1,-beta,-alpha);
End;
End;
Общий принцип нашего выборочного поиска состоит в том, что нужно последовательно увеличивая глубину, достигнуть beta предела. Мы это делали только с глубиной d-1, но можно расширить этот принцип.
Const Min_Depth = 2

Var best_move:array[0..MAX_DEPTH] of Move_Type;
./* Ищет не все */
Function search(depth,ply,alpha,beta:integer):integer;
Var score, D:integer;
If check() then depth = depth+1;
If depth <= 0 then return Quies(alpha,beta);
Generate_And_Sort_Moves();
Pick_Best_Move( best_Move[ply] );
For each move do
Begin
If depth <= Min_Depth then
Score = alpha+1
Else begin
Score = alpha+1;
D = max(min_depth, depth/2+1);
While (D < depth-1) and (score > alpha) do
begin
Score = -search(D,ply+1,-beta,-alpha);
D = D+1;
End;
End;
If score > alpha then
Score = -search(depth-1,ply+1,-beta,-alpha);
If time_up then break;
If score > alpha then
Begin
Alpha = score;
Best_move[ply] = move;
If alpha >= beta then break;
End;
End;
Return alpha;
End;
Обратите внимание, что поиск каждого узла начинается с лучшего хода, полученного при d-1, кроме сложных позиций, где alpha увеличить не удалось и программа пытается это сделать с глубиной +1.

Недействительное перемещение.
Эвристика недействительного перемещения в свое время произвела настоящий фурор в шахматном программировании. Это связано, в первую очередь, с программой Fritz, которая очень точно анализировала сложные тактические позиции на сравнительно маломощных машинах.
Что же из себя представляет эта эвристика? Она использует тот же принцип статического отсечения. Считается, что в любой нормальной, где нет опасности цунгцванга, можно найти ход, не ухудшающий текущего положения.
13. Делается пропуск хода и очередь хода передается противнику. Поиск выполняется на меньшую глубину.
14. Полученный результат рассматривается как минимум возможной оценки. Если наш минимум уже сравнялся с beta, то поиск можно досрочно прекратить и вернуть beta/
15. Поиск недействительного перемещения выполняется до основного поиска. Так как глубина поиска сокращается существенно (3,…) и число отсечек за beta довольно велико, то общее число исследуемых позиций сокращается и программа может сосчитать глубже.
16. Поиск недействительного перемещения позволяет сосчитать глубже в среднем на 1-2 полухода за тоже время. Кроме того, он проводит какоето подобие статического отсечения и позволяет сгладить эффект горизонта. Эффект горизонта возникает из за того, что программа не успевает до конца исследовать возможные тактические осложнения и поэтому будет неверно ориентироваться в игре.
17. Поиск недействительного перемещения немного изменяет общий стиль игры. Если вызывать недействительное перемещение только по достижении определенной глубины (2 или 4) полухода, то это приведет к лучшему планированию игры.
/* Поиск с отсечкой по результату недействительного перемещения */
Function AlphaBeta(depth,alpha,beta,side,xside,is_null_search:integer):integer;
Var
Score, best:integer;
Begin
If depth <= 0 then
Return Evaluate(side);


Поделитесь с Вашими друзьями:
  1   2


База данных защищена авторским правом ©nethash.ru 2017
обратиться к администрации

войти | регистрация
    Главная страница


загрузить материал