Вы не вошли. Пожалуйста, войдите или зарегистрируйтесь.
Какая то странная математика)
Ну ок, я кароче говоря ниче не понял)
Главное чтобы тебе не поставили мат на ход раньше, чем утверждает эта прога)
Skipper_NORTON пишет:У DTM никаких проблем нет. Чисто с математической стороны - это самая сильная игра в шахматы.
Правда что ли?
С математической точки зрения DTC (distance to conversion) сильнее играет в шахматы.
Не согласен. Вот пример позиции
http://en.wikipedia.org/wiki/Tablebase
где объясняется отличие DTM и DTC. Белые - Крb6, Фc2, черные - Крb8, Лd1.
Ферзь может пойти на c7 и поставить мат в 2 хода. А если он возьмет ладью то мат будет в 3 хода. Т.е. ход 1.Фc7 ведет к DTM #2, а 1.Ф:d1 к DTM #3. Т.е. по DTM ход 1.Фc7 ЛУЧШЕ чем 1.Ф:d1 , ведь лучше мат поставить в 2 хода чем в 3 хода 
А по DTC (distance to conversion) -- выигрыш ладьи приравнивается к мату т.е. 1.Ф:d1 к DTC #1 , 1.Фc7 приводит к DTC такому же как DTM #2.
Считать выигрыш ладьи лучше чем раньше поставить мат - неправильно, я могу привести пример позиции, где такой подход к оцениванию будет просто абсурдным. Скажем, позиция такая - кроме королей на доске 1 белый ферзь против 3 черных легких фигур (например 2 слона и конь). Хотя по фигурам материал равен по силе, но король черных оттеснен в угол доски и ферзь может не беря ни одной черной легкой фигуры быстро, за 5 ходов поставить мат. А тут черные ставят под бой коня, чтобы отвлечь ферзя и вырваться королем из угла. Что будет по DTC ? Правильно, лучший ход - забрать коня. Потом король черных вырывается из угла и борись с ферзем против оставшихся 2-х слонов ходов 50 до мата.
DTM - the best
Отредактировано Skipper_NORTON (05/01/2009 20:40:56)
согласен Налимов игру не портит. Недавно наблюдая игру движков в эндшпиле, нарывался на подобные сюрпризы. Двиг видя переход в выйгранный энд, например, отдает фигуру(лишнюю) за пешку и далее мательник в 30 ходов например. не факт, что с лишней фигурой он так быстро бы управился
Ну что тут обсуждать? Мат - это ВЫИГРЫШ в прямом смысле слова, его значимость должна перевешивать всевозможные другие факторы! Надо просто забыть другие возможности, там... выигрыш фигур или переходы в какие-то младшие эндшпили или еще что-нибудь подобное. Так можно напридумать еще что-нибудь - кроме выигрыша фигур. Выигрыш фигуры кстати, еще не значит максимального усиления позиции, бывает наоборот, ослабление! Иначе не было бы такого понятия как "жертва". Напридумали всяких метрик, DTZ, DTC, я выдумщикам могу еще альтернативный вариант подбросить - учитывать позиционные факторы.
Если писать базы которые должны полностью исчерпывающе оценить игру (любую, не обязательно шахматы) и все переходы в ней, то нужно исходить из главного - есть 3 конечных состояния - выигрыш-ничья-проигрыш и расстояние до них. Всё. С таким подходом базы будут приводить к самой сильной игре из любой области - игра Го, шашки, и т.д.
В математическом смысле DTC обеспечивает идеальную игру - всегда делается ход не меняющий оценки позиции.
В DTM базах есть позиции с неверными оценками, т.е. движок может упустить выигрыш/ничью при ходе в такую позицию.
согласен Налимов игру не портит. Недавно наблюдая игру движков в эндшпиле, нарывался на подобные сюрпризы. Двиг видя переход в выйгранный энд, например, отдает фигуру(лишнюю) за пешку и далее мательник в 30 ходов например. не факт, что с лишней фигурой он так быстро бы управился
Скажем так. Если бы у него была база с бОльшим количеством фигур (на позицию, до того как он отдал фигуру), то движок может фигуру и не отдавал бы и выиграл бы еще быстрее. Но на ту позицию у него базы нет. Без базы он играет намного слабее, поэтому даже с лишней фигурой он возможно будет дОльше выигрывать, чем отдав фигуру, но играя по базе, т.е. получив действительно самую сильную игру.
С помощью баз получается настолько сильная игра, что игра самых лучших гроссмейстеров тут даже и рядом не стояла. Если бы были 32-фигурные базы, то можно было бы играя и за белых и за черных наилучшим образом, записать так сказать TheBest-партию, т.е. самую лучшую линию. Возможно, эта стартовая позиция шахмат уже изначально выигрышна для белых, но в этом случае, с 32 фигурми, до выигрыша будет не одна тысяча ходов. Менее вероятно, что эта позиция ничейна. Еще менее вероятно, что там выигрывают черные, т.к. позиции цугцванга с 32 фигурами - это редкость. Уверен, что если бы любой гросс, даже чемпион мира играл бы с такой программой с 32-фигурными базами, то он ВСЕГДА (!!) проигрывал бы программе, если бы даже брал у проги фору из стартовой позиции в целую ладью! (а возможно, даже и с лишним ферзем)
WildCat
Давайте не будем голословными. Если вы считаете что в DTM есть позиции с неверными оценками, при использовании базы прога может упустить выигрыш-ничью, то как говорится - ПОЗИЦИЮ В СТУДИЮ! Мы посмотрим что там у Налимова (ну и значит в моих базах то же должно быть), и вы покажете как там что можно упустить.
Отредактировано Skipper_NORTON (05/01/2009 21:14:04)
Практически уверен, что исходная позиция ничейна. Впрочем, это немножко оффтоп.
Ну и насчёт ферзя и ладьи это Вы подзагнули. Впрочем, проверить сие утверждение, конечно же, невозможно.
Отредактировано foreveryoung (05/01/2009 21:27:07)
Базы Налимова на данный момент - лучшие в мире и их нельзя в чем-то обвинить. Ошибок в них не обнаружено и уверен, они не будут обнаружены никогда. (В базах Томпсона, читал немного ошибок все-таки обнаружили). Мои базы построены по тому же исчислению для легальных позиций, как и у Налимова, поэтому все количества позиций для всех оценок совпадают. Но у меня другой формат баз, потому что перевод в идентификаторы построен по-другому. Ну и на 20 % хуже сжатие. Зато у меня наилучшее соотношение параметров - скорость генерации - количество оперативной памяти. А для 7-фигурных необязательно иметь 20-140 ГБ оперативной памяти, это просто идеальный вариант, чтобы не было свопа. Можно генерировать и с 8 ГБ оперативки, просто время генерации замедлится раз в 5 из-за свопа. Зато такие компы намного дешевле и их можно много приобрести. Но я бы все-таки посоветовал при создании 7-фигурных баз иметь достаточно оперативки.
Надеюсь, на своем веку поюзаю не только 7-фигурные, а и 8-фигурные. Объем винчестеров за последние 10 лет увеличился в 1000 раз, ОП - тоже, надеюсь темпы роста не остановятся.
Допустим в позиции по DTM мат в 100 ходов. Как мне узнать это выигрыш или ничья?
Были где-то ветки Kirr'a с рекордами до мата и до перехода в другую базу.
Менее вероятно, что эта позиция ничейна.
Общепринято считать шахматы ничьей.
даже чемпион мира играл бы с такой программой с 32-фигурными базами, то он ВСЕГДА (!!) проигрывал бы программе
База сама не может выигрывать ничейную позицию (для этого нужен хороший движок). Разве только изредка из-за зевков человека.
если бы даже брал у проги фору из стартовой позиции в целую ладью!
Шутка юмора?
(а возможно, даже и с лишним ферзем)
С лишним ферзем даже я обыграю любую базу.
Ладно, насчет лишнего ферзя я может и подзагнул Но насчет ладьи - уверен на все сто процентов. Мое утверждение - "если бы любой человек играл с программой которая использовала бы 32-фигурные базы, то он всегда проиграл бы ей из стартовой позиции минус ладья (фора для человека)". Почему? Я смотрю партии гроссмейстеров - видно, что часто один другому проигрывает от того, что допустил в дебюте или миттельшпиле малозаметную ошибочку, что потом приводит к атаке на короля. На самом деле такие ошибочки происходят у всех и в каждой партии, просто не каждый противник это может увидеть, а программа играющая идеально используя базы - увидит точно. Думаю, в каждой партии с такой программой будет мощнейшая, ИДЕАЛЬНАЯ атака на короля от которой очень трудно защититься, а главное - лишняя ладья где-нибудь в противоположном углу просто не будет играть никакой роли. В результате атаки человек просто потеряет материал (если вообще не получит мат), и в лучшем случае перейдет в эндшпиль уже при равном материальном соотношении. А далее - понятно - в эндшпиле материал равен но идеальная игра программы против далеко неидеальной игры человека. Я сколько раз видел, как знаменитые гроссмейстеры в эндшпилях допускали детские, непостижимые ошибки.
шахматы - это визуализатор борьбы с собственными ошибками
Skipper_NORTON
А если эту лишнюю ладью сразу подтянуть на защиту короля?) вообще окопаться понадежнее вокруг короля и ждать эндшпиль))))
Думаю, в каждой партии с такой программой будет мощнейшая, ИДЕАЛЬНАЯ атака на короля от которой очень трудно защититься
Вообще никаких атак и ни на что не будет!!! База будет делать случайные ведущие к ничьей ходы - в такой ситации гроссу ничью сделать, как два пальца апасфальт.
Допустим в позиции по DTM мат в 100 ходов. Как мне узнать это выигрыш или ничья?
Были где-то ветки Kirr'a с рекордами до мата и до перехода в другую базу.
Если вы про то, что правило 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)
Отредактировано Skipper_NORTON (06/01/2009 14:43:06)
Вообще никаких атак и ни на что не будет!!! База будет делать случайные ведущие к ничьей ходы - в такой ситации гроссу ничью сделать, как два пальца апасфальт.
Позиция без ладьи явно прогрышная. Программа будет делать самые лучшие ходы, и они будут не ничейными, а проигрышными. Когда она отыграет материал, и позиция станет равной по материалу, то программа начнет делать ничейные ходы. Замечу, что это будут НАИЛУЧШИЕ ходы, из наилучшего множества, и достаточно человеку сделать малейшую ошибочку, как он попадает уже в проигрышную позицию. Программа же таких ошибок не сделает.
Насчет ничейных. Жалуются что программа не умеет эндшпиль по базе играть на выигрыш, если позиция ничейная. Проблема только к в том что если позиция ничейна, то таких ходов (из лучшего множества - ничейного) много, а если выигрышна-проигрышна, то лучших ходов мало - обычно вообще 1-2. Ничто не мешает включить обычный переборчик (с обычными принципами - оттеснение короля и т.д.), на какую-нибудь глубину, но выбирать уже только из множества ничейных позиций.
Просто при генерации баз добавить для каждой позиции значение, которое будет показывать, сколько ходов в будущем будет при идеальной игре без взятий и движений пешек.
Т.е. параллельно еще и базу DTC строить? Не будет ли быстрее только ее и строить? Тогда DTM будет просто излишеством. И нужна будет только эстетам, таким как Skipper_NORTON.
WildCat пишет:Допустим в позиции по DTM мат в 100 ходов. Как мне узнать это выигрыш или ничья?
Были где-то ветки Kirr'a с рекордами до мата и до перехода в другую базу.Если вы про то, что правило 50-ти ходов не даст выиграть (базы Налимова не учитывают правило 50-ти ходов), то можно сгенерировать модифицируемый вариант баз, но метрика должна быть все равно DTM. Это самая точная метрика, для того чтобы игра была самой сильной. Я бы назвал модифицируемую метрику DTM-50.
При генерации DTM-50 есть практические сложности, которых нет у DTZ-50 или DTC-50.
Она уже будет неидеально точной, похуже чем DTM, но по крайней мере, намного точнее чем DTZ. И неточностей в ней будет намного меньше. Просто при генерации баз добавить для каждой позиции значение, которое будет показывать, сколько ходов в будущем будет при идеальной игре без взятий и движений пешек. Если превысили лимит в 50 ходов - то помечать позицию условно-ничейной, и потом при дальнейшей генерации не ссылаться на нее как на выигрышную. Из-за этого, в дальнейшем много позиций будут построены с другими точными оценками, и программа не будет в большинстве случаев стремиться попасть на такую линию, где потом возникнет 50 ходов без взятий и дв. пешек. Но есть возможность когда возникнут позиции, помеченные таким вот образом как условно-ничейные, но теоретически может быть линия, отличающаяся от идеальной, но ведущая к взятию или продвижению пешки чуть пораньше - скажем на 49-м ходу. Замечу, что > 99% условно-ничейных позиций под такую категорию не попадут. Почему? Потому что обычно идеальная игра выливается со временем или к взятию фигуры или к продвижению пешек, поэтому ЕСЛИ ПО DTM получилась позиция условно-ничейной, т.е. за 50 ходов этого нельзя сделать, то с большой вероятностью этого и в принципе нельзя сделать. Ведь мы установили только что это нельзя сделать за 50 ходов, а там может быть на самом деле и 70 и 100 и 200. Альтернативные линии которые могут привести к взятию-дв.пешки скажем на 49-м ходу, могут быть только для очень узкого круга позиций, идеальные линии которых не ведут к этому скажем за 50-55 ходов. К тому же, как выше уже говорил, мы отсеем множество позиций, которые с большими оценками (в 100-200) - просто не будут стремиться попасть на линии где в будущем возможна такая ситуация с 50-ю ходами без взятий-дв. пешек. Они необязательно будут ничейными, просто могут быть оценены по-другому.
Задача, всё-таки, выиграть, а не выиграть кратчайшим путём. DTM не гарантирует выигрыш выигранной позиции, из-за правила 50 ходов. DTM-50 вам вряд ли удастся так просто посчитать. DTZ-50 и DTC-50 - гарантируют выигрыш в выигранной позиции, и ничью в ничейной. Из них DTZ-50 компактнее, и поэтому предпочтительнее. Простые практические соображения.
Если я буду писать генератор с учетом правила 50-ти ходов, то наверное, буду делать именно DTM-50. У DTZ и DTZ-50 неточностей гораздо больше. Меня просто раздражает когда позиция считает равноценными варианты - поставить мат через 5 ходов, и выиграть фигуру или отдать фигуру через 4 хода а потом до мата еще 50 ходов трудной игры! DTZ - это плохо. Но самая точня метрика - чисто DTM, а правило 50-ти ходов должно распространяться я считаю только на людей. Т.к. если человек не может выиграть за 50 то он скорее всего и не выиграет а будет только мучить соперника. А если программа МОЖЕТ выиграть, скажем за 70, то зачем ей запрещать это??? Недаром раньше делали исключения из правила 50 ходов (увеличивали и до 75 и до 100)
Правило 50 ходов нужно, например, для того чтобы можно было прервать партии между программами. Без этого правила проги будут возить ничейное окончание бесконечно.
Вообще, ошибку у Налимова, НО НЕ В БАЗАХ, а в подсчетах числа позиций по множествам я заметил... Т.е. tbs-файлы со статистикой содержат ошибку. Базы у Налимова точнейшие и ошибок не содержат. В tbs-файлах при подсчете очевидно использовалась 32-разрядная целочисленная переменная, у которой происходило переполнение, если число становилось больше чем 2 в 32-й степени, т.е. около 4 млрд. Но таких неправильных множеств очень мало. Например KBBP-KR, там больше 4-х млрд - только ничейных с ходом черных. Их там около 5 млрд. Произошло переполнение и 4 млрд "сбросились", поэтому в tbs-файле указано только около 1 млрд. Я же в своем генераторе при подсчете использую int64, поэтому у меня подобных переполнений нет. Повторюсь, сами базы у Налимова точны, и безошибочны.
А если эту лишнюю ладью сразу подтянуть на защиту короля?) вообще окопаться понадежнее вокруг короля и ждать эндшпиль))))
Окопаться не успеешь... Если не стартовая позиция, а уже модифированная, то возможно.
Skipper_NORTON пишет:Думаю, в каждой партии с такой программой будет мощнейшая, ИДЕАЛЬНАЯ атака на короля от которой очень трудно защититься
Вообще никаких атак и ни на что не будет!!! База будет делать случайные ведущие к ничьей ходы - в такой ситации гроссу ничью сделать, как два пальца апасфальт.
Я чего то не понял насчет ходов базы, ведущей к ничьей без ладьи. Таких ходов не существует, есть только 2 пути сопротивления --- наиболее вероятен путь уклонение от разменов, закрытие позиции, но все равно неизбежный переход в эндшпиль без ладьи. Игра будет долгой, но с неизбежным результатом, с целью бессмысленно сопротивляться побольще ходов ( это цель таких баз ). Второй путь - тоже закрытие позиции с паралельной постановкой перед соперников некоторых проблем. Позиционных или тактических ловушек. Ну и на короля без материала умные движки любят нападать. В общем движок без материала играет более практично, с реальными шансами на ничью или выигрыш. На сверхкоротком контроле разумеется. Или в блиц, но не с гроссом.
Да и в привычной 6-ти фигурке база делает не идеальные ходы, а наиболее формально затягивающие борьбу, часто безвольно ведущие к неизбежному проигрышу. Движок играет часто более практично, с реальными шансами на защиту.
В общем в классику не то что ладью, а и фигурц НИКОГДА база не сможет дать не только гроссу, а и приличному кмс.
Ведь в партиях действительно есть куча ошибок, но это борьба. А тут ясная стратегия поменять и реализовать.
Я чего то не понял насчет ходов базы, ведущей к ничьей без ладьи.
Я говорил про игру без форы. Обсуждать игру без ладьи просто несерьезно.
При генерации DTM-50 есть практические сложности, которых нет у DTZ-50 или DTC-50.
Если одновременно с DTM-50 строить и DTC, то сложностей не будет. Либо можно еще проще сделать, строим DTМ, строим DTC, затем исправляем ошибки в DTМ c помощью DTC и получаем DTM-50.
И нужна будет только эстетам, таким как Skipper_NORTON.
Тут не надо быть эстетом... 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-й версии, который я выкладывал в интернете.
Отредактировано Skipper_NORTON (06/01/2009 16:05:07)
Да и в привычной 6-ти фигурке база делает не идеальные ходы, а наиболее формально затягивающие борьбу, часто безвольно ведущие к неизбежному проигрышу.
Наиболее затягивающие борьбу - это и есть самые лучшие ходы. Математически - они и затягивают больше всего, именно потому что у защищающейся стороны имеется больше всего контр-маневров и шансов. И достаточно сделать ошибочку - как ты уже и не выиграл а попал в ничейную позицию. Бывают только очень редкие исключения, когда наиболее затягивающие ходы, ведут к некой цикличности в маневрах, поэтому облегчают задачу, т.к. человек похожий этап прошел раньше. НО это крайне редко.
А я вот не понимаю, если проги могут возить ничейную позу из таблиц Налимова бесконечно, то как ваще эти таблицы Налимова выяснили что поза ничейна? Рассчитали бесконечность?
Или там повторы начинаются...
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
Генератор путем ретроанализа ищет все выигранные позиции. Если ретроанализ закончен а какие-то позиции не помечены, то они автоматически остаются ничейными, т.е. ни белые ни черные не могут выиграть при правильном сопротивлении противника.
Отредактировано Skipper_NORTON (06/01/2009 17:16:21)
А методика этого ретроанализа секретна?)
Ничего секретного. Можно найти в инете. Главная трудность - не сам алгоритм ретроанализа, а хорошо оптимизировать по параметрам время генерации - количество используемой оперативной памяти. Т.к. именно это может удешевить стоимость мощных компьютеров генерирующих 7-фигурные базы. Комп с 48 ГБ оперативки и 500 ГБ - по стоимости отличаются сильно. Также, скорость генерации очень важна, т.к. создаваться 7-фигурные будут долгие годы, и выиграть скажем 5 лет, т.е. построить базы на 5 лет раньше - тоже очень существенный фактор. Именно поэтому я так сильно и долго все оптимизировал и скоро выложу в интернете свою вторую версию генератора. Если мне не по карману пока приобрести такие мощные компьютеры чтобы построить 7-фигурные базы (я у себя дома могу только 6-фигурные строить), то надеюсь кто-нибудь построит 7-фигурные.
Отредактировано Skipper_NORTON (06/01/2009 17:22:11)
А методика этого ретроанализа секретна?)
Нет, все просто. Например, рассмотрим окончание дамка против дамки на доске 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.
Вы просили показать пример кода для работы с базами. На данный момент я в 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
Генератор путем ретроанализа ищет все выигранные позиции. Если ретроанализ закончен а какие-то позиции не помечены, то они автоматически остаются ничейными, т.е. ни белые ни черные не могут выиграть при правильном сопротивлении противника.
Skipper_NORTON, спасибо!
WildCat пишет:И нужна будет только эстетам, таким как Skipper_NORTON.
Тут не надо быть эстетом... DTM - это самый лучший вариант. Жалуется же народ, что по DTZ-50 программа вместо того чтобы поставить мат в 5 ходов делает размены через 4 хода а потом играет до мата 30 ходов! Вообще, самый лучший вариант - просто иметь 2 типа баз - чистый DTM (мои или Налимова) и DTC-50. DTC-50 думаю, будут весить в раза меньше чем DTM, итого полный комплект будет всего лишь на 50 % больше весить чем у Налимова (DTM). Смотрим - по DTM математически самый сильный ход, выигрышный ли с учетом правила 50-ти ходов (для этого заглядываем в DTC-50)? Если да - то его делаем, если нет, то программа смотрит, есть ли другой выигрышный с учетом правила 50 ходов в DTC-50. Очень редко - будет, и ради этого базы будут на 50 % больше весить.
И глюков никаких и игра самая сильная.
Задача всё-таки выиграть, а не выиграть кратчайшим образом. С таблицами DTZ-50 (или DTC-50), на самом деле, будет более сильная игра, чем с DTM. По той причине что таблицы DTM будут иногда упускать выигрыш, а DTZ-50 - нет. С таблицами DTZ-50 программа наберёт больше очков в турнире.
Так как таблицы DTZ-50 - компактнее, чем DTM, то обращение к ним будет быстрее, и следовательно программа сможет сделать больше обращений за единицу времени (либо с тем же количеством обращений больше посчитать самостоятельно). Что также прибавит силу игры. Именно по этой причине многие используют "битовые базы", например, Shredder и Scorpio - с ними игра сильнее, чем с DTM, несмотря на то что в DTM больше информации.
Если таблицы в одном формате гарантируют выигрыш, и к тому же занимают в разы меньше места, чем в другом формате, то только эстет предпочтёт второй формат.
kirr. Партии между программами можно прерывать и через 100 например. 50 - это очень мало все таки...
Тогда возникнет вопрос - почему через 100, а не, например, через 150? Ведь есть (наверное) выигрыши и в 200 ходов. Число 100 ничем не лучше чем 50. А вот у числа 50 преимущества существенные:
1. Так сложилось исторически что мы используем правило именно 50 ходов. Число же 100 или любое другое будет взято от фонаря.
2. Существующие движки используют правило 50 ходов. Оно в них жёстко зашито и нет параметра чтобы его поменять. Если сейчас начать переходить на правило 100 ходов, то старые движки придётся переделывать, или они будут играть в другие шахматы, чем новые движки.
3. С правилом 50 ходов играют белковые шахматисты. Таблицы, использующие правило 50 ходов, будут применимы и к человеческим шахматам. Таблицы без правила 50 ходов применимы с натяжкой, только за отсутствием альтернативы.
Короче, скоро выложу в интернете 2-ю версию своего генератора, DTM, распрараллеливаю на потоки, хотя и не все. Оптимизировал работу с винчестером. Создает базы в 3 раза быстрее (!) чем генератор 1-й версии, который я выкладывал в интернете.
Kirr а вы не подскажите как прикрутить неналимовские таблицы к СВ оболочке?
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 и то только при игре с другими программами имеющими базы. Да и чисто, больший человеческий интерес...
Отредактировано Skipper_NORTON (09/01/2009 14:58:37)
Так как таблицы DTZ-50 - компактнее, чем DTM, то обращение к ним будет быстрее, и следовательно программа сможет сделать больше обращений за единицу времени (либо с тем же количеством обращений больше посчитать самостоятельно). Что также прибавит силу игры. Именно по этой причине многие используют "битовые базы", например, Shredder и Scorpio - с ними игра сильнее, чем с DTM, несмотря на то что в DTM больше информации.
Я думаю, что битовые базы используются, т.к. выигрыш в 8 раз по месту на винчестере да и в оперативной памяти - чувствителен с финансовой точки зрения. Просто в 8 раз больше разновидностей 6-фигурных баз иметь на винчестере - это чувствуется, т.к. иначе многие базы просто отсутствовали бы (семь восьмых). Но с битовыми базами программа может и вообще не выиграть, т.к. там только выигрыши-невыигрыши хранятся, а нужно еще знать наилучший ход.
Что касается более быстрого обрашения... Во сколько полные (не битовые) базы DTZ-50 меньше чем DTM ? Думаю, процентов на 50... Базы хранятся на жестких дисках, к ним время доступа большое - около одной миллисекунды. Далее если требуется какое-нибудь значение, то кэшируется в оперативную память какой-нибудь участок (линия), таких участков может быть много. А винчестер все равно блоками читает, поэтому этот блок и записывается в ОП, потом если понадобится оттуда значение, то программа получит его уже из ОП. Принцип кэширования таков. Чем больше кэш тем следующее его увеличение дает меньшую эффективность. В процессорах тоже есть кэш и процессор к нему обращается в 10 раз быстрее чем к оперативке. Так вот сравнивали процы с кэшами отличающимися в 3 раза - а во всем остальном они были одинаковыми, разница в производительности всего на 13 % ! А у нас разница между DTZ-50 и DTM вообще маленькая. Может, на 2 % по времени программа с DTZ-50 и быстрее отработает, так это время и некритично - программы всегда все равно его с запасом используют. Это преимущество, если честно не повысит рейтинг программы даже и на 1, а может даже понизить, т.к. если ей придется потом выигрывать на 50 ходов дольше чем по DTM - то вдруг время закончится?
около одной миллисекунды
эхх, если бы оно так было! как бы здорово зажилось! 
расклад такой вобщем:
винты на 7200 об. имеют среднее время доступа от 13 до 16 мсек.
винты на 10000 об. имеют 7-10 мсек.
винты на 15000 об. имеют от 4-6 мсек.
винты SSD и флэш накопители имеют от 0.1 до 1 мсек.
при работе с таблицами флеш вне конкуренции! какой бы крутой винт вы бы не поставили, хорошая флешка или ssd его перебъет влегкую.
единственый минус - это цена таких дисков. ну и объемы еще не очень большие.
Модераторы, измените название этой темы. Уберите последнее слово, или поменяйте в нем букву "к" на "г"
Skipper_NORTON
Да коты прикольнее))
Модераторы, измените название этой темы.
А у самому некогда что ли?
ну так что, новая версия будет или нет?
ну так что, новая версия будет или нет?
Да уже есть. Но пока хорошо не прогоню свой набор тестов, не могу выкладывать в интернете. Нужна уверенность, что всё хорошо и правильно. Выложу в интернете через неск. недель.
WildCat
Я вижу только возможность отвечать или редактировать свои сообщения. А изменить название темы возможности не вижу.
Skipper_NORTON, попробуй отредактировать самое первое сообщение.
Skipper_NORTON, попробуй отредактировать самое первое сообщение.
Попробовал, все равно возможности изменить название темы не видно... Только сообщение можно изменить. 
6-7-фигурный эндшпильный генератор готов
на подходе генератор эмо
[ Сгенерировано за 0,129 секунд(ы), выполнено 8 запросов ]
