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

Матч с Руффианом Закончился победой. +30-5=15. Примерно 200 пунктов рейтинга преимущества.

Сегодня попробовал
Просто очуметь, играет в атакующем стиле, как и я люблю


Хотя и не дожал врага, но какая красота игры!

Миттельшпиль играет - одно загляденье.
При переходе в эдшпиль, нужно что то делать.
В стиле Магнуса Карлсена - получил перевес, размен и выигрышный эндшпиль.

Я ж говорил : сетка резка, как квас летом . Но , определенно, глубины и качества перебора пока не хватает нам. Уж очень все примитивно. Оценочно сейчас уровень игры порядка 2800. Для уровня 3000 надо бы добавить чего. Варианты :

1. Late Move Reduction. Сделаем какую-нибудь классическую логарифмическую формулу, известную еще с времен Фрукта.
2. Late move prunning. Обрезка на малых глубинах поздних ходов. Тут даже без оптимизаций и без оценочной функции в узле может хороший прирост быть
3. Обязательно Singular Extension пусть и простенький.
4. Ну и там по мелочи несколько полезных алгоритмов наберется.

Главное что это все просто и быстро уже будет реализовываться.

Как наиграетесь - може мобсуждать

Да - с эндшпилем вопросы. Сетка прекрасно отыскивает лучик света в темноте и идет к нему, но когда достигает выигранной позиции начинает немного буксовать. Там уже прожектор лупит, а не лучик, который говорит "да везде выиграно куда ни ходи, причем везде одинаково легко"

Сейчас мы с вами разговариваем как Шеннон с Ботвинником в 1965.
Я как и Ботвинник - мечтатель, в как Шеннон - математик.
Ведь я ничего не знаю о
booot76 wrote: И небольшая лекция обо всем этом будет полезна и познавательна

Ну если совсем обзорно, то идея в следующем : есть у нас уже работающий альфа-бета, который даже старым "дофруктовским" движкам может и накостылять. Исправно работает согласно алгоритмам. Но медленно с точки зрения разгона в глубину по наиболее интересным вариантам. И появилась у разработчиков идея как бы сделать перебор уже не "плоским", где все ветки получают одинаковую глубину перебора, а неравномерным : "интересные" ветки смотреть как можно глубже, а "так себе" резать как можно раньше. Перераспределив таким образом общее машинное время, которое у нас константа.
И понеслись идеи как отличать "интересные" от "так себе". А что если мы благодаря качественно работающему алгоритму сбора статистики начнем хорошо упорядочивать ходы в узле и таким образом предельно повысим вероятность того, что первые 3 хода в узле окажутся отсекающими по бете? А если не отсекают, то , скорее всего с огромной вероятностью это альфа узел где ВСЕ остальные ходы тоже ничего не отсекут? И тут у нас открывается возможность запустить такой алгоритм :
1. В каждом узле рассмотреть первые 3 хода максимально добросовестно (ибо "интересно"), а с остальными - поступить по справедливости : либо уменьшить глубину рассмотрения их, либо вообще нафиг отсечь. Сделав, правда, стоп-кран : если с уменьшенной глубиной отсечение в поздних ходах все-таки было совершено, то такой ход надо назвать "интересным" и пересмотреть его уже с максимальным усердием.
Вот собственно краткое содержание 2 первых алгоритмов.

Ну а 3-й это , наоборот, про продления. Уж самых-самых "интересных". Идея у него несложная тоже : рассматриваем первый ход в узле (хеш-ход, который уже не первый раз "первый" в этом узле) с усердием, а прежде чем рассматривать остальные запускаем перебор с усеченной глубиной и запретом на этот наш первый ход. Узнаем : а какой- же у нас второй лучший ход в этом узле? И если он "сильно хуже" первого, тогда первый ход в узле мы называем "самым-самым интересным" и не только его не думаем резать, но еще и удлинняем чтобы еще больше посмотреть за горизонт. Таким образом движок строит цепочки форсированных ходов, а лишь потом смотрит в глубину что же там после них. Сильно помогает

Ботвинник, помнится, называл эту мысль горизонт событий, но делал это без усердия

А почему она "классическая логарифмическая"?

Впервые появилось таковой. По моему в Тоге. Или даже во Фрукте еще.

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

Поэксперементировал.
Сделал по умолчанию 8 сек на ход, на 5 сек все же больше проигрывал.
В общем то бился достойно, даже с Рыбкой.

Сработало правило 50 ходов.


Тут и по таблицам ничья.

С добавлением дальнейших протокол UCI пока что то не очень получается

Ну пока не торопитесь. Допилим движок - там уже выпускать будете неспеша его А рыбка это серьезно. Рановато нам пока

Прошу вас вкратце описать текущую реализация движка.
У меня в голове каша
И сложно все по полочкам разложить для себя.

Тогда может паузу небольшую сделаем? Я завтра краткую инвентаризацию проведу что у нас есть

ПО инвентаризации.

1.Основа нашего движка - разновидность альфа-беты под названием PVS (Principal Variation Search). Основная идея: первых ход в узле смотреть в полном окне (альфа, бета) , предполагая, что он лучший, а остальные ходы смотреть в минимальном окне (альфа,альфа+1), предполагая, что раз первый не вызвал отсечение, то и остальные не будут, а сужение окна сильно секономит нам количество просмотренных узлов из-за куда более агрессивного отсечения. Если же минимальное окно было таки превышено, тогда перематриваем ход на той же глубине уже с его полным окном. В этом алгоритме мы сразу получаем 2 типа узлов : PV (полное окно альфа-бета, шире чем 1) и NonPV (минимальное). Это нам важно для будущих алгоритмов отсечения, которые более бережно должны относиться к PV узлам, потому что именно в них, меджду альфой и бетой мы надеемся найти лучший вариант и передать его в корень. Алгоритм известен еще по моему с начала 80-х где еще CrayBlitz его использовала. И далее автор его перенес уже в 90-х в свой движок Crafty.

2. Так как мы ждем что первые ходы у нас должны быть отсекающими, то большое внимание надо уделять статистике сбора информации и процедуре оценки и ранжирования-сортировки ходов в узле. Тут у нас используется целый набор алгоритмов (тут как раз жалеть не стоит - чем лучше сортировка тем лучше движок). Самый первый и самый стандартный алгоритм Butterfly History. Я его использую немножко видоизмененную, свою его реализацию. Основная идея : Если ход в узле был отсекающим по бете, то в глобальной таблице "Фигура-куда пошла" увеличиваем его оценку в зависимости от глубины перебора в которой он лучший стал. Табличка заполняется глобально по дереву. Дале я использую связанную историю. Подход тот же, но уже не глобально по дереву, а в зависимости от ходов выше по ветке. Условно : Если противник когда-то пошел конем на край доски, а мы его когда-то в ответ на это пешкой атаковали и получилось хорошо, то теперь ход этой же пешкой в ответ на код того же коня на край доски получает персональный бонус по истории. То же и для нашего последнего хода на ветке. Условно : если мы когда-то прогнали пешкой коня на край доски, а потом второй пешкой его добили, то ..... Далее я использую алгоритмы "киллеры" и "опровергающие". Идеи те же : если какие-то ходы на этом уровне дерева когда-то оказывались опровергающими , то мы на этом же уровне дерева их рассматриваем перед всеми остальными. Глобально ("киллеры") и оказавшиеся опровергающими в ответ на предыдущих ход противника ("опровергающий"). Это все алгоритмы для "тихих" ходов. Для взятий - свой алгоритм. Взятия у нас рассматриваются прежде всего и сортируются по стоимости цели. Чем большую фигуру берем тем раньше этот ход будет рассмотрен. Но прежде - проверяем этот ход на оценке разменов. Если ход кажется проигрывающим (типа ферзь берет защищенную пешку), то , наоборот, такие ходы смотрим в самом конце после всех тихих.

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

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

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

Пока из важны все - нюансы реализаций в комментариях. Я и так там "Войну и Мир" вам написал

3.

Картинку бы еще для чайников
Можно без UML

Та я сам - чайник , картинки рисовать не умею . Мне бы алгоритм, какой, смастерить. Просто может слишком быстро для Алексея двигаюсь. Надо дать ему время. Спешу, потому что у меня скоро уже данные для новой версии сгенерируются. На части их которых , к слову, сетку нашу обучил. Потом по своему движку забот будет хватать. Это если еще электричество будет. Интересно просто было : если написать простой добротный движок-макет на минималках, ни разу не хватающий звезд с неба, но без явных багов и с совремнным пониманием задачи, то насколько сильно он будет играть? Пока , как бы, результаты даже меня немного удивляют. Рыбу уже руками трогаем.

Vladimirovich wrote:
Общая схема работы шахматного движка. Не конкретно данного движка, но общая для всех классических.

1. Сначала смотрим основной вариант (PV). Это любая ветка в начале перебора или лучшая с предыдущего перебора c +1 к глубине.
Допустим мы исследовали PV и получили оценку +5 (см. картинку ниже). Теперь переходим к следующему варианту, который попытаемся отсечь.

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



Главный принцип нулевого хода - после первого хода варианта пропустить ход соперника и сделать ещё один ход за себя. Если даже после двух ходов подряд оценка все равно ниже чем у основного варианта (+3 меньше чем +5 на схеме), то отсекаем такой вариант. Два хода подряд обычно большое преимущество, и если даже они не помогли, значит вариант плох и не достоин рассмотрения.

Если же получили оценку выше основного варианта (допустим +18), то отменяем нулевой ход и приступаем к основному перебору. Генерируем ходы (из нижней позиции на схеме) уже по всем правилам шахмат.

Продолжение следует.

Кое-что оптимизировал в движке не добавляя пока ничего нового. Жду Алексея.

Провел матч с The Baron (2899) 5 секунд на ход 80 партий. Боевая ничья 40-40. Вот где-то пока мы так. Без основных ускорителей на минималках .

3. Генерируем ответы соперника и сортируем их в порядке перспективности. А как, напишу в следующем посте.

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

Допустим получили для этого ответа оценку +2. Это предполагаемый ответ нашего соперника. Поскольку здесь он выбирает ход, то лучше чем на +2 в данном варианте мы уже не можем рассчитывать - соперник же не враг себе, он выберет лучший ход для себя, а не для нас. Другие ответы нет смысла рассматривать. А поскольку у нас есть вариант получше (с +5), то отсекаем весь вариант и переходим к следующему.

Если говорит технически, то +2 меньше чем +5, а значит у нас произошло отсечение по бете.

Схема альфа-бета отсечений, после неудачного нулевого хода(+18):



Продолжение следует.

Альфа-бета отсечения в человеческих терминах можно описать так:
"Если в каком-то варианте мы сразу же наткнулись на сильный ответ противника, то вариант можно сразу же браковать, не рассматривая остальные ответы". Какой смысл, если у соперника тут хорошая игра?

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

Второе сложнее. Мы должны быстро отсортировать технически возможные ходы в порядке их выгоды для соперника. То есть первым мы должны исследовать ход с наименьшей оценкой для нас. Если рассматривать схему в предыдущем посте, то оценка должна быть меньше или равной +5. Тогда мы сможем отсечь вариант немедленно. Но ведь мы её пока не знаем.

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

Продолжение следует.

3. Как отсортировать ходы в порядке убывания их силы для соперника?

Исторически сложилась следующая последовательность:

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

б) Смотрим "выгодные" взятия. То есть взятия с положительным материальным балансом, отсортированные по данному параметру. Логично, ведь такие взятия резко повысят оценку для соперника, а значит и "выгодность" хода. Стандартные методы для данной процедуры - MVV/LVA, SEE, и в современных движках History для взятий.

в) Смотрим тихие ходы. Обычно это "Киллеры", иначе говоря "убойные ходы", то есть ходы которые недавно вызывали отсечения.
Дело в том, что в похожих позициях обычно и отсекающие ходы одинаковые. Значит надо в первую очередь попробовать ходы недавно вызывавшие отсечение. Технически мы просто запоминаем два последних отсекавших тихих хода и обновляем их ряд по мере продвижения по дереву. Для каждой глубины "киллеры" свои.

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

д) "невыгодные" взятия и прочие ходы.


Но допустим мы посмотрели пока первый ответ соперника и отсечения не произошло. Допустим оценка первого хода в схеме выше была не +2, а +7. Это больше беты, а значит отсечения нет; надо смотреть следующие ответы. Здесь, для ходов с позицией по сортировке >1 возможна дополнительная оптимизация. О ней далее.

Продолжение следует.

5. Выше мы предположили, что после рассмотрения первого ответа соперника, он получил оценку +7. Ниже, я прилагаю обновленную схему.

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

Казалось бы, тогда и не нужно смотреть эти ходы. Но сортировка у нас простейшая - явно не идеальная. Поэтому смотреть ходы с порядковым номером 2 и выше всё-таки придется. Но поскольку такие ходы вряд-ли когда-либо обновят первую линию (PV), то давайте их смотреть с меньшей глубиной. И чем больше номер хода по сортировке, тем с меньшей глубиной его можно рассматривать.

Если ход, который идет вторым номером разумно "подрезать" совсем чуть-чуть, то глубину каждого следующего ответа будем сокращать всё больше и больше. В этом суть метода Late Move Reductions (LMR) - сокращения на поздних ходах. Схему работы метода LMR смотрите ниже.

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

Схема LMR:


Как видите, в общем случае мы отсекаем или сокращаем практически всегда. Не тем, так другим методом. Но есть нюансы. Об этом в следующем посте.

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

Продолжение последует, но позже. Когда-нибудь позже

Предлагаю исодники сделать доступными для всех.
Но какую площадку выбрать?
Может этот форум?
Что скажет Vladimirovich?
Что скажет booot76?

Я не возражаю. Макет написан "для тренировки пальцев" в учебных и научно-популярных целях.

Ром, а какой движок вы написали?

alexlaw wrote: Все зависит от объема.
На форум можно грузить любые архивы по умолчанию до 400К. Размер можно увеличить но это не главное.
Возникает проблема с версионностью, форум для этого не предназначен.

Есть github. Может там?

Vladimirovich wrote: Просто оставлять последнюю версию. А предыдущие удалять.