6-7-фигурный эндшпильный генератор готов

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

С помощью баз получается настолько сильная игра, что игра самых лучших гроссмейстеров тут даже и рядом не стояла. Если бы были 32-фигурные базы, то можно было бы играя и за белых и за черных наилучшим образом, записать так сказать TheBest-партию, т.е. самую лучшую линию. Возможно, эта стартовая позиция шахмат уже изначально выигрышна для белых, но в этом случае, с 32 фигурми, до выигрыша будет не одна тысяча ходов. Менее вероятно, что эта позиция ничейна. Еще менее вероятно, что там выигрывают черные, т.к. позиции цугцванга с 32 фигурами - это редкость. Уверен, что если бы любой гросс, даже чемпион мира играл бы с такой программой с 32-фигурными базами, то он ВСЕГДА (!!) проигрывал бы программе, если бы даже брал у проги фору из стартовой позиции в целую ладью! (а возможно, даже и с лишним ферзем)

WildCat

Давайте не будем голословными. Если вы считаете что в DTM есть позиции с неверными оценками, при использовании базы прога может упустить выигрыш-ничью, то как говорится - ПОЗИЦИЮ В СТУДИЮ! Мы посмотрим что там у Налимова (ну и значит в моих базах то же должно быть), и вы покажете как там что можно упустить.

Практически уверен, что исходная позиция ничейна. Впрочем, это немножко оффтоп.

Ну и насчёт ферзя и ладьи это Вы подзагнули. Впрочем, проверить сие утверждение, конечно же, невозможно.

Базы Налимова на данный момент - лучшие в мире и их нельзя в чем-то обвинить. Ошибок в них не обнаружено и уверен, они не будут обнаружены никогда. (В базах Томпсона, читал немного ошибок все-таки обнаружили). Мои базы построены по тому же исчислению для легальных позиций, как и у Налимова, поэтому все количества позиций для всех оценок совпадают. Но у меня другой формат баз, потому что перевод в идентификаторы построен по-другому. Ну и на 20 % хуже сжатие. Зато у меня наилучшее соотношение параметров - скорость генерации - количество оперативной памяти. А для 7-фигурных необязательно иметь 20-140 ГБ оперативной памяти, это просто идеальный вариант, чтобы не было свопа. Можно генерировать и с 8 ГБ оперативки, просто время генерации замедлится раз в 5 из-за свопа. Зато такие компы намного дешевле и их можно много приобрести. Но я бы все-таки посоветовал при создании 7-фигурных баз иметь достаточно оперативки.

Надеюсь, на своем веку поюзаю не только 7-фигурные, а и 8-фигурные. Объем винчестеров за последние 10 лет увеличился в 1000 раз, ОП - тоже, надеюсь темпы роста не остановятся.

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

шахматы - это визуализатор борьбы с собственными ошибками

Skipper_NORTON

А если эту лишнюю ладью сразу подтянуть на защиту короля?) вообще окопаться понадежнее вокруг короля и ждать эндшпиль))))

Если вы про то, что правило 50-ти ходов не даст выиграть (базы Налимова не учитывают правило 50-ти ходов), то можно сгенерировать модифицируемый вариант баз, но метрика должна быть все равно DTM. Это самая точная метрика, для того чтобы игра была самой сильной. Я бы назвал модифицируемую метрику DTM-50. Она уже будет неидеально точной, похуже чем DTM, но по крайней мере, намного точнее чем DTZ. И неточностей в ней будет намного меньше. Просто при генерации баз добавить для каждой позиции значение, которое будет показывать, сколько ходов в будущем будет при идеальной игре без взятий и движений пешек. Если превысили лимит в 50 ходов - то помечать позицию условно-ничейной, и потом при дальнейшей генерации не ссылаться на нее как на выигрышную. Из-за этого, в дальнейшем много позиций будут построены с другими точными оценками, и программа не будет в большинстве случаев стремиться попасть на такую линию, где потом возникнет 50 ходов без взятий и дв. пешек. Но есть возможность когда возникнут позиции, помеченные таким вот образом как условно-ничейные, но теоретически может быть линия, отличающаяся от идеальной, но ведущая к взятию или продвижению пешки чуть пораньше - скажем на 49-м ходу. Замечу, что > 99% условно-ничейных позиций под такую категорию не попадут. Почему? Потому что обычно идеальная игра выливается со временем или к взятию фигуры или к продвижению пешек, поэтому ЕСЛИ ПО DTM получилась позиция условно-ничейной, т.е. за 50 ходов этого нельзя сделать, то с большой вероятностью этого и в принципе нельзя сделать. Ведь мы установили только что это нельзя сделать за 50 ходов, а там может быть на самом деле и 70 и 100 и 200. Альтернативные линии которые могут привести к взятию-дв.пешки скажем на 49-м ходу, могут быть только для очень узкого круга позиций, идеальные линии которых не ведут к этому скажем за 50-55 ходов. К тому же, как выше уже говорил, мы отсеем множество позиций, которые с большими оценками (в 100-200) - просто не будут стремиться попасть на линии где в будущем возможна такая ситуация с 50-ю ходами без взятий-дв. пешек. Они необязательно будут ничейными, просто могут быть оценены по-другому.

Если я буду писать генератор с учетом правила 50-ти ходов, то наверное, буду делать именно DTM-50. У DTZ и DTZ-50 неточностей гораздо больше. Меня просто раздражает когда программа считает равноценными варианты - поставить мат через 5 ходов, и выиграть фигуру или отдать фигуру через 4 хода а потом до мата еще 50 ходов трудной игры! DTZ - это плохо. Но самая точня метрика - чисто DTM, а правило 50-ти ходов должно распространяться я считаю только на людей. Т.к. если человек не может выиграть за 50 то он скорее всего и не выиграет а будет только мучить соперника. А если программа МОЖЕТ выиграть, скажем за 70, то зачем ей запрещать это??? Недаром раньше делали исключения из правила 50 ходов (увеличивали и до 75 и до 100)

Позиция без ладьи явно прогрышная. Программа будет делать самые лучшие ходы, и они будут не ничейными, а проигрышными. Когда она отыграет материал, и позиция станет равной по материалу, то программа начнет делать ничейные ходы. Замечу, что это будут НАИЛУЧШИЕ ходы, из наилучшего множества, и достаточно человеку сделать малейшую ошибочку, как он попадает уже в проигрышную позицию. Программа же таких ошибок не сделает.

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

Вообще, ошибку у Налимова, НО НЕ В БАЗАХ, а в подсчетах числа позиций по множествам я заметил... Т.е. tbs-файлы со статистикой содержат ошибку. Базы у Налимова точнейшие и ошибок не содержат. В tbs-файлах при подсчете очевидно использовалась 32-разрядная целочисленная переменная, у которой происходило переполнение, если число становилось больше чем 2 в 32-й степени, т.е. около 4 млрд. Но таких неправильных множеств очень мало. Например KBBP-KR, там больше 4-х млрд - только ничейных с ходом черных. Их там около 5 млрд. Произошло переполнение и 4 млрд "сбросились", поэтому в tbs-файле указано только около 1 млрд. Я же в своем генераторе при подсчете использую int64, поэтому у меня подобных переполнений нет. Повторюсь, сами базы у Налимова точны, и безошибочны.

Окопаться не успеешь... Если не стартовая позиция, а уже модифированная, то возможно.

Я чего то не понял насчет ходов базы, ведущей к ничьей без ладьи. Таких ходов не существует, есть только 2 пути сопротивления —- наиболее вероятен путь уклонение от разменов, закрытие позиции, но все равно неизбежный переход в эндшпиль без ладьи. Игра будет долгой, но с неизбежным результатом, с целью бессмысленно сопротивляться побольще ходов ( это цель таких баз ). Второй путь - тоже закрытие позиции с паралельной постановкой перед соперников некоторых проблем. Позиционных или тактических ловушек. Ну и на короля без материала умные движки любят нападать. В общем движок без материала играет более практично, с реальными шансами на ничью или выигрыш. На сверхкоротком контроле разумеется. Или в блиц, но не с гроссом.
Да и в привычной 6-ти фигурке база делает не идеальные ходы, а наиболее формально затягивающие борьбу, часто безвольно ведущие к неизбежному проигрышу. Движок играет часто более практично, с реальными шансами на защиту.
В общем в классику не то что ладью, а и фигурц НИКОГДА база не сможет дать не только гроссу, а и приличному кмс.
Ведь в партиях действительно есть куча ошибок, но это борьба. А тут ясная стратегия поменять и реализовать.

Тут не надо быть эстетом... DTM - это самый лучший вариант. Жалуется же народ, что по DTZ-50 программа вместо того чтобы поставить мат в 5 ходов делает размены через 4 хода а потом играет до мата 30 ходов! Вообще, самый лучший вариант - просто иметь 2 типа баз - чистый DTM (мои или Налимова) и DTC-50. DTC-50 думаю, будут весить в раза меньше чем DTM, итого полный комплект будет всего лишь на 50 % больше весить чем у Налимова (DTM). Смотрим - по DTM математически самый сильный ход, выигрышный ли с учетом правила 50-ти ходов (для этого заглядываем в DTC-50)? Если да - то его делаем, если нет, то программа смотрит, есть ли другой выигрышный с учетом правила 50 ходов в DTC-50. Очень редко - будет, и ради этого базы будут на 50 % больше весить.

И глюков никаких и игра самая сильная.

kirr. Партии между программами можно прерывать и через 100 например. 50 - это очень мало все таки...

Короче, скоро выложу в интернете 2-ю версию своего генератора, DTM, распрараллеливаю на потоки, хотя и не все. Оптимизировал работу с винчестером. Создает базы в 3 раза быстрее (!) чем генератор 1-й версии, который я выкладывал в интернете.

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

А я вот не понимаю, если проги могут возить ничейную позу из таблиц Налимова бесконечно, то как ваще эти таблицы Налимова выяснили что поза ничейна? Рассчитали бесконечность?
Или там повторы начинаются...

Kirr.

Вы просили показать пример кода для работы с базами. На данный момент я в dll реализовал только функцию GetEvaluateFromFEN, которая принимает позицию как строку, в формате FEN. В позициях не должно быть рокировок. Пример строки - "4k3/8/8/Pp6/8/8/8/4K1Q1 w - b6" - со взятием на проходе, пешку b5 на поле b6. "4k3/8/8/Pp6/8/8/8/4K1Q1 w" - без взятия на проходе (последний должен быть символ - 0, после 'w'). Если возвращает -10000, то или позиция нелегальна, или нет соответствующей базы. Нужно просто подключить к вашей шахматной программе ChessDLL.dll, ChessDLL.lib, и ChessDLL.h. Там же определены функции

void* InitCHESS();
short GetEvaluateFromFEN(void* CHESS, char* FEN);
void DeleteCHESS(void* CHESS);

Сначала вызываем InitCHESS, потом этот указатель void* передаем в функцию GetEvaluateFromFEN и также передаем строку FEN. Например,

void* p = InitCHESS();
// ... далее определяем строку FEN и указатель на нее f
short value = GetEvaluateFromFEN(p, f); // здесь уже получаем оценку
//в конце не забыть освободить память с помощью DeleteCHESS

В value будет оценка позиции, за сколько ходов позиция выиграна, если отрицательное значение то выигрывают черные, если положительное - то белые. Если 0 - то ничья. Так программно можно использовать мои базы. Если после всех ходов вы получите оценки то можете в своей программе их сравнить и ваша программа может выбрать самый лучший ход... Пока интерфейс небольшой, позже могу предоставить dll с большими возможностями.

dan77790

Генератор путем ретроанализа ищет все выигранные позиции. Если ретроанализ закончен а какие-то позиции не помечены, то они автоматически остаются ничейными, т.е. ни белые ни черные не могут выиграть при правильном сопротивлении противника.

А методика этого ретроанализа секретна?)

Ничего секретного. Можно найти в инете. Главная трудность - не сам алгоритм ретроанализа, а хорошо оптимизировать по параметрам время генерации - количество используемой оперативной памяти. Т.к. именно это может удешевить стоимость мощных компьютеров генерирующих 7-фигурные базы. Комп с 48 ГБ оперативки и 500 ГБ - по стоимости отличаются сильно. Также, скорость генерации очень важна, т.к. создаваться 7-фигурные будут долгие годы, и выиграть скажем 5 лет, т.е. построить базы на 5 лет раньше - тоже очень существенный фактор. Именно поэтому я так сильно и долго все оптимизировал и скоро выложу в интернете свою вторую версию генератора. Если мне не по карману пока приобрести такие мощные компьютеры чтобы построить 7-фигурные базы (я у себя дома могу только 6-фигурные строить), то надеюсь кто-нибудь построит 7-фигурные.

Нет, все просто. Например, рассмотрим окончание дамка против дамки на доске 3x3 (угловые поля черные). Симметрию учитывать не будем. Всего доступно пять полей, это 5 * 4 * 2 = 40 позиций с учетом очереди хода. Запираний нет, о них не беспокоимся. Позицию буем писать в формате "a xx yy", где a это b или w-—кто ходит, xx это положение белой шашки, yy черной.

Итерация первая: рассматривам все позиции. Если в позиции возможно взятие, то оценка позиции M[1] или M[-1] в зависимости от того, кто ходит. Итого, следующие позиции (8) получают оценку
M[1]: w a1 b2, w c1 b2, w a3 b2, w c3 b2
M[-1]: b b2 a1, b b2 c1, b b2 a3, b b2 c3
(во всех тривиальное взятие)

Итерация вторая, рассматриваем все позиции. Если из позиции все ходя приводят к позициям с оценкой, ставим им оценку M[2] или M[-2] в зависимости от очереди хода: Итого, следующие позиции (8) получают оценку
M[2]: b a1 c3, b c1 a3, b a3 c1, b c3 a1
M[-2]: w a1 c3, w c1 a3, w a3 c1, w c3 a1
(во всех позициях возможен единственный ход, который приводит к позиям с оценкой M[1] или M[-1]

Итерация третья, рассматриваем все позиции. Если в позиции есть хотя бы один ход, который приводят к оценке M[2] или M[-2], то ставим оценку M[3]. Это позиции (8):
M[3]: w b2 a1, w b2 c1, w b2 a3, w b2 c3
M[-3]: b a1 b2, b c1 b2, b a3 b2, b c3 b2
(везде в этих позициях есть ход в угол—-запирание)

Итерация четвертая, рассматриваем все позиции. Если из позиции все ходя приводят к позициям с оценкой, ставим им оценку M[4] или M[-4] в зависимости от очереди хода. Но таких позиций нет. Поэтому все остальные позиции (16) отмечаются как ничейные.
M[0]: w a1 c1, w a1 a3, w c1 a1, w c1 c3, w a3 a1, w a3 c3, w c3 c1, w c3 a3
M[0]: b a1 c1, b a1 a3, b c1 a1, b c1 c3, b a3 a1, b a3 c3, b c3 c1, b c3 a3

Итого получаем, что все 8 + 8 + 8 + 16 = 40 позиций получили оценку.



Единственное у меня затруднение, что делать в играх по типу сянци, где в случае троекратного повторение засчитывается поражение тому, что его вынуждает...

а в Го ретроанализ бессмысленнен?)

Имеет смысл на маленьких досках. Например, го на доске 5x5 решено как раз при помощи ретроанализа. А так поскольку в го нет перехода в младший эндшпиль, то ретроанализ можно проводить только для всей игры целиком, что занадто.

А как думаете, 10-фигурники когда появятся?)

думаю к 2015-му году - 7-фигурники, к 2030 - 8-фигурники, к 2060 - 9-фигурные, к 2100 - 10-фигурные.

Ну что, нам спешить некуда... Подождем....

Кстати по разным вопросам проще обратиться к создателям 7-ми фигурки. Один из них, Яков, еще и на этой гостевой засветился http://kasparovchess.crestbook.com/viewtopic.php?id=450 .

Kirr а вы не подскажите как прикрутить неналимовские таблицы к СВ оболочке?

Kirr.

Вопрос нужно разделить на две части. 1 - чем базы в формате DTM лучше чем DTC-50 или DTZ-50? 2 - наоборот, чем именно базы DTZ-50 лучше чем DTM? Если исходить из того, что базы нужны только для того, чтобы программа могла выиграть (причем по принципу "лишь бы выиграть", т.е. неважно как, пусть и с нелепыми разменами) у другой программы, которая тоже использует базы, то DTZ-50 лучше но только чуть-чуть. Почему чуть-чуть? А насколько это повысит рейтинг программы? Предположим, рейтинг программы которая играет вообще без баз - 2600. Предположим, используя 6-7-фигурные - у нее рейтинг будет 2650. Точно больше чем на 50 не повысится, т.к. многие партии заканчиваются с большим количеством фигур. Но конкретно таких ситуаций (попаданий) где будут использованы случаи, с невозможностью выиграть за 50 ходов без взятий и движений пешек - еще НАМНОГО меньше, в десятки-сотни раз! Это увеличит ее рейтинг еще максимум - на 1. Поэтому, если программа получит рейтинг 2650 по DTM, то он DTZ-50, будет 2651. А с человеком, и вообще разницы не будет, т.к. почти никто не выдержит самой идеальной игры по DTM более 50 ходов. Человеку же свойственно ошибаться. Итак, преимущество DTZ-50 - только + 1 к рейтингу и то, в случае игр программ именно с программами, тоже имеющими базы.

Теперь подумаем чем DTM лучше. Предположим, я анализирую какую-нибудь свою партию или каких-нибудь гроссмейстеров. Насколько точно я сыграл в каждой позиции (или гросс сыграл)? DTM покажут правильно, точно и всегда, а DTZ-50 могут показать ерунду, которую выше уже описали. Далее, предположим, я играю с человеком, партию несколько дней, т.е. можно откладывать, дома анализировать и т.д. По DTM опять же, я вижу правильные варианты. А пользуясь DTZ-50 я могу ухудшить свое положение! Т.е. попасть в позицию, где мне будет труднее выиграть. Я уже описал пример такого случая, вкратце повторю, может кто не читал моего поста выше. На доске (кроме королей) - белый ферзь против 3-х легких фигур, скажем коня и двух слонов. Черный король оттеснен в угол и ферзь может быстро, скажем за 5-10 ходов поставить мат, а может также выиграть коня, но тогда король черных вырвется из угла и потом нужно будет бороться с ферзем против двух слонов до мата еще 50 ходов. Базы DTM покажут всегда лучший ход, который всегда максимально улучшит положение, а DTZ-50 покажут вариант - с выигрышем коня, если его использовать то потом может, вообще выиграть не получится, т.к. человек играет неидеально. Такой эндшпиль редко встречается, я просто привел его для наглядности. На самом деле таких случаев хватает. Или вот я решил потренировать свою игру в каком-нибудь эндшпиле. Играю с программой, которая использует базы. Кажется, всё, выиграть не смогу, программа построила неприступную крепость, а базы показывают что у меня позиция выигрышная. Если я решил воспользоваться подсказкой компа, то хочу увидеть действительно наилучшие продолжения (максимально математически улучшающие положение) а DTZ-50 может показать ерунду, т.к. там принцип "лишь бы выиграть, неважно как". Наконец, DTM можно еще использовать и для всяких математических теорий - как правильнее дать оценку позиции когда будет 8 и более фигур, т.е. сравнивая позиции 7-фигурные, можно будет классифицировать разные их особенности и строить теории всяких плюсов и минусов. Мы можем их точно сравнивать по DTM а по DTZ-50 не можем. А правило 50 ходов здесь вообще не должно учитываться, если мы хотим изучить теорию взаимодействия фигур, то должны знать случаи, когда позицию можно и за 200 ходов выиграть.

Поэтому базы DTM имеют бОльшую теоретическую и практическую ценность, чем увеличения рейтинга программы на 1 и то только при игре с другими программами имеющими базы. Да и чисто, больший человеческий интерес...

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

Что касается более быстрого обрашения... Во сколько полные (не битовые) базы DTZ-50 меньше чем DTM ? Думаю, процентов на 50... Базы хранятся на жестких дисках, к ним время доступа большое - около одной миллисекунды. Далее если требуется какое-нибудь значение, то кэшируется в оперативную память какой-нибудь участок (линия), таких участков может быть много. А винчестер все равно блоками читает, поэтому этот блок и записывается в ОП, потом если понадобится оттуда значение, то программа получит его уже из ОП. Принцип кэширования таков. Чем больше кэш тем следующее его увеличение дает меньшую эффективность. В процессорах тоже есть кэш и процессор к нему обращается в 10 раз быстрее чем к оперативке. Так вот сравнивали процы с кэшами отличающимися в 3 раза - а во всем остальном они были одинаковыми, разница в производительности всего на 13 % ! А у нас разница между DTZ-50 и DTM вообще маленькая. Может, на 2 % по времени программа с DTZ-50 и быстрее отработает, так это время и некритично - программы всегда все равно его с запасом используют. Это преимущество, если честно не повысит рейтинг программы даже и на 1, а может даже понизить, т.к. если ей придется потом выигрывать на 50 ходов дольше чем по DTM - то вдруг время закончится?