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

Я добавил горизонтальные возможности ладьи после того, как она запуталась в своих пешках в миттельшпиле

 

Надо искать... Вечером посмотрю в исходниках GnuGo, но вообще сохраняют всю историю (или максимум истории) опровергающих ходов для каждой позиции во всех играх, где медленная оценка, нет четкого критерия для хорошей сортировки ходов, и много возможных ходов в каждой позиции - ГО, Hex, Хальма (уголки на поле 16x16 у каждого по 19 шашек в углу)

Либо в специфических ситуациях - когда памяти много, а быстродействие низкое - например шахматы на встроенном языке 1С )))

 

http://www.gnu.org/software/gnugo/gnugo_11.html#SEC143
Вот ссылка на описание Хеш структуры. Пока еще разбираюсь...

 

А вот статистика по моей программе (тест на начальной позиции)
if (oc>a1)and(hhoo<>0)and(bestM1<>0)and(hhoo<>bestM) then
Begin
vspopal:=vspopal+1;
if hhoo=bestM1 then
vspopal1:=vspopal1+1;
end;
Что это: oc - полученная оценка, если она больше a1 (сохраненное значение альфа), значит есть лучший ход.
hhoo - номер лучшего хода, если равен нулю (в данном случае по первому условию этого быть не может), значит нет лучшего хода.
bestM1 - вытесненный (второй) лучший ход в хеше (он всегда просматривается только после первого -bestM) Если не равен нулю, значит в хеше было два лучших хода.
Ну и последнее условие - опровергающий ход не равен первому лучшему ходу из хеша (ситуация, когда пришлось использовать второй...)
Ну и статистика -
19513 18311 (vspopal, vspopal1)
практически в 94% случаев второй ход из хеша сработал...
(был опровергающим, или лучшим(в случае ненулевого окна))
Вдобавок к этому - делая ход из хеша (пускай второстепенный, второй) - мы можем быть уверены, что дальнейшие ветви у нас хорошо прохешированы, так как ход оказался в хеше - значит по нему уже разок прошлись...
Ну и как я уже говорил - ход "обычно хороший", и в хистори редукшн по нему не сокращаем перебор. А по истории. так как она не привязана к конкретной позиции - ход может оказаться плохим...

 

Далее - двухуровневый хеш... Использовался в Крейблиц. В тестах (не на играющей программе, а просто "стреляем в хеш" случайными 64-битными числами) - показывает очень хорошие результаты...
Врятли это плохая идея (хотя сейчас большие объемы памяти, можно особо не заморачиваться. Но в чемпионате СНГ использовался (должен был использоваться по регламенту) 32МБ), и в условия недостатка памяти (длинные контроли) Должен давать заметную прибавку.
Потом... В западных чатах неоднократно "случайно подслушал" о причинах сильной игры Рыбки - двухпроходный переборный алгоритм... Говорят, что сейчас используется и в Junior-e...
Я в курсе, что до этого было много неудачных попыток. На сей раз похоже получилось...

 

Статистика по 40-му посту на острой позиции r1bqk2r/pppp1ppp/2n2n2/2b1p1N1/2B1P3/8/PPPP1PPP/RNBQK2R w KQkq - 6 5

40258 38469 96.6%

 

Раз уж мы взялись повышать эффективность использования хистори редкшн, то статистику лучше всего собирать по следующему критерию: процент бета отсечений (по всему дереву в основной модели перебора - без учета бета отсечений в модели форсированной игры), которые пришлись на 1-й 2-й или 3-й ход в отсортированном списке ходов. В идеале должно быть 100% (в этом случае все ходы с номером 4 и выше что вырезалось хистори редукшн вырезается правильно и безвредно). А уж после замеряния процентов можно и об методах их увеличения поговорить . В том числе и о схемах хеша.
У последней версии booot 4.10.1 в приведенной вами позиции после 30 секунд расчета этот процент равняется 97%. То есть в 3% бета отсечений опровергающим оказался ход с большим, чем 3 номером в списке ходов после сортировки и в этих случаях есть шанс получить дырку в переборе, используя хистори редукшн.

 

Я вроде пока говорил не о хистори, а о хеше лучших (опровергающих) ходов, в рамках основной хеш-таблицы И об использовании в нем не одного, а двух лучших ходов. Это нужно в основном не для хистори, а для лучшего упорядочивания ходов в рамках переборных алгоритмов (для того-же, для чего нужен и первый ход в хеше)
Хистори вообще другая тема.
Дыру получить при Хистори всегда большая вероятность
Только непонятно какие показатели считать... Наверно нужно много показателей.
1. Общий процент опровержения по бете на "сокращенных" ходах.
Среди них - процент опровержения по бете и процент опровержения по альфе при Верификации (повторном проходе с полной глубиной)
2. Среднее количество "сокращенных" ходов (общий процент) по опровергнутым по альфе ветвям, то есть где просмотрели (были опровергнуты) все ходы... (есно всё там, где применяется метод - король не под шахом, не PV ветвь)
Хотя это "навскидку" - надо подумать, что считать...
Или просто гонять на тактических тестах - там где хистори и проваливается...
[q]"Имеются в виду позиции с тихими ходами и перебросками фирур."[/q]
А о хистори я говорил только в том ключе - что раз уж у нас есть еще один ход в хеше, и на какой-то глубине он был хороший, то есно на нем тоже не будем сокращать - тем более что он смотрится раньше тактических ходов.

 

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

 

Лучше наверно всё-таки проверять упорядочивание не по косвенным, а по прямым признакам.
Отключить все Прунинги (Null Move, Футилити и т.д.) и Редукшины (Хистори), а потом уже смотреть на коэфициенты.
Методы отсечений и сокращений это уже второстепенно, и откношение к упорядочиванию имеют только косвенное...
Насчет Хистори Редукшн - Всё зависит от схемы. У меня упорядочивание при Хистори важно не более, чем без него.
Так как режутся конкретные ходы, по конкретным признакам, а не по сортировке, и номеру хода в отсортированном списке (это не является четким критерием).
Но естественно - в меру возможностей несокращаемые ходы вытягиваются в начало списка.
(шахи вытягивать достаточно ресурсоемко, но это в моей схеме)

 

Наверно немного другая статистика нужна (пока без деления по типам ветвей)
В ветвях, в которых БЫЛО ОПРОВЕРЖЕНИЕ ПО БЕТЕ - какой процент опровержений был -
На первом ходе, если он из хеша.
На первом ходе, если он не из Хеша.
На первых двух ходах, если Один из них не из хеша
На первых двух ходах, если оба они не из Хеша
На первых двух ходах, если они оба из Хеша (только для моей схемы с двумя ходами в Хеша)
и т.д.

 

Хммм последнее сообщение за 2006 год.... алгоритмы поиска видимо не развиваются(

 

Хаос такому не потакает *lol*

 

Хаос поглотил шахматное программирование

 

Ну просто NS забил на шахматное программирование, лень ему.

 

А у какого движка алгоритм больше всего напоминает человеческий ? то есть ходы делает не компьютерные ,а более человеческие?

 

У Фрица вроде

 

Которого?

 

Да нет ето Rybka

 

Мнения разделились
а как же движки типа заппы и шреддера, вроде лучше позицию понимают ?

 

Думаю у великой проги - Fritz 10 )

 

Просто вся тусня переехала на форум sdchess.net

 

Chemer

Там вирусов чуть меньше чем до фига

 

dan77790, там нет вирусов.

 

NS

Спасибо, что успокоили, но мой антивирус иного мнения(

 

dan77790, а можно узнать какие вирусы и на каких страницах?
похоже вы единственный кто может их увидеть.

 

NOD32, Symantek, Касперский, Авира и Лавасофт, все с последними обновлениями - вирусов на сайте не видят.

 

Сколько туда захожу, а захожу я туда давно и часто, никогда вирусов не встречал.

 

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

 

На сайте либо есть вирус, либо нет его. Сам он исчезнуть не может.
Вирус был, но безобидный для пользователей в течении недели в ФЕВРАЛЕ месяце.
(Вирус на страницах открываемых пользователями не появлялся)
И это единственный случай за всё время существования форума.