Нужен ли генетический алгоритм?

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

WinPooh:
Ссылку на кого-то из команды Ботвинника я тут видел. Но хочу сначала свои соображения собрать.
А до оптимизации - битбордов и т.п. хочу еще философию прояснить. Вынес это в тему "Шахматный язык".

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

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

Винни красиво сказал про ненаписанную программу.....

А есть действительно крупные математики которые и щас занимаются шахматами или покером?
Совместно с такими крупными программерами как, допустим, Винни или NS?)

Вообще программеры и математики взаимодействуют?
Или они щщитают что спецы и там и тут) и в кодинге и в математике)

NS, например, сам нехилый математик. В этом деле ему помощников не надо.
WinPooh Я только сейчас догадался - вас, наверное, именно за эту фразу в консерваторы и записали тут однажды. В "частичные"

И чем ценна программа Ботвинника? Подтасовками? Есть сейчас хоть какие-то сомнения что все решения (дерево перебора) были нарисованы лично Ботвинником? Фактически не было у него никакой программы.

Несмотря на вышесказанное, идеи Ботвинника не умерли. И даже находят свои удачные воплощения - в Рыбке 3, например.

Да ну! И какие же?

Угу, Юрий, поделитесь. Для тех, кто не читал исходники/декомпилят Рыбы 3.

Если мне не изменяет склероз, Рыба действует по принципу "Весна покажет". Решает поиск. Брутальнее Рыбы не отсекал никто.

Ботвинник же предлагал планировать, а не искать? Плохо помню детали.
Или просто какие-то фичи рыбной ОФ напоминают идеи взаимодействия фигур у Ботвинника.
HIARCS по слухам считает взаимодействие фигур.

А вообще, флеймогонная тема. У М.М. не было толком машины. В начале 90-х уже были машины царапающие гроссмейстерский уровень. Патриархи часто пытаются сорвать последний куш. Кто мы, чтобы их судить?

А.Тюринг, Шенон сформулировали верные идеи.
А вообще, чем плохо? У нас же есть Брудно с альфа-бетой, которая определила развитие шахматных машин. SCOUT/NegaScout/MTD(f) - всё перепевы её родной сурмяжной.

Не верю я Осипову на счет сырцов рыбы! Уж больно неправдоподобно все это. На счет дизассемблера верю, а на счет исходников - нет. Юрий - ждем от Вас обстоятельных разъяснений - ибо без них все ваши сообщения не более чем дешевые понты.

Рыба машина-зверь. Я заметил, что каждый ее ход направлен на увеличение активности ее фигур — у статических факторов позиции тем временем меньший вес.

Разговоры типа "верю - не верю" уже надоели. Одни верят в одно, другие в другое. Никакие обстоятельные разъяснения в таких случаях не помогают. Каждый все равно остается при своем мнении.

И делиться секретами Рыбки я не имею права. Обращайтесь к автору.

А зачем тогда было вообще поднимать тему сырцов рыбки?
После подобных разъяснений я Вас уже не воспринимаю серьезно как программиста.
Это всего лишь мое личное имхо.

Вот, интересный Вы, Юрий, человек.
Вам доставляет кайф намекать на то, что Вы знаете некую тайну? Распространённый "массонский синдром".

Да, без проблем. Просто я не верю, а знаю, что декомпиляция - простой процесс. При тренировке и знании предметной области - тривиальный, пусть и кропотливый. Многих этому учат в ВУЗ-ах. Дальше сплошные вероятности, но, согласитесь, когда мне звонят в дверь, резоннее предположить свидетелей Йеговы, чем Маньку Белушши в одних тапках.

Нашли что-то интересное? Поделитесь идеей! Чего стоит голая идея без мелочей реализации?
В данном случае прав Коззи с его открытым письмом. Нашел - поделись!

С Уважением

Сырдон

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

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

Конечно, общую структуру программы таким путем понять можно, и даже какие-то элементы алгоритма. Но получить рабочие исходники – извините. Тем более не на ассемблере, а на Си.

P.S. Не помню, чтобы Коззи с кем-то делился. А уж делиться не своим совсем некрасиво.

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

dan77790 тебе на форум sdchess.net

А что бы и тут не ответить?

Осипов Юрий вы так и не сказали - зачем вы начинали весь этот "базар", что у вас есть исходники рыбы 3? Чего хотели добиться? Кого хотели подразнить или поддеть? Ну если не хотите открывать, или хотябы осветить основные моменты, то тихонько бы смотрели бы на них и медитировали! И очень я сомневаюсь, чтобы команда Райлиха передала сырцы актуальной программы, которая неплохо продается конкуренту. Может у Вас еще есть исходники Windows 7?

Да вы посмотрите на код Стрелки. Попробуйте написать что-то подобное. А потом можно будет обсудить насколько Юрий хороший программист

А если уж тут вспомнили Коззи то давайте вспомним что он сказал о Стрелке:
"Anyway, from an engineering standpoint Strelka (rybka) is fantastic."
Думаю что это потрясающая оценка

@Chemer

Неверно. Юрий - очень квалифицированный программист. И это не ставится под сомнение. Решпекты, по-любому.

@Юрий
Ну, вот уже и интересная дискуссия получается.

Он вопил о конфликте асспиранта и соревновательного программиста.
Безусловно, конфликт присутствует. Шахматное программление - прекрасная тестовая область для поисковых задач. Однако делится народ очень не охотно. Та же фигня в самых вкусных областях. Оптимизация запросов в БД и т.д.

А Прометей? . Спорный вопрос. Если дали подержать, то безусловно атятяй. Если сам выковырял, то уже серая область. И хочется, и колется, и мама не велит.

recStudio рулит при всех её недостатках.
В комбинации с ida Pro - ещё круче.

Тут Вы эксплуатируете утверждение о невозможности чисто машинной компиляции. Тезис "из колбасы не получить поросёнка". Полу-ручная, "кентаврическая" декомпиляция простой процесс, если знаешь, что искать.

Неразличимость констант - это как? Как в Стрелке?
Распознать типичные константы в ходогенераторе на битбордах - проще паренной репы.
Смещений - тоже не ужас-ужас. Скажем, размер записи в хэше устанавливается на раз. Дальше дело техники.

Аааа, Вы про то, что константы не отличить от адресов? Нет. Это просто. Адреса ссылаются в сегмент данных, константы очень типичны. Например, при генерации ходов пешек константа для битбордов сразу в глаза лезет.

Золотые слова. Но Вы же отлично разбираетесь в предметной области! Вам же не нужно лезть в мелочи, для Вас программа будет состоять из знакомых уже элементов.

А дальше, как говорил незабвенный Рыбкин (Вы не знакомы?) писать код руками по мотивам.
И так до посинения - система проверки семантической идентичности нового кода и старого тоже возможна. Вызвать произвольную функцию в чужом exe с нужными парамами - CreateRemoteThread нам поможет.

Syrdon, ваш оптимизм по поводу декомпиляции, вероятно вызван изучением кода Анечки. Я тоже смотрел Анечку дизассемблером. То ли NS так пишет, то ли Дельфа так компилирует, но код в самом деле очень простой для изучения.
Код Рыбки на два порядка сложнее. В ней очень большой сегмент данных, диапазон адресов в котором очень широкий. Ида здесь часто путается - где константы в коде заменять на адреса, а где оставлять константами.

Теперь представьте себе такую романтическую картину.
У вас имеется примерно 400000 строк ассемблерного кода.
Он не такой прозрачный, как в Анечке. Он агрессивно оптимизирован, а местами обфусцирован. Логика с человеческой точки зрения запутана, связанные между собой куски разбросаны по разным местам, команды черт знает как переставлены.
И в этом коде содержится примерно две сотни далеко не очевидных багов.
Возьметесь такой код отладить, чтобы он хотя бы заработал как исходный EXE ?
А потом понять алгоритмы и переписать на СИ ? Или хотя бы написать "по мотивам" ?

Напомним, что оптимизм обоснованый. На разбор необходимых структур и почти полный (ОК, только за белых и только миттельшпиль) разбор ОФ ушло 4 часа.
Основной иснтрумент - декомпилятор в Си. Дизассм/отладчик - вспомогательный.
Для Анечки он даже не потребовался.

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

Не уверен, что оценка точная. Сегмент данных, код Налимова, CRT - в баню.
UCI обработку, управление временем - туда же.

Единица анализа - более-менее замкнутая функция (вход/выход/сторонние эффекты). Для ф-и почти всегда достаточно понять, что они делают и оставить как black box до поры до времени.

Юрий, Вы опять пытаетесь всё свести к "не в силах это человеческих".

Какие алгоритмы? Там довески к алгоритмам, а не алгоритмы. Там весь смак в блистательной Конкордии составляющих.

Альфа/Бету придумал Брудно почти 50(!) лет назад.
SCOUT описан Перлом в конце 70х.
NegaScout описан Райнфельдом в начале 80х.
Ноль-ход описан Билом чуть позднее и доведён Моршем до кондиции в 90-е.
Позднее отсечение - уже общее достояние. Самое позднее с публикации Fruit. Майер-Кален не скрывал, что в нём сила.

Не врал же Рыбкин, этот кристальной честности анонимус! А он очень чётко описал процесс декомпиляции. То, что его затюкали не имеет значения.

При всём уважении (не шучу), от Стрелки отчетливо пахнет рыбой.

Я просто прошу Вас занять более конструктивную позицию. Если Вы утверждаете, что в Рыбе 3 есть идеи Ботвинника, то обоснуйте. Народу же интересно.

Пессимизм обоснованный. И не у него одного.
Вы писали: "Со второго курса не имел с ассмом дела...". Но ИДА на компе у вас, однако, есть. С трудом как-то верится про 4 часа.

В треде разница между сообщениями была именно те самые 4 часа.
Как щаз помню, мусор вынес, купил хлеб и засел.

#1100 07/10/2007 16:29:35 -> NS "Ok".
#1105 08/10/2007 00:37:17 -> syrdon ...

Ну, вот, как раз, мусор вынес, хлеб купил и засел.
Может, ещё "по хате мусор собрал".

Продолжаем сказку про белого бычка.

Эта история всех впечатлила и оставила подозрение, что там ушло побольше времени. ОФ обычно спрятана глубоко в недрах форсированного поиска. А туда еще надо пробраться через рекурсию полного поиска. Правда, я Анечку так глубоко не смотрел. Может там и в самом деле все на поверхности.

Я говорил не про райлиховские баги, а про баги Иды. Из-за них собранная программа вообще не работает. И я не понимаю, как можно изучать программу, если ее даже запустить нельзя. Запуск исходного EXE в дебаггере – неинтересно. Надо иметь возможность что-то менять и экспериментировать.

Замкнутых в себе функций не бывает. Чтобы какая-то функция работала правильно, необходимо, чтобы в сегменте данных все было для этого подготовлено. Структура позиции правильная, ходы сгенерированы и много чего еще. И чтобы в функции не было глупостей от Иды.

Вообще-то складывается подозрение, что Рыбкин это Вы.

Естественно, пахнет. Потому как под Рыбку и подстраивалась. Фруктом пахнет тоже, потому что из него делалось. А вообще, таких движков, от которых пахнет другими движками – много. Авторы очень стараются это прятать поглубже. Я же, наоборот, старался, чтобы было максимально похоже на Рыбку.

Ишшо раз – не имею права.

А вообще, syrdon, у меня к вам предложение – еще раз проверить ваши потрясающие способности. Посмотрите Идой Рыбку 3 и ответьте на вопрос: каким числом оценивается мобильность слона? Неважно, сколько уйдет на это времени. Интересно вообще – возможно ли сделать такое в принципе?