Открыть список
Как стать автором
Обновить

Комментарии 45

Я сам писал шахматную программу, поэтому не удержался от пары комментариев:
1. Про поиск в ширину автор пишет полную чушь, дерево, в принципе не надо хранить, если у вас список ходов из позиции детерминирован, то важен только текущий путь и оценки, для механизма отсечения.
2. Автор искажает факты, только начиная с ключевого пункта "(при этом ветки со взятиями и шахами могут достигать заметно большей глубины)" из раздела «Углубление поиска» его программа, действительно смогла играть, до этого она могла просчитвать мат в пределах видимости, но ни о какой игре речь не шла.
Поясню дополнительно: если рассматривать любую позицию, то почти всегда возможно взятие вашей фигуры, если не ваш ход или вы можете взять достаточно весомую фигуру противника, а расплата, которая наступет дальше, находится за горизонтом события, поэтому программа, просчитывающая на определённую глубину не может В ПРИНЦИПЕ адекватно оценивать никакую позицию, все оценки — коту под хвост, она постоянно будет приписывать либо вычитать сильную фигуру, чего не будет случаться в реальности.
Статья выглядит довольно ладной, но, сдаётся мне, что автор нифига не писал (особенно, учитывая отсылки к дерменизму: вы можете просчитать на нужную глубину, только имея безлимит по времени, имея же временной лимит, вы просто обязаны реализовать просчёт во время обдумывания хода соперником и ни о каком детерминизме речь уже не идёт), просто посмотрел движки, пособирал инфу и выложил нам компиляцию того, что надо сделать.

P.S. Ну и тот, кто действительно писал движёк, знает чем отличается минимакс, от альфа-бета, про который в статье даже не упоминается. Исходники не смотрел, вроде бы в ТурбоВижн 19xx лохматого года идёт движёк шахмат, для общего развития.
Шахматный движок в 328 байт: в целом, ценность шахматного кода преувеличина
Спасибо за статью о Дельфи/Lazarus.
дерево, в принципе не надо хранить

А как его визуализировать, если не хранить?


сдаётся мне, что автор нифига не писал

А код на гитхабе, видимо, сам-собой возник? :-)

А как его визуализировать, если не хранить?

Вы же не отображаете всё дерево, а только путь, даже если оно интерактивно, показать прощёлкнутую ветку — никаких проблем нет, это несколько деятков позиций.

А код на гитхабе, видимо, сам-собой возник? :-)

Не собираюсь вникать в то, откуда взялся код и насколько он оригинален.

Ну надо где-то брать оценки для отображаемой ветки. Пускай позиций отображается немного, но их оценка формируется из большого количества листьев. Может быть с альфа-бетой посчитать их "на лету" было бы достаточно быстро, не знаю. Я выбрал простой вариант.

С оценками — возможно, но в реальности, важен просчитыаемый путь и оценка, в динамике. Вот как это выглядело в классике (Super Chess 3.5, ZX Spectrum 1984г):
Super Chess 3.5
откуда взялся код и насколько он оригинален.

Осмелюсь предположить, что код с поиском в ширину — достаточно уникален. Кто ж станет такое писать. Зато он позволяет прочувствовать как именно играет AI с полным перебором на фиксированную глубину. Если бы его не написал — это осталось бы загадкой :)


Кстати, первый коммит в репозитории — как-раз старая версия, которая играет детерминированно и думает только на своём ходу. В этом нетрудно убедиться.

Все, в частности — я. Поиск в ширину, это первое понимание того, как вообще может работать выбор в дереве лучшего значения (когда они «лучшие» существуют все одновременно и уровнем ниже происходит естественный выбор), далее приходит понимание того, что всё дерево не нужно
а нужен только путь
image

Хм, тогда непонятно в чём суть претензии, что я начал с поиска в ширину, если все с этого начинают :-)

Суть претензии в логических и временных несостыковках, вашего повествования, а не в фактах по отдельности. А так же неразборчивость в существенных и несущественных деталях. Ну это типа, как, сейчас мы нарисуем сову.

P.S.
— Скажите, а правда, что Кац выиграл в лотерею миллион?
— Правда. Но не Кац, а Рабинович. Не в лотерею, а в карты. Не миллион, а сто рублей. И не выиграл, а проиграл.

В Turbo Vision не видел, но видел OWL Chess — довольно хорошая программа на Borland Pascal под Win 3.1 Исходники доступны. Но задача изначально стояла написать с нуля, а не изучать другие движки. Изучение чужих движков практически не даёт опыта решения задач, возникающих в процессе работы над AI других игр.

Создание игровой программы — это чертовски интересный процесс.
Мы с отцом пилили программу по русским шашкам «Магистр» примерно с 1992 ​по 2003 год.
И кстати, что интересно, последняя самая сильная версия была тоже на Delphi (генератор ходов правда был на встроенном в Delphi ASMе).

К 2003 году у нас уже была практически полная 7-я фигурная база окончаний (за исключением всякой экзотики типа 6 против 1).

Потом мне уже стало как-то неинтересно и я забил, а отец до сих пор пытается полностью решить такую разновидность шашек как «поддавки».

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

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

Вспоминаю те годы с большой теплотой, наверное это был мой самый интересный проект в программировании за 30 лет.
Сам я не шахматист и даже не сказать что любитель шахмат

Это серъезная проблема (общая проблема велосипедостроения, не «в боевых условиях» или без опыта на теор.данных).

Бонус/штраф
Для каждого игрока:

Подсчитать стоимость фигур: конь — 3, ладья — 5 и т.д. Начальная стоимость пешки — 1, но она растёт по мере её продвижения.

Бонус за сделанную рокировку, штраф за потерю возможности рокировки, штраф в миттельшпиле за невыведенные фигуры (коней и ладьи в углах). Штраф за сдвоенные пешки и бонус за захваченные открытые линии.

Определение какие поля находятся под боем и кем. Это медленная операция — основная часть времени выполнения оценочной функции тратится именно здесь. Зато польза от неё колоссальная! Незащищённая фигура под боем на ходу противника — минус фигура. Защищённая — минус разность стоимости фигур. Это позволяет получить эффект углубления поиска на 1-2 уровня.

Если остался один король: штраф за расстояние от центра доски и штраф за расстояние до короля противника. Такая формула в эндшпиле заставляет AI стремиться прижать короля противника к краю доски, т.е. получить позицию, из которой можно найти возможность поставить мат.

Итоговая оценка =


А другие тактические приемы?
бонусы: форпост, захват центра, рентген, связка, преимущества двух слонов, король в оппозиции, захват 2й/7й горизонтали…
штрафы: ослабление полей (ч. или б.), разорванная пешечная цепь, глупый слон, потеря темпа…

Как в эндшпиле матовать конем и слоном?
Это серъезная проблема (общая проблема велосипедостроения, не «в боевых условиях» или без опыта на теор.данных).


Текущие подходы уже и не используют такие тактические приемы, alphazero/muzero и подобные подходы похоже работают лучше.
Пиар для Гугла конечно, они же не в бизнесе шахматных движков, но модель которая [само]обучалась только очень небольшое время без баз и десятилетиями отточенных тактических приемов и даже не заточенная на шахматы, как минимум сравнима с другими SOTA программами.

Захват центра — через небольшой бонус за количество полей под боем, за 7 горизонталь тоже.
Но тут есть проблема: вся эта куча параметров — как их определить: на глаз, по ощущениям?
Это работает пока AI играет на таком уровне, что очевидно где решение правильное, а где — ошибка. А дальше уже нужны другие методы типа генетической оптимизации. В шахматах это нелегко, из-за того, что партии длятся долго и провести миллион партий для оптимизации параметров — дело затратное.

Я вот думаю свой движок попробовать на GPU распараллелить. Только надо придумать как. Наверное, стоит каждый переход на уровень вниз запустить как поток на GPU. Но тогда большая часть из них нифига не отсечётся — ведь отсечение происходит на запускающем уровне выше по результатам возврата из веток ниже. Надо подумать.

Я провел несколько партий против AI на chess.com


А как вы подключили туда движок? У вас UCI поддерживается?
Я свой на Arena запускал для тестирования.

GPU сильно уступает в математических вычислениях. Эффективно будет только, если создать на GPU сотни и сотни потоков

А я и собираюсь создать на пару миллионов потоков. :) Вопрос только в том, чем их загрузить.
Возможно, будет иметь смысл на первых нескольких полуходах собрать базу ходов и все их отправить уже дальше считаться на GPU. Потом посмотреть, что вернёт GPU и выбрать лучший ход из этих миллионов.
Возможно, стоит хранить большую часть данных в памяти GPU. Тогда, думаю, легче будет распараллелить
А там хранить-то особо нечего. :) Всё ж рекурсивное.
Хэш позиций, отсортированные ходы для них. Вообще получаем батч позиций, где нужно сгенерировать ходы. Генерим. Получаем батч позиций для оценки. Оцениваем. Загрузить в общем-то не проблема, у тебя уже на 3–4 полуходе будут достаточные батчи.
Там всего сотня мегабайт уйдёт на это всё.
На что уйдёт? Если исходить из скорости генерации миллион позицию в секунду (а это примерно одно ядро CPU) и 100 байт на позицию, то сотня мегабайт в секунду и будет уходить. А на GPU мы хотим ещё получить boost, значит будет быстрее.

Тут проблема в общем хеше позиций. Не видно, как эффективно использовать приватную память, а с глобальной скорость будет падать…
На кэш уйдёт.

и 100 байт на позицию,


Ничего подобного. 64 бита зобрист-ключ и 4 байта оценка позиции для данного ключа. Всё.

то сотня мегабайт в секунду и будет уходить.


Не будет. ;) Кэш общий.
А сортированный список ходов? Это очень важно с точки зрения перфоманса. А оценка позиции нам в общем-то и не сильно нужна.
Этот список ходов для текущей позиции на доске. Он весьма мал.
Я к тому, что для миллиона потоков в GPU нужно снизить кол-во обращений в ОЗУ, иначе профита не будет
В ОЗУ процессора или видеокарты? Первое, насколько я помню CUDA (а помню так себе), вообще невозможно — поток GPU не умеет работать с ОЗУ процессора.
В ОЗУ кончено не видеокарты. Суть в чем, алгоритм твой будет хранить всё в ОЗУ и ты собираешься отдавать GPU работу, но во время работы нужно обращаться к тому, что хранишь.
Я предлагаю тебе использовать по полной ОЗУ видеокарты в программе. И тогда потоки в GPU будут эффективнее, т.к. ты сможешь себя не ограничивать там и отдавать потокам более значимую работу.
В противном случае, ты будешь отдавать мелкую работу миллионам потоков, т.к. им просто напросто не с чем работать, т.к. да, из CUDA нельзя получить доступ к «внешней» ОЗУ.
но во время работы нужно обращаться к тому, что хранишь.


Нет. Каждый поток на GPU будет независим от остальных и просчитывает всю свою ветку со всеми частями, как если бы игра началась с его позиции. Что касается кэша, то им вообще можно пожертвовать (при миллионе потоков — легко). В этом случае расход памяти вообще околонулевой, а коллизий нет вообще.
Проблема только в том, что этот миллион потоков отвечает всего нескольким дополнительным полуходам. Стоит ли овчинка выделки, вот вопрос.
Это совсем грустно и неэффективно. И без кэша… Ты понимаешь, зачем нужен кэш? Альфа-бета перебор очень зависим от порядка просмотра ходов. Если у нас порядок ходов от самого плохого к лучшему, нам надо просмотреть все позиции на заданной глубине (экспоненциальный взрыв). Если у нас порядок ходов от лучшего к худшему, то большая часть вариантов отсекается, и у нас что-то вроде логарифма.

Поэтому движок обычно считает на глубину N, сохраняет как можно больше нод в хеше вместе с порядком ходов от лучшего к худшему. А потом считает на глубину N+1 при этом максимально использует результаты, полученные на глубине N (в первую очередь смотрим ход, которым был лучшим на глубине N).

Наверное, будет лучше смотреть в направлении методов MCTS, они лучше отвечают архитектуре GPU
Прочти мою статью про шахматный движок и увидишь, как всё это на самом деле работает и почему всё не так, как ты полагаешь. И именно поэтому отключив кэш сильной просадки скорости не будет. Late Move Reduction сокращает варианты гораздо (ГОРАЗДО!) эффективнее любого кэша. А кэш это так, чуток быстродействия добавить.
Возможно, но в любом случае Stockfish достаточно неплохо ест память, и есть рекомендация выделять 1G per thread. Что он хранит?
Он там хранит кэш. Польза от кэша, разумеется, есть. Просто она не так велика, как кажется (там общее количество позиций таково, что попадание в кэш не так уж часто, но оно есть).
Тут интересно APU заюзать, там вроде CPU и GPU разделяют память.
А как вы подключили туда движок? У вас UCI поддерживается?

Никак — вводил ходы вручную.

А у вас там ошибок в программе нет?
А то что-то странное творится:
1 Кb1-c3 d7-d5
2 Кg1-f3 d5-d4
3 Кc3-b5 c7-c5
4 e2-e3 Кb8-c6
5 e3:d4 c5:d4
6 c2-c3 d4:c3
7 d2:c3 Сc8-e6
8 Сc1-f4 Фd8:d1+
9 Лa1:d1 Лa8-c8
10 Кb5-c7+ Лc8:c7
11 Сf4:c7 Кg8-f6
12 Сf1-b5 Кf6-d5
13 Сc7-g3 a7-a5
14 Кf3-e5 Кd5-b6
15 Кe5:c6 b7:c6
16 Сg3-c7 f7-f5
17 Лd1-d8+ Крe8-f7
18 Сb5:c6 Кb6-c8
19 0-0 Кc8-d6
20 b2-b3 g7-g5
21 Сc7:d6 e7:d6
22 Лf1-e1 Лh8-g8
23 Лd8-a8 f5-f4
24 Лa8:a5 Лg8-g6
25 Сc6-e4 Лg6-h6
26 Лa5:g5 Сf8-g7
27 Лe1-d1 Сg7-e5
28 g2-g3 f4:g3
29 f2:g3 Крf7-f6
30 h2-h4 Сe6:h3
31 c3-c4 Крf6:g5


Пешка пошла с h2 в h4. Потом слон с e6 на h3.
А потом я вижу отсутствие пешки на h4! Слон её съел? А каким волшебством?
Также непонятно, почему выбрав ход чёрных и запустив AI игра начинается с хода чёрных! Но я-то жду, что AI походит белыми. Как в таком случае играть чёрными?
Ну и ещё долго думает и отлично кушает память. :)
Ну и сообщение о сбое тоже наблюдал один раз. :)
Пешка пошла с h2 в h4. Потом слон с e6 на h3.
А потом я вижу отсутствие пешки на h4! Слон её съел? А каким волшебством?

Дык взятие на проходе.


AI играет той стороной, которая вверху. Если перевернуть доску — он будет играть белыми.


А ошибки, конечно, есть. Код после доработок сырой. И по-хорошему надо ещё разок отрефакторить и оттестировать. Но это выльется в ещё пару дней работы, результат которой лично для меня никакой ценности уже не составит.

Дык взятие на проходе.


Слоном?! :O

Взятие на проходе (фр. en passant — на проходе) в шахматах означает специальный ход пешки, при котором она берёт пешку противника, перемещённую с начальной позиции сразу на два поля. Но под боем оказывается не то поле, на котором остановилась вторая пешка, а то, которое было пересечено ею. Первая пешка завершает взятие именно на этом, пересечённом поле, как если бы пешка противника переместилась лишь на одно поле.

Взять на проходе может только пешка, но не фигура противника. Пешка бьёт пешку.

О как, не знал! :(

Чтобы подобные проблемы отлавливать можно реализовать для своего движка perft и сравнить с известными данными: www.chessprogramming.org/Perft_Results
1. От программирования шахмат меня отталкивает то, что это паханное-перепаханное поле.
2. Всё-таки более классический путь написать UCI движок, и использовать логи. И тебе сразу же доступны много разных GUI + соперников-программ. Визизуализация дереве как идея мне не очень нравиться: выводи все линии, и если ты хочешь получить более делальный анализ, проанализируй ещё раз на меньшей глубине.
3. До многопоточности я бы всё-таки больше занялся генератором ходов и прочей оптимизацией. Хранение позиции в массиве не самая хорошая идея, ну хотя бы тогда использовать 0x88 для генерации ходов. А сейчас, особенно с ассемблерной инструкцией PEXT, наверное биторды впереди планеты всей. В один поток сколько позиций генериться в секунду?
4. Ну и вместо минимакса, который используется очень часто, я бы всё-таки посмотрел в сторону MCTS, всё-таки хоть что-то да новое…

Ну а так да, велосипед… Который другим бы, наверное, не рекомендовал изучать… Слишком уж много не очень удачных решений, которые надо будет переделывать для развития.

Согласен, я тоже не рекомендую его изучать — рекомендую писать своё. В программировании, как и в математике, самому решать задачи полезнее, чем изучать чужие решения.
За 0x88 отдельное спасибо :) У меня положение на поле как раз хранится в виде 0bYYYYXXXX.

Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.