Комментарии 52
1. Про поиск в ширину автор пишет полную чушь, дерево, в принципе не надо хранить, если у вас список ходов из позиции детерминирован, то важен только текущий путь и оценки, для механизма отсечения.
2. Автор искажает факты, только начиная с ключевого пункта "(при этом ветки со взятиями и шахами могут достигать заметно большей глубины)" из раздела «Углубление поиска» его программа, действительно смогла играть, до этого она могла просчитвать мат в пределах видимости, но ни о какой игре речь не шла.
Поясню дополнительно: если рассматривать любую позицию, то почти всегда возможно взятие вашей фигуры, если не ваш ход или вы можете взять достаточно весомую фигуру противника, а расплата, которая наступет дальше, находится за горизонтом события, поэтому программа, просчитывающая на определённую глубину не может В ПРИНЦИПЕ адекватно оценивать никакую позицию, все оценки — коту под хвост, она постоянно будет приписывать либо вычитать сильную фигуру, чего не будет случаться в реальности.
Статья выглядит довольно ладной, но, сдаётся мне, что автор нифига не писал (особенно, учитывая отсылки к дерменизму: вы можете просчитать на нужную глубину, только имея безлимит по времени, имея же временной лимит, вы просто обязаны реализовать просчёт во время обдумывания хода соперником и ни о каком детерминизме речь уже не идёт), просто посмотрел движки, пособирал инфу и выложил нам компиляцию того, что надо сделать.
P.S. Ну и тот, кто действительно писал движёк, знает чем отличается минимакс, от альфа-бета, про который в статье даже не упоминается. Исходники не смотрел, вроде бы в ТурбоВижн 19xx лохматого года идёт движёк шахмат, для общего развития.
Шахматный движок в 328 байт: в целом, ценность шахматного кода преувеличина
Спасибо за статью о Дельфи/Lazarus.
дерево, в принципе не надо хранить
А как его визуализировать, если не хранить?
сдаётся мне, что автор нифига не писал
А код на гитхабе, видимо, сам-собой возник? :-)
А как его визуализировать, если не хранить?
Вы же не отображаете всё дерево, а только путь, даже если оно интерактивно, показать прощёлкнутую ветку — никаких проблем нет, это несколько деятков позиций.
А код на гитхабе, видимо, сам-собой возник? :-)
Не собираюсь вникать в то, откуда взялся код и насколько он оригинален.
Ну надо где-то брать оценки для отображаемой ветки. Пускай позиций отображается немного, но их оценка формируется из большого количества листьев. Может быть с альфа-бетой посчитать их "на лету" было бы достаточно быстро, не знаю. Я выбрал простой вариант.
откуда взялся код и насколько он оригинален.
Осмелюсь предположить, что код с поиском в ширину — достаточно уникален. Кто ж станет такое писать. Зато он позволяет прочувствовать как именно играет AI с полным перебором на фиксированную глубину. Если бы его не написал — это осталось бы загадкой :)
Кстати, первый коммит в репозитории — как-раз старая версия, которая играет детерминированно и думает только на своём ходу. В этом нетрудно убедиться.
Хм, тогда непонятно в чём суть претензии, что я начал с поиска в ширину, если все с этого начинают :-)
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 и подобные подходы похоже работают лучше.
Захват центра — через небольшой бонус за количество полей под боем, за 7 горизонталь тоже.
Но тут есть проблема: вся эта куча параметров — как их определить: на глаз, по ощущениям?
Это работает пока AI играет на таком уровне, что очевидно где решение правильное, а где — ошибка. А дальше уже нужны другие методы типа генетической оптимизации. В шахматах это нелегко, из-за того, что партии длятся долго и провести миллион партий для оптимизации параметров — дело затратное.
Я провел несколько партий против AI на chess.com
А как вы подключили туда движок? У вас UCI поддерживается?
Я свой на Arena запускал для тестирования.
GPU сильно уступает в математических вычислениях. Эффективно будет только, если создать на GPU сотни и сотни потоков
Возможно, будет иметь смысл на первых нескольких полуходах собрать базу ходов и все их отправить уже дальше считаться на GPU. Потом посмотреть, что вернёт GPU и выбрать лучший ход из этих миллионов.
Тут проблема в общем хеше позиций. Не видно, как эффективно использовать приватную память, а с глобальной скорость будет падать…
Я предлагаю тебе использовать по полной ОЗУ видеокарты в программе. И тогда потоки в GPU будут эффективнее, т.к. ты сможешь себя не ограничивать там и отдавать потокам более значимую работу.
В противном случае, ты будешь отдавать мелкую работу миллионам потоков, т.к. им просто напросто не с чем работать, т.к. да, из CUDA нельзя получить доступ к «внешней» ОЗУ.
но во время работы нужно обращаться к тому, что хранишь.
Нет. Каждый поток на GPU будет независим от остальных и просчитывает всю свою ветку со всеми частями, как если бы игра началась с его позиции. Что касается кэша, то им вообще можно пожертвовать (при миллионе потоков — легко). В этом случае расход памяти вообще околонулевой, а коллизий нет вообще.
Проблема только в том, что этот миллион потоков отвечает всего нескольким дополнительным полуходам. Стоит ли овчинка выделки, вот вопрос.
Поэтому движок обычно считает на глубину N, сохраняет как можно больше нод в хеше вместе с порядком ходов от лучшего к худшему. А потом считает на глубину N+1 при этом максимально использует результаты, полученные на глубине N (в первую очередь смотрим ход, которым был лучшим на глубине N).
Наверное, будет лучше смотреть в направлении методов MCTS, они лучше отвечают архитектуре 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 — на проходе) в шахматах означает специальный ход пешки, при котором она берёт пешку противника, перемещённую с начальной позиции сразу на два поля. Но под боем оказывается не то поле, на котором остановилась вторая пешка, а то, которое было пересечено ею. Первая пешка завершает взятие именно на этом, пересечённом поле, как если бы пешка противника переместилась лишь на одно поле.
…
Взять на проходе может только пешка, но не фигура противника. Пешка бьёт пешку.
О как, не знал! :(
2. Всё-таки более классический путь написать UCI движок, и использовать логи. И тебе сразу же доступны много разных GUI + соперников-программ. Визизуализация дереве как идея мне не очень нравиться: выводи все линии, и если ты хочешь получить более делальный анализ, проанализируй ещё раз на меньшей глубине.
3. До многопоточности я бы всё-таки больше занялся генератором ходов и прочей оптимизацией. Хранение позиции в массиве не самая хорошая идея, ну хотя бы тогда использовать 0x88 для генерации ходов. А сейчас, особенно с ассемблерной инструкцией PEXT, наверное биторды впереди планеты всей. В один поток сколько позиций генериться в секунду?
4. Ну и вместо минимакса, который используется очень часто, я бы всё-таки посмотрел в сторону MCTS, всё-таки хоть что-то да новое…
Ну а так да, велосипед… Который другим бы, наверное, не рекомендовал изучать… Слишком уж много не очень удачных решений, которые надо будет переделывать для развития.
Согласен, я тоже не рекомендую его изучать — рекомендую писать своё. В программировании, как и в математике, самому решать задачи полезнее, чем изучать чужие решения.
За 0x88 отдельное спасибо :) У меня положение на поле как раз хранится в виде 0bYYYYXXXX.
На нынешнем этапе писать шахматный движок... Ну блин - только если времени девать некуда и для саморазвития детям. Чисто отрабатывать какие-то вещи которые еще неизвестны в программировании. А делать думающий движок... Не елки - это зачем? Тем более не зная основ шахматной тактики как минимум? Ладно я детей учу, и учу их как думать. Но писать не понимая шахмат, да еще и "думающий движок"... Нет уж - увольте. Даже если спрошу почему у фигур такая стоимость - ведь не ответит...
Слишком много нюансов со стороны шахматиста. НЕ играющему на хотя бы средне-профессиональном уровне минимум лет 5 этого не понять.
Что вы называете "думающий движок", чем он отличается от "не думающего"? И почему "не зная основ тактики"?
Я так понимаю что "думающий" использует шахматные тактические и стратегические наработки. Простой перебор - вещь хорошая. но есть множество способов отсечь тупиковое решение на начальном этапе. Не зная теорию шахмат - Вам этого сделать не удастся. Просто перебор вариантов - это круто... в современном мире мощностей и наплевательского отношения к ресурсам машины. Но это не круто, в моем понимании, для самого программиста.
Если даже брать тупо "стоимость фигур". У Вас она неверная, потому что для расчета партии она должна считаться по другому. А для этого надо знать - а ПОЧЕМУ такая стоимость и откуда она взялась? Но это задачка даже для некоторых шахматистов сложная. Вон например Карпов считает что стоимость ферзя равна 10-ти пешкам. И я (далеко не мастер) могу с ним сильно-сильно поспорить в этом вопросе. причем - аргументированно :-) И даже думаю что выиграю этот спор.
У вас какое-то бинарное понятие "знания теории шахмат". Оно подтверждается чем - дипломом, сертификатом? :-)
Ну да ладно, вполне допускаю, что вы знаете "теорию шахмат", можете сильно-сильно, аргументированно и успешно спорить с шахматистами о том, сколько стоит ферзь - 10 или 8 пешек. Но вот от темы разработки игрового AI вы, судя по вашим постам, весьма далеки. Так что нет смысла спорить, пусть каждый занимается своим делом.
Если разговор будет идти про AI - то да, возможно и соглашусь. Тут я звезд с неба хватать не буду. Но пишу то я о другом. Вы пытаетесь разработать что-то в той области в которой не совсем понимаете теорию. Если бы изначально было ознакомление с теорией, и Вы бы попробовали хотя бы понять что к чему - то и разговор был бы другим. А так - разговор действительно ни о чем. Писать AI в теме в которой есть неизвестные - ну это не очень хорошо. Какой результат можно ожидать если закладывать знания не зная основ?
Про бинарное и дипломы и прочее. Да, есть 7 лет обучения в детском возрасте. Есть педагогическое образование. Есть опыт работы преподавателем шахмат. Есть понимание (это как раз изначально - из-за шахмат - попытка понять почему и как). Понимаете, почему я завел разговор про то что надо шахзматы знать - первое что учится в шахматах это понимание - а нафиг сдделан ЭТОТ ход? Т.е. ты ищешь первооснову того что произошло. Когда тебе про это годами капают на мозги ты попросту по другому думать не можешь. Именно этим и хороши шахматы.
Еще у них есть плюс - недооценка соперника - первая и главная ошибка. Этот щелчек по носу ты получаешь на первых же соревнованиях. И получаешь их потом неоднократно на протяжении всех игр - расслабился, зазнался - бац по лбу. Я не хочу сказать что Вы плохой программист. Боже упаси. Я пишу про то что Вы пытаетесь не разобравшись в базовой теории научить этой теории AI. Вот Ваша ошибка.
Кстати, больше половины обучения шахматам - это поиск ошибок - своих и чужих. Это вбивается раскаленными гвоздями в мозг до основания. Поэтому уж простите меня великодушно, но в меня это вбили. Я всегда критически анализирую подаваемую информацию. В силу обучения шахматам.
Т.е. в последнем пункте мы закольцевались на первый пункт - Вы не пытаетесь найти в своем процессе ошибки которые допускаете. Вы ищите ошибки в теории программирования, совершенно игнорируя множество теории в шахматах. Т.е. скатываетесь условно на простой перебор и циклы. Шахматы так не работают. Точнее могут работать, но это болезнь современного поколения - пытаться решить задачу за счет процессорных мощностей. Это и не оптимально и попросту некрасиво. А шахматы - учат красоте в том числе :-)
В шахматах все сложнее чем кажется на взгляд непосвященного в недра человека. :-)
www.youtube.com/watch?v=U4ogK0MIzqk
Шахматы на Delphi. Как я изобретал велосипед