Всем привет, скажите почему код http://www.geocities.com/axchess/firstchess.c не компилируется и выдает ошибку \firstchess\firstchess.c(292) : error C2065: 'false' : undeclared identifier?

false нет в обычном си, переименуй файл в *.cpp)

Получилось ! Спасибо.
Добавлено спустя 42 секунды
А что в C вместо true\false ?

Не ноль/ноль.
Хотя в «новом» стандарте C99 появился bool, можешь попробовать сделать «#include <stdbool.h>», но не все компиляторы это поддерживают…

Алгоритмы шахматных программ

--------------------------------------------------------------------------------

Часть I. Минимакс.
Для начала рассмотрим более простую игру, например, крестики-нолики на доске 3х3. Рассмотрим начальную позицию. Тут у первого игрока (пусть это будут крестики) имеются 9 ходов (симметрию игнорируем). На каждый из них у соперника имеется 8 ответов, в свою очередь на каждый из них - по 7 ответов у крестиков и т.д. Максимальная длина игры - 9 полуходов (т.е. ходов одного из соперников), но она может кончиться и побыстрее, если кто-то выиграет.

Возьмём листок бумаги и сверху нарисуем начальную позицию. Так как из неё возможно 9 ходов, проведём из неё 9 чёрточек (ветвей). В конце каждой ветви нарисуем позицию, которая получается после этого хода, и в свою очередь проведём из неё ветви - ходы, возможные из данной позиции. И так далее. Полученная структура называется деревом, ибо (1) у неё есть корень - начальная позиция, (2) у неё есть листья - позиции, из которых не идёт ветвей, ибо один из игроков победил или случилась ничья, и (3) она отдалённо похоже на дерево, если лист бумаги перевернуть. Крестики-нолики - простая игра, её дерево должно уместиться на (большом) листе бумаги, но можно себе представить так же нарисованное дерево для шахмат (вроде бы есть всего 10**50 или около того различных позиций, и правило 50 ходов ограничивает максимальную длину партии ~4000 ходов). Разумеется, для такого листа бумаги не хватит всех атомов во вселенной, но представить такой лист всё равно можно (я, во всяком случае, могу).

Теперь припишем каждому листу его оценку. Пусть выигрыш крестиков будет -1, ноликов - плюс 1, а ничья будет нулём. Начнём <поднимать> оценку вверх по дереву - рассмотрим вершину, непосредственно стоящую над листом (терминальной позицией). Из неё ведёт несколько ветвей (в крестиках-ноликах ровно одна, но это не важно). Представим, что ход сейчас - крестиков. Он заинтересован в получении -1, поэтому из нескольких вариантов он выберет вариант с минимальным значением (-1, если возможно, а если нет, то хотя бы 0). Таким образом, он выберет минимальную оценку из тех, какую имеют его <потомки>, и припишет её этой вершине.

Уровнем выше - очередь хода <ноликов>. Он, в свою очередь, заинтересован в получении +1, поэтому он будет максимизировать полученную снизу оценку.

В конце концов мы поднимем оценку до корня. В случае крестиков-ноликов это будет, разумеется, 0, ибо теоретическим результатом крестиков-ноликов при оптимальной игре обоих игроков является ничья. Что является теоретическим результатом шахмат науке неизвестно.

Разумеется, имея нарисованное дерево игры, играть очень легко - крестики должны выбирать ход, ведущий из текущей позиции в позицию с минимальной оценкой; нолики - в позицию с максимальной. Как легко понять, описанный алгоритм и есть обещанный минимакс.



Часть II. Альфа-бета.
Внимательные читатели должны были догадаться что минимакс будет работать не только на деревьях с оценками плюс/минус один, но и на деревьях, листьям которых приписаны просто действительные числа. В дальнейшем мы будем рассматривать именно такие деревья (для объяснения основных алгоритмов я буду говорить о деревьях, забыв на время о собственно играх). Кроме того, я сосредоточусь именно на определении теоретического результата игры, т.е. на подъёме оценки вверх по дереву.

Минимакс - очень трудоёмкий алгоритм. Для определения теоретического результата игры размечается абсолютно всё дерево. Вопрос: нельзя ли, сохранив математическую корректность минимакса, обходить поменьше?

Оказывается, можно. Алгоритм называется альфа-бета. Легко доказать, что он даёт те же результаты (не бойтесь, я этого делать не буду). Идея его, если объяснить на пальцах, такова:

Пусть есть корень, у него - 2 потомка, у каждого из них - по 3 потомка-листа. В корне - очередь хода мина, соответственно, в вершинах второго уровня - ход макса. Листам, которые потомки левого поддерева, приписаны оценки 0, 5, 10. Так как в вершинах второго подуровня мы максимизируем, левому поддереву припишем оценку 10.

Начинаем рассматривать правое поддерево. Пусть у самого левого листа оценка 100. А теперь - внимание! Мы знаем, что уровнем выше мы будем максимизировать. Это означает, что оценка *всего правого поддерева* будет уж не меньше 100, т.к. оставшиеся листья могут эту оценку только поднять. Кроме того мы знаем, что в начальной позиции мы будем минимизировать, и значит выберем левое поддерево, оценка которого 10.

Итого, мы получили оценку всего дерева, рассмотрев всего 4 позиции из 6. Шахматная аналогия - предположим, что я рассмотрел один из своих ходов, и обнаружил, что после всех ответов противника позиция равная. Я посмотрел, что происходит после другого моего хода, и обнаружил, что одним из своих ответов противник выигрывает коня. Рассматривать другие его ответы уже не имеет смысла - этот свой ход я уже не сделаю.

Просьба обратить внимание, что нам повезло, что в правом поддереве оценку 100 имеет самый левый лист. Будь он правым, и если при этом оба левых имеют оценку 7, нам пришлось бы обойти все 6 листьев. В наихудшем случае (мы всегда рассматриваем поддерево/лист с наилучшей оценкой в последнюю очередь) альфа-бета вырождается в минимакс. В наилучшем случае (наилучшее поддерево всегда рассматривается первым) рассматривается (очень грубо) 2*(sqrt(количества вершин, рассматриваемых минимаксом)).

Альфа-бета является алгоритмом с - ветвь отсекаются только после того, как хотя бы одного потомка оценили, и убедились, что значение этой ветви не повлияет на итоговый результат.




Часть III. Применение теории к практике.
Разумеется, для реальных игр (шахмат, шашек, го) всё дерево машина обойти не сможет. Поэтому идут на жульничество.

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

Во-вторых и в главных, точная оценка заменяется на приближённую. А именно, после перебора на некоторую глубину, если не случилось мата или форсированной ничьи, вместо того, чтобы перебирать дальше, мы зовём оценочную функцию, которая приписывает текущей позиции (а точнее, всему поддереву, начинающемуся с текущей позиции), некоторую оценку. Как эта функция устроена - чуть позже, а пока главное: тут мы бесповоротно порвали с теорией, ибо оценочная функция есть нечто приближённое. Вот это и есть основное жульничество - альфа-бета была научно обоснована совсем в других условиях, и почему она после введения в неё оценочной функции работает в реальных играх, не совсем понятно (точнее говоря, есть сколько угодно работ на эту тему, но мне они представляются неубедительными). Более того, искусственно создан целый класс игр, где альфа-бета в таких условиях не работает.

Как устроена оценочная функция? Во-первых, надо просто сосчитать материал. Простейший вариант: пешка - 1, конь и слон - 3, ладья - 5, ферзь - 9.

Во вторых, надо добавить позиционную оценку, и это есть самое сложное. Факторов много, в шахматных книжках приведены далеко не все, и главное - там сказано <это есть хорошо, а то плохо>, а нам надо <это есть плюс половина, а то - минус три четверти>. Соответственно, приходится сначала факторам приписывать веса с потолка, а потом отлаживать, вручную или пытаясь оптимизировать функцию в пространстве размерности несколько тысяч.

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

Таким образом, получаем позиционную оценку белых, складываем с материалом белых, делаем то же самое для чёрных, вычитаем одно из другого, и всё сведено к одному числу. Красота!

К сожалению, не всё так просто. Первые программы использовали только что описанный алгоритм - перебор на фиксированную глубину с вызовом там оценочной функции (если раньше мат не случился). И немедленно выяснилось, что мы можем прекратить перебор, например, в середине размена, или при "висящем" ферзе, или когда на доске стоит мат в один ход, и тот факт, что у атакующей стороны не хватает ладьи, не имеет никакого значения. Были попытки учитывать всё это в оценочной функции, но она тогда становилась безумно сложной, и медленной. На каждый починенный таким образом случай начинало приходиться десять других, где замедление программы вследствие более медленной оценочной функции приводило к недостаточной глубине перебора и ещё худшей игре. Кроме того, программа с маниакальным упорством пытается отсрочить свои неприятности, получая взамен худшие. <Ага, я перебираю на 7 полуходов, и вижу, что теряю слона. А вот отдам-ка я вот эту пешку, и тогда слона противник возьмёт на 4 полухода позже, получится 11, я и не увижу. Итого минус 1, а не минус 3>. Разумеется, при более глубоком переборе программа бы обнаружила, что в итоге у неё будет минус 4, но времени перебирать глубже нет. Это явление называется <эффектом горизонта>, ибо программа стремится выпихнуть неприятности за горизонт видимости (или горизонт событий).

Попытки использовать селективные методы провалились с ещё большим треском. Не удаётся понять, как человек играет в шахматы, и попытки сделать программы с "forward pruning" - отсечениями ветвей дерева без их предварительного рассмотрения, исходя из чисто шахматных принципов, проваливаются. Всегда находятся позиции, где программа отсекает нужный ход (<выплёскивает воду месте с ребёнком>).

В конце концов стало понятно, что оценочную функцию можно звать только в спокойных позициях. Поэтому в конце основного перебора вставили ещё один, упрощённый, где рассматриваются только взятия, превращения, и, возможно, шахи и ответы на шах. Так как таких ходов немного, <форсированный вариант> (так это называется) замедляет программу всего лишь на 20-50%, а сила игры резко увеличивается, т.к. программа не пытается оценить острые позиции.

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

Вот какова была ситуация в начале и середине 70-х.




Часть IV. Улучшения.
Как уже было сказано, за 40 лет никакой замены альфа-бете не найдено. В этом смысле наиболее печальна история Ботвинника. В течении 20 лет он занимался созданием шахматной программы. Он свято верил, что будучи чемпионом мира по шахматам и одновременно хорошо понимая программирование, он сумеет создать программу, которая будет играть на уровне чемпиона мира. Итог печален - программа так никогда не заиграла (по этому поводу кто-то хорошо сказал <Ботвинник только думает, что он знает, как он думает>). Что ещё хуже, Ботвинник напечатал статью с описанием алгоритма в журнале International Computer Chess Association. Статья содержала результаты анализа нескольких позиций, якобы выполненных программой. Независимый анализ показал, что эти результаты являются фальсификацией - они не могли быть получены с использованием алгоритма Ботвинника.

Тем не менее, все эти годы качество игры шахматных программ улучшалось. Частично прогресс обьясняется быстрым развитием аппаратуры - персональные компьютеры по ряду параметров достигли уровня суперкомпьютеров конца 70-х (хотя по ряду параметров всё ещё серьёзно отстают). Частично же <виновато> развитие алгоритмов - прорыва не было, но было множество эволюционных улучшений. Каковы главные из них?

(1) Использование библиотеки дебютов. Дебютная теория в шахматах хорошо разработана, и только естественно, что программы стали её использовать. Более того, используют они её лучше, чем гроссмейстеры, т.к. запомнить несколько миллионов позиций для машины проще простого.

(2) Использование баз данных с целиком просчитанными эндшпилями. Сейчас реальный предел для персонального компьютера - 5-фигурные эндшпили (считая королей). Используя такие базы данных, программы играют простые эндшпили безупречно. Более того, современные программы могут во время перебора вариантов <дотянуться> до базы данных из позднего миттельшпиля, когда на доске находится ещё 10-15 фигур. Скромно замечу, что к созданию наиболее широко распространённых баз эндшпилей приложил руку я.

(3) Думанье во время хода противника. Мы сделали ход и теперь задумался противник. Зачем времени пропадать? Выберем наиболее разумный с нашей точки зрения ход, который он может сделать, и начнём думать над ответом на него. Если он сделает другой ход - ну и леший с ним, всё равно не наше время было. Это - наиболее простой вариант использования времени противника, и он же наиболее эффективный, т.к. хорошие программы правильно предсказывают ~70% ходов противника.

(4) Различные эвристики, которые помогают отсортировать ходы в процессе перебора. Как уже отмечалось ранее, альфа-бета очень чувствительна к порядку, в котором анализируются ходы. При хорошем порядке она быстрее, причём быстрее принципиально. При этом алгоритм всё равно остаётся экспоненциальным - перебор на N+1 полуходов работает в разы медленнее, чем на N полуходов, но по крайней мере возводимое в степень число ощутимо уменьшается. В типичной шахматной позиции возможно примерно 40 ходов, и для перебора на N полуходов минимаксу (он же альфа-бета с наихудшим упорядочением ходов) надо рассмотреть 40**N позиций. Альфа-бете с наилучшим упорядочением ходов надо рассмотреть примерно 6**N позиций - разница принципиальна. Эвристики применяются различные, например: первым делом попытаться съесть только что ходившую фигуру противника (она работает, т.к. большинство рассматриваемых ходов - полнейший идиотизм). Другая полезная эвристика (с меньшим приоритетом) - попытаться сделать ход, который был лучшим у соседа слева (она основана на том, что в похожих позициях наилучший ход часто один и тот же). Имеются ещё несколько эвристик, но надеюсь, что идея в целом понятна.

(5) Итеративное углубление (iterative deepening). В реальной игре у программы имеется какое-то время на каждый ход, и им надо с умом распорядиться. Просто начинать перебор на фиксированную глубину, как делали ранние программы, неразумно - в сложной позиции с большим количеством разменов и/или шахов будет много вариантов, которые будут просчитываться очень глубока из-за <углублений>, и программа может не успеть выполнить перебор. А одной из особенностей альфа-беты является то, что результатом незаконченного перебора воспользоваться нельзя - нет никакой гарантии, что найденный к моменту прерывания наилучший ход является хоть сколько-нибудь разумным. С другой стороны, в какой-нибудь закрытой позиции с малым количеством возможных ходов (branching factor) перебор может закончиться неожиданно быстро. Идея итеративного углубления состоит в том, что программа сначала производит перебор на глубину 1. Осталось время - перебираем на глубину 2. Осталось время - на глубину 3. И так далее. Разумеется, при этом приходится часть работы делать заново, но тут понимает как раз экспоненциальный характер алгоритма. Следующий перебор занимает (грубо) в 6 раз больше времени, поэтому мы заново делаем максимум 1/6 работы. Зато у нас всегда есть ход от предыдущей итерации, которым мы можем воспользоваться, если нам придётся прервать текущую. Возможны дальнейшие оптимизации - например, не начинать новую итерацию, если мы съели больше половины отведённого на думанье над этим ходом времени, ибо всё равно почти наверняка не успеем.

(6) Хэш-таблицы (transposition tables). В шахматах мы имеем не дерево игры, а граф - очень часто после перестановки ходов мы получаем одну и ту же позицию. Возникла простая идея - занять всю память машины, которая иначе бы не использовалась, под запоминание уже рассмотренных позиций. Для каждой позиции надо хранить её оценку (точнее, оценку поддерева под этой позицией), глубину перебора, наилучший ход, и некоторую служебную информацию. Теперь, начав разбирать позицию, надо взглянуть - а не встречали ли мы уже её? Если не встречали, то поступаем как раньше. Если встречали, то смотрим, на какую глубину мы её раньше разбирали. Если на такую же, как нам надо сейчас, или более глубокую, то можно воспользоваться старой оценкой и сэкономить время. Если же на меньшую, то мы всё равно можем воспользоваться частью информации, а именно наилучшим ходом. Лучший ход для глубины N может оказаться лучшим и для глубины N+1. То есть, кроме своего изначального предназначения, хэаш-таблица оказывается полезна и для упорядочения ходов. Тут ещё неожиданно помогает итеративное углубление - когда мы начинаем следующую итерацию, хэш-таблица оказывается заполнена информацией от предыдущей, и до какого-то момента (до глубины 1) все позиции просто есть в ней, с наилучшим ходом на глубину N-1. Программа, использующая итеративное углубление и хэш-таблицы, часто выполняет все итерации от 1 до N в несколько раз быстрее, чем если бы она сразу начала итерацию N, т.к. с вероятностью 75% она всегда первым выбирает наилучший ход, а с вероятностью ~90% наилучший ход оказывается в числе первых трёх рассмотренных.

(7) Пустой ход (null move). В шахматах очерёдность хода очень важна, и тот игрок, который мог бы сделать два хода подряд, имел бы огромное преимущество. Возникла очень простая идея - пусть игрок A сделал свой ход и теперь очередь B. У него есть преимущество - например, лишний конь. Надо рассмотреть поддерево на глубину N. Игрок A говорит <я не буду делать ход, пусть B делает два хода подряд, зато поддерево после этого мы посмотрим до глубины N-2 а не N-1, как было бы после моего хода>. Мы выполняем этот перебор на меньшую глубину, и если у A всё равно преимущество, мы решаем <так как на самом деле он будет делать ход, наверное на самом деле его преимущество будет ещё больше>. То есть мы сэкономили, разобрав не настоящее поддерево до глубины N, а другое до глубины N-1 - напоминаю ещё раз, что перебор экспоненциален, так что выигрыш очень значителен. Иногда оказывается, что игрок B, имея два хода подряд, может восстановить баланс - пустой ход не сработал, придётся перебирать всё честно до глубины N. Опять-таки, мы потеряли не очень много времени, т.к. перебирали до глубины N-1. Разумеется, пустой ход, являясь эвристикой, может и наврать - например, в цугцванге право хода лишь мешает. Но в реальной игре цугцванг встречается лишь в эндшпиле, а в эндшпиле пустой ход можно и не использовать. Пустой ход оказался очень серьёзным улучшением, т.к. он позволяет сократить время перебора на глубину N с 6**N до (25-3)**N.

(8) Единственный ответ (singular extension). Стандартная альфа-бета прекращает анализ позиции, как только найден ход, который вызовет отсечение. Так как у нас не полное дерево игры, а мы используем оценочную функцию, может оказаться, что мы проврались, и никакого отсечения нет. Соответственно, мы думали, что в этой позиции у нас лучше, а на самом деле мы теряем ферзя. Идея единственного ответа состоит в том, что найдя один хороший ответ, мы не отсекаем сразу всё поддерево, а продолжаем перебор, пока не найдём второй хороший ход. Если же мы его не нашли, то позиция анализируется заново, на сей раз на глубину N+1. Очень помогает в тактических позициях - программа начинает видеть комбинации на несколько ходов раньше, но резко замедляет перебор и поэтому используется только программами, работающими на суперкомпьютерах.

О текущем состоянии дел в компьютерных шахматах - в следующий раз.

ниасилил

iliapan Чрезвычайно умный комментарий, спасибо.

извини, не люблю подобные комменты, но просто непонятно зачем выложил?

и скажи чем помочь

Запостил он это, видимо, потому, что тема называется «Программирование шахмат», и в скопированной им статье есть интересная информация по теме. Эта тема в данный момент тебя не интересует, вот ты и «ниасилил». Комментировать этот факт, да еще и с нарушением, совершенно излишне)


Мне? Мне ничем помогать не надо, это не моя тема Завязываем с оффтопом

Чтоб осилили. Мне, например, было чрезвычайно интересно

Думаю, лучше закрыть.