Главная › Форумы › Шашечные программы › Шашечные программы › Стандартная проверка корректности генератора ходов
- В этой теме 126 ответов, 8 участников, последнее обновление 17 лет, 1 месяц назад сделано Kallisto.
-
АвторСообщения
-
04.03.2007 в 17:35 #364665AlexanderSУчастник
Раз совпадает… Значит у меня практически готова первая версия в международные шашки
Только интерфейс нужен,
и книга по эндшпилю — а то сейчас нет эндшпильной оценки.Ну все программисты давно уже вроде как отказались от попытки формализовать эндшпильную оценку. ИМХО практически по каждому классу придется все отдельно описывать. Оно тебе надо? Сгенерируй ЭБ и не мучайся. А для больших эндшпилей (типа 4*4) уже можно будет частные случаи рассматривать.
04.03.2007 в 17:41 #364666NSУчастникНу все программисты давно уже вроде как отказались от попытки формализовать эндшпильную оценку. ИМХО практически по каждому классу придется все отдельно описывать. Оно тебе надо? Сгенерируй ЭБ и не мучайся. А для больших эндшпилей (типа 4*4) уже можно будет частные случаи рассматривать.
Нет, не отказались. В шахматах формализуют.
У меня в русских шашках описано в коде несколько классов Эндшпильных позиций.Я могу разбить эндшпиль на классы, и для каждого класса посчитать ОФ на балансе шашек — но это достаточно долго, проще почитать теорию.
Если ЭБ безранговые — эндшпильная оценка потребуется в любом случае.
04.03.2007 в 17:55 #364667letasУчастникРаз совпадает… Значит у меня практически готова первая версия в международные шашки
Только интерфейс нужен,
и книга по эндшпилю — а то сейчас нет эндшпильной оценки.В программе dragon-2.4.1 есть генератор баз окончаний.Он не подойдет для оценки эндшпиля?
04.03.2007 в 18:34 #364668NSУчастникВ программе dragon-2.4.1 есть генератор баз окончаний.Он не подойдет для оценки эндшпиля?
Так это-же ЭБ, без описания формата она ничего не даст, и ЭБ не так уж и сложно посчитать самому.
Хотелось именно разобраться с Эндшпильной оценкой и прописать её в коде, так как не у всех есть большие объемы памяти, и не у всех есть желание качать/генерировать большие базы.
В Тоге/Фрукте не было поддержки ЭБ, но это не мешало им быть сильнейшими шахматными программами.
04.03.2007 в 19:12 #364669KvadratУчастникВ программе dragon-2.4.1 есть генератор баз окончаний.Он не подойдет для оценки эндшпиля?
Так это-же ЭБ, без описания формата она ничего не даст, и ЭБ не так уж и сложно посчитать самому.
Хотелось именно разобраться с Эндшпильной оценкой и прописать её в коде, так как не у всех есть большие объемы памяти, и не у всех есть желание качать/генерировать большие базы.
В Тоге/Фрукте не было поддержки ЭБ, но это не мешало им быть сильнейшими шахматными программами.
Вы вообще хотите обойтись без использования ЭБ? Круто.
Белые простые a1,c1,c5,e5
Черные простые g3,h4. Ход белых.
при наилучшей игре со стороны черных игра завершается через 85 ходов! Есть ряд семифигурных окончаний на сайте у М.Глизерина. Там ваапче игра идет больше сотни ходов!04.03.2007 в 19:20 #364670NSУчастникВы вообще хотите обойтись без использования ЭБ? Круто.
Белые простые a1,c1,c5,e5
Черные простые g3,h4. Ход белых.
при наилучшей игре со стороны черных игра завершается через 85 ходов! Есть ряд семифигурных окончаний на сайте у М.Глизерина. Там ваапче игра идет больше сотни ходов!Ничего нет страшного в том что программа не будет уметь выигрывать несколько конкретных позиций.
Я не хочу отказываться от ЭБ, я просто хочу чтоб программа хорошо играла и без ЭБ.
Многие сложные Эндшпильные позиции Шахматные программы умеют выигрывать без ЭБ, например KNNKP в шахматах — для выигрыша зачастую требуется под 100 ходов. Но Хиаркс этот класс эндшпилей понимает и без ЭБ.
И научить программу можно не просто правильно разыгрывать, но и правильно оценивать весьма сложные эндшпильные позиции.
05.03.2007 в 00:57 #364671AlexanderSУчастникPerft в международные шашки:
совпадают все цифры
если несложно, посчитай еще какую-нибудь позицию из миттельшпиля, где близко дамки, или эндшпиля.Нет, не отказались. В шахматах формализуют.
Хорошо, уточняю — в ШАШКАХ )
В шахматах с малым материалом материальное преимущество в абсолютном большинстве реализуемо даже для перворязрядника, кроме некоторых классов и исключительных позиций, которые и вручную можно втиснуть.
А большие базы генерировать в шахматы накладно, вот никто 10-фигурнку и не сделал, а так кто знает какие там сюрпризы были бынапример KNNKP в шахматах
Эмм… Не понял. Окончание король + 2 коня выиграно против короля с пешкой??
Так это-же ЭБ, без описания формата она ничего не даст, и ЭБ не так уж и сложно посчитать самому.
Ну так что не не посчитал, раз несложно?
ОФ-то для эндшпилей по 100% точной базе проще будет настраивать чем в партиях.
Помню с таким энтузиазмом взялся
Формат Дракона открытый, с исходниками. Знал бы Си покопался бы05.03.2007 в 07:22 #364672NSУчастникНу так что не не посчитал, раз несложно?
ОФ-то для эндшпилей по 100% точной базе проще будет настраивать чем в партиях.
Помню с таким энтузиазмом взялся
Формат Дракона открытый, с исходниками. Знал бы Си покопался быЭБ — я и так очень туго сейчас соображаю, очень сильно химиотерапией поврежден мозг, поэтому боюсь понаделать ошибок при генерации ЭБ и не хочу на них отвлекаться — и так достаточно плотно занят настройками ОФ и переборных алгоритмов в разные виды шашек.
В русские шашки у меня есть формат Каллисто с готовым генератором, его я в новой версии и буду использовать. С Международными нужно опять напрягаться…У меня есть свой формат + я знаю формат Каллисто, поэтому нет смысла смотреть формат Дракона, проще переделать известные мне форматы под стоклетки.
Хорошо, уточняю — в ШАШКАХ )
В шахматах с малым материалом материальное преимущество в абсолютном большинстве реализуемо даже для перворязрядника, кроме некоторых классов и исключительных позиций, которые и вручную можно втиснуть.
А большие базы генерировать в шахматы накладно, вот никто 10-фигурнку и не сделал, а так кто знает какие там сюрпризы были быНе так уж и мало нужно в шахматах втискивать
Классов эндшпильных позиций намного больше чем в шашках, и нужно не забивать исключительные позиции, так как обычно исключений половина А полностью писать оценку, коорая поможет и оценить, и играть на выигрыш, для каждого класса окончаний отдельно…В шахматах генерацией ЭБ занимаются команды по 100 человек, с огромным числом компов, поэтому ЭБ в шахматах всяко не менее развиты чем в шашках. Полностью посчитана Шестифигурка, но она занимает просто Жуткий объем.
Игра на выигрыш без ЭБ в большинстве эндшпильных позиций в шахматах оцень тяжела, примеры — самые распространненые ладейные эндшпиля, ферзевые и т.д. Не всё так просто. На первый взгляд в шашках реализовывать преимущество без ЭБ наоборот проще.
Например матование тремя дамками одну — значительно проще чем матование слоном и конем голого короля.
Так-же не так уж и просто матовать Ферзем против ладьи и т.д.Эмм… Не понял. Окончание король + 2 коня выиграно против короля с пешкой??
Да, в большинстве случаев когда пешка блокирована конем этот эндшпиль выигран, но методика игры на выигрыш весьма сложна.
05.03.2007 в 07:33 #364673NSУчастникperft в международных шашках с пустой 1,2,3,8,9,10 горизонталью, у каждой стороны по 5 шашек:
Depth= 1 Nodes= 9
Depth= 2 Nodes= 81
Depth= 3 Nodes= 534
Depth= 4 Nodes= 2538
Depth= 5 Nodes= 9052
Depth= 6 Nodes= 29999
Depth= 7 Nodes= 98971
Depth= 8 Nodes= 310315
Depth= 9 Nodes= 1008317
Depth=10 Nodes= 3174159
Depth=11 Nodes= 10369533
Depth=12 Nodes= 34907917
Depth=13 Nodes= 123162301
Depth=14 Nodes= 462333827
Depth=15 Nodes= 1824763597
05.03.2007 в 10:36 #364674KallistoУчастникИсправил бразильскую версию. Perft совпадает
Вот значения для пула:
1 - 7
2 - 49
3 - 302
4 - 1469
5 - 7482
6 - 37986
7 - 190146
8 - 929902
9 - 4570615
10 - 22442551
11 - 110877932
12 - 544300084
13 - 2670481140
05.03.2007 в 14:42 #364675NSУчастникЯ никак не могу найти — чем правила Пула отличаются от правил Чеккерса?
добавлено
Всё, нашел — бразильские без правила обязательного взятия большинства.17.03.2007 в 23:58 #364676arpegУчастникДавно уже хотел удовлетворить свое любопытство и проверить свою программу генерации возможных ходов. Но поскольку она создана мной, когда я знал практически одну стандартную функцию, то пришлось поработать, чтобы избавиться от возникающих проблем.
Программа была создана около семи лет назад. После этого изменения больше не вносились. В алгоритм генерации входит еще несколько функций. Сейчас, конечно, я понимаю, что был не прав. Это сильно замедлило генерацию. Хотя одна из них – очистка от лишних ходов (лишний ход – это тот ход, который приводит к такой же позиции, что и один из предыдущих) – возможно, и не лишняя. Точнее сказать, такая очистка в одном случае может быть оправдана, а в другом – попросту «вредна».
Вот мои данные генерации возможных позиций на разных уровнях, начиная с начальной. В скобках результат Каллисто.
1. 7 (7)
2. 49 (49)
3. 302 (302)
4. 1469 (1469)
5. 7482 (7482)
6. 37986 (37986)
7. 190146 (190146)
8. 929899 (929905)
9. 4570586 (4570667)
10. 22436633 (22450628)
Как видно по сравнению с Каллисто различия начинаются с 8-го уровня. А на 10-ом уровне различия уже существенные.18.03.2007 в 03:47 #364677AlexanderSУчастник10. 22436633
а у меня сгенерировало 22444032 по такому алгоритму, до 9 включительно цифры совпадали
Точнее сказать, такая очистка в одном случае может быть оправдана, а в другом – попросту «вредна».
Я бы сказал что без разницы в любом случае.
Проверку на совпадение позиций можно делать довольно быстро. Во-первых, делать ее только в позициях со взятиями, так как два разных тихих хода в одну позицию не приведут. Во-вторых, во взятиях только нескольких шашек. А таких позиций не так уж и много, замедление получается небольшим. А скорость генерации на общую скорость перебора вообще влияет мало. В-третьих, нужно не проверять на дубликаты после того как мы уже сгенерировали все ходы, а делать проверку «по ходу» — при генерации очередного хода смотреть на уже сгенерированные — не совпадают ли позиции, если нет то добавляем ход.
Но поскольку к сильному сокращению дерева это не приводит, то что есть эта проверка что нет ее — для перебора практически без разницы.24.03.2007 в 12:25 #364678KvadratУчастникНельзя ли выложить текстовушку с вариантами всех первых 8 полуходов исключив из нее совпадающие позиции с перестановками ходов. Таких позиций должно быть существенно меньше чем 929905.
24.03.2007 в 14:54 #364679AlexanderSУчастникНельзя ли выложить текстовушку с вариантами всех первых 8 полуходов исключив из нее совпадающие позиции с перестановками ходов. Таких позиций должно быть существенно меньше чем 929905.
2 49 49
3 302 216
4 1469 805
5 7482 2806
6 37986 9610
7 190146 31051
8 929905 100413
-
АвторСообщения
- Для ответа в этой теме необходимо авторизоваться.