Шахматное программирование: алгоритмы поиска и сортировки ходов

Хм... Написал редукшн, аналог Хистори - пока простейший вариант (работает нормально начиная с версии 0.06a, кроме хистори - отличий между версиями 0.05e и 0.06a практически нет, для сортировки ходов историю пока не использую)
Пургу несут на форумах, что прибавляет максимум 100 пунктов, а если есть продления на разменах - типа не прибавляет ничего.
У меня очень хорошо лёг. Думаю, что сбалансировав - можно с его помощью значительно больше сотни пунктов поднять...

http://www.f50.parsimony.net/forum200321/messages/15156.htm
В Блиц пока отстаю от нового Booot-а на 60 пунктов.
Их легко смогу поднять на улучшении ОФ.
Текущей силы уже должно хватить для того, чтоб войти в пятерку в третьей лиге WBEC (программа до сих пор плохо играет с короткими контролями)

Добрый день, коллеги!
Сезон охоты на Booot следует считать открытым . На самом деле улучшение оценочной функции это еще то увлекательное занятие! Последние 5 версий Booot (последняя удачная была чуть ли не год назад - 4.5) как раз и содержали попытки улучшения оценочной. Результаты оказались средние между "хуже чем было" и "значительно хуже чем было". . В самой последней версии 4.10.0. (выйдет сегодня-завтра) я занялся улучшением переборных алгоритмов при предельном упрощении оценочной. Судя по всему этот путь для Booot куда как перспективнее. Так что в свою очередь открываю сезон охоты на диких кошек .

Я оставляю исходники проекта после того, как перестаю им заниматься (типа ненарисованную картину показывать нельзя ). Предыдущий проект Booot 3.** был закончен. Вся линейка 4.** переписана практически заново. Так что как только начну переписывать движок еще раз (Booot 5.**) последняя версия 4.** будет выложена на sdchess.narod.ru. Но если кому интересны Делфи-исходники текущей версии могу кинуть .

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

Кстати, в личных встречах, по моим турнирам - Анечка с Booot-ом "в плюсе", причем с достаточно большим отрывом.
(насколько я понимаю, у него с защищенностью короля тоже "не очень" )

У версий 4.9 и 4.91 глюки при определении безопасности короля. Связано это было с тем, что уж очень много строк кода я туда пытался впихнуть . То же и с проходными. Иногда думаешь, что чем меньше специальных знаний, тем сильнее движок играет. Смысл в том, что сам я - КМС по шахматам. И когда пытаюсь движку вдумчиво объяснить шахматные знания он часто скатывается на мой уровень понимания игры

Я сейчас не играю - но у меня хорошая шахматная школа, и рейтинг плавал от 2200 до 2300+ Есно и сейчас Рейтинг ЭЛО ФИДЕ больше 2200.
поэтому вся оценка была написана "как я её понимаю" Зато очень удобно анализировать партии - я хорошо вижу на чём программа проиграла.

У меня сила игры примерно в том же диапазоне . Вот только я уже отчаялся написать оценку "как я ее понимаю" . Считаю более практичным "отдать слесарю слесарево" и пусть комп считает оценку "как ему удобно". Беру курс на выбрасывание из движка всего лишнего. А то смотрю партии движка: там он обыграл Руффиана и тут же слил черт знает кому и черт знает как - нервы ни к черту .

У меня пока лишнего в оценке точно ничего нет я даже оценку изолятора выкинул (как уже писал выше) - оценваются только сдвоенные изолированные пешки.
С нестабильностью игры - та же беда. Причем после добавления Хистори Редукшн программа стала играть еще более "нестабильно".
Но я режу очень много (с контролем 20' на 40 ходов, периодически в миттельшпиле программа считает на 16 полуходов!!!! И это при том, что скорость всего 400 kNPS (Это из-за спешки (генератор легальных ходов), скоро исправлю - подниму в 2.5 раза)), но ничего не поделать - так она играет сильнее.

меня пока лишнего в оценке точно ничего нет я даже оценку изолятора выкинул (как уже писал выше) - оценваются только сдвоенные изолированные пешки.

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

Скорость генератора ходов важна, но не слишком принципиально. К тому же когда много режешь (Booot в новой версии тоже использует Late move reduction) то НПС падает принципиально (больше нод вырезал - меньше стало быть себе насчитал) .

У меня без сокращений 400000 узлов в секунду
Если в 2.5 раза поднять быстродействие, то в блиц сила вырастет очень здорово.
А с длинным контролем - у меня портится история, нужно хранить историю не только из корня, но и по подветвям + отвел на историю всего один байт (в спешке), соответственно при большой глубине история становится не очень корректной + нельзя сокращать на ходе проходной пешки (и нежелательно писать плохую историю остальным ходам, когда опровергающим является движение проходной), а я сокращаю, и пишу плохую историю...
То есть найдутся резервы, даже без дописывания оценки поднять силу (в кратчайшие сроки) и с короткими, и с длинными контролями.
Оценка защищенности короля, чтоб избежать нелепых жертв - у меня не превышает одной пешки.
Может превысить только в сочетании с другими признаками.

Если в 2.5 раза поднять быстродействие, то в блиц сила вырастет очень здорово.

Если поднять ОБЩЕЕ быстродействие с 400 тыс до милллиона, то да! Эффект должен быть. Только общая производительность от скорости генератора ходов зависит не так уж и сильно (хотя у вас в движке может быть по другому). Хотя зависит конечно . Там куда большее значение имеет скорость оценочной функции, скорость Make-Unmake,определения повторений позиции, сортировка ходов (включая SEE) и т.д.

"соответственно при большой глубине история становится не очень корректной + нельзя сокращать на ходе проходной пешки, а я сокращаю..."

А я вообще на историю наплевал при реализации History Prunning . Точнее почти наплевал: у меня только киллер-ходы исключаются из сокращений (ну и тактические ходы понятно).

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

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

У меня быстрая оценка, медленный как раз make - в нем проверяется легальность хода...
(в версии 0.00 был нормальный make (не проверял легальность) - и было 1500000 позиций в секунду, после этого было добавлено не так много замедляющих факторов)
У меня исключаются из сокращений все тактические, киллеры, ходы из Хеша. + Добавлю исключение на Движении проходных.
Дополнительное исключение из сокращений опровергающих "по истории" - достаточно серьезно повышает силу (в моей схеме).
Только у меня таких ходов мало. (не сокращаю, если ход был опровергающим как минимум в 1/6 из тех позиций, которые по некоторым условиям считаются достойными попасть в историю )

медленный как раз make - в нем проверяется легальность хода...

У меня тоже - Все руки не доходят грамотно связки проверять да не запускать постоянно дурные алгоритмы проверки на шах после хода.

Дополнительное исключение из сокращений опровергающих "по истории" - достаточно серьезно повышает силу (в моей схеме).

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

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

"Сортируются только взятия, первыми рассматриваются ходы из Хеша (у меня два опровергающих в хеше)"

Это как??? Он если опровергающий по бета, то как бы один... он же единственный . Или , наверное, у вас хеш с двумя схемами замещения и позиция может оказаться как в одной половинке хеша так и в другой?

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

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

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

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

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

0x88 - генерация только взятий и генерация взятий и превращений - практически одинаковы по скорости
Да . В битбордах есть свои прелести.

В Го, например, сохраняют всю историю опровергающих ходов
Ход, который был опровергающим на меньшей глубине - в любом случае должен стоять на втором месте, а не позже - так как он всяко лучше любого хода полученного сортировкой ходов/взятий.
Опровергающий ход остается тем-же, только если позиция встретилась не с большей бетой.
То есть ход полученный сортировкой взятий/ходов, киллер (ход, лучший в другой позиции) более интересен, чем опровергающий?
То есть, например при глубине 10 мы получили лучший ход (d4), при глубине 11 лучшим стал другой (e4) и этот первый лучший уже неинтересен? И в схеме редукшина мы даже на нем сократим перебор?
И рассмотрим его одним из последних на глубине 12, хотя огромная вероятность, что если первый ход из хеша оказался неопровергающим, то опровергающим будет этот, второй ход?

Из-за одного опровержения - у него не будет хорошее Хистори... Ежели е4 был лучшим при глубине 2,3,4,5,6,7,8,9
Либо если ход d4 специфичен, и лучшим был он только в этой позиции (и является хорошим только в этой позиции).
Да и в сортировке он может в самом конце оказаться...

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

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

"Ход, который был опровергающим на меньшей глубине - в любом случае должен стоять на втором месте"

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

"То есть ход полученный сортировкой взятий/ходов, киллер (ход, лучший в другой позиции) более интересен, чем опровергающий?"

Нет, он не интереснее опровергающего, но он может быть намного полезнее, чем второй опровергающий, полученный на маленькой глубине.

"То есть, например при глубине 10 мы получили лучший ход (d4), при глубине 11 лучшим стал другой (e4) и этот первый лучший уже неинтересен?"
В корне перебора он обязательно должен идти вторым (там все последовательно), но в реальном дереве (где помимо глубин 10 и 11 существуют разброс глубин 10 и 5) его ценность лично для меня не так ясна . К тому же если он действительно настолько хорош, то он будет в киллерах либо иметь высокую хистори, и будет на первых ролях в переборе, что не даст его вырезать. А если он таки плох, то придется придумывать какие-то иные критерии по которым нужный ход надо сберечь , поскольку бестолку рассмотренный вторым номером второй опровергающий занял его место под солнцем .

И рассмотрим его одним из последних на глубине 12,
Если он был лучшим на глубине 10, то у него будет ТАКАЯ хистори, что одним из последних он не станет.

"Из-за одного опровержения - у него не будет хорошее Хистори"

Одно опровержение на глубине 10 важнее чем 20 опровержений на глубине 2 (в моей по крайней мере схеме). Так что лично я за судьбу такого хода не стал бы сильно волноваться.

"Тем более, что лучше начинает работать редукшн, и улучается бренчинг фактор."

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

Как это какая разница? У меня ходы из хеша не режутся, а история (по другим позициям) у них могла быть очень плохая.
Насчет того, что сохранение второго хода в хеше не нужно... Могу покопать инет - и найти, в каких движках входящих в элиту хранится 2 хода в хеше... Они видимо тоже заблуждаются, считая что взятие отсортированное по SEE или MVL/LVA не может быть ценнее, чем опровергающий ход в этой позиции, даже при глубине 1...
Бранчинг фактор напрямую зависит от порядка ходов в тех позициях, в которых есть опровергающий ход, и наверно глупо доказывать, что лучший ход, который был опровергающим при глубине 1 - обычно хуже, чем "первое взятие по SEE" опровергнутое при этой-же глубине, и при той-же бете.

У меня ходы из хеша не режутся, а история (по другим позициям) у них могла быть очень плохая.

У меня не режутся первые 3 хода (в том числе и ход из хеша, если таков есть (он всегда первый)), киллера и взятия. Обычно хватает , чтоб ход с высоким хистори заслужил то, чтобы его рассмотрели без урезания.

"Они видимо тоже заблуждаются, считая что взятие отсортированное по SEE или MVL/LVA не может быть ценнее, чем опровергающий ход в этой позиции, даже при глубине 1 "

Редко бывают плохие идеи - бывает плохая реализация . Лично мне кажется, что взятие с хорошим SEE следует рассмотреть сразу же за ходом из хеша, особо не интересуясь историей лучших ходов вообще. Шахматы такая игра, что если можно сожрать коня за пешку. то в 99% узлах дерева перебора это следует сделать (как в ГО не знаю - не играю).

"и наверно глупо доказывать, что лучший ход, который был опровергающим при глубине 1 - не может быть хуже, чем "первое взятие по SEE" опровергнутое при этой-же глубине."

Не согласен. Ход может быть опровергающим на глубине 1, но на глубине 2 (после размена, отвергнутого ранее) оценка может кардинально изменииться.

Так я и рассматриваю взятие с хорошим SEE сразу после хода из Хеша, только Не после одного, а после двух.Причем этот второй ход из хеша, всяко на некоторой глубине оказался лучше, чем это первое взятие по SEE, так как оно по сортировке было рассмотрено раньше и опровергнуто, а он наоборот, сам был опровергающим ходом.
Может измениться оценка, с этим никто не спорит. Но если ход был лучше при глубине 1 (сравниваем два хода - первое взятие по SEE, и опровергающий ход при глубине один, при этом понятно, что взятие было рассмотрено до него, и было опровергнуто), то больше 50% вероятности, что он вообще лучше... А то так можно рекурсивно договорится до того, что и ход лучший при глубине 10, хуже первого взятия по SEE, так как он опровергается при глубине 11 И перебор вообще не имеет смысла - взяли первое взятие, и сделали ход. А то вдруг наш лучший ход опровергается при глубине 20...
Вот если это первое взятие станет опровергающим, тогда оно и вытеснит один из ходов из хеша...

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

Насчет мобильности ферзя - давно известно, что это очень спорный признак
Оценка по расстоянию - у меня работает... но я ей дал -1/1000 пешки (у меня оценка в тысячных) За единицу расстояния.

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

Мобильность ферзя пробовал в тестах - ничего реального не дает. Правда Сергей мне сразу сказал, что это не сереьезно, но я люблю проверять А вот ладью и слона оставил. Вот только как ее оценить правильно? Во сколько оценить клеточку? Пока стоит 1/100 пешки...

Мобильность ладьи и слона обязательно нужны.
Горизонтальные возможности ладьи нужно ценить меньше, чем вертикальные.
А остальное всё индивидуально. Главное избежать (компенсировать другими признаками, например защищенностью короля) ходы вроде g5 за черных (чтоб ограничить чернопольного слона белых).
Плюс - у меня ладья "стреляет" через свою-же ладью. То есть вторая ладья не ограничивает возможности первой.

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

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