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

Сделал шахматы на C#. Программа всего 400 строк, выполняет перебор на 5 ходов.
http://www.aicommunity.org/members/no/chess.rar

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

Про ГА читал пару лет назад во время подготовки к экзамену по Информационным технологиям в менеджменте.

Но, меня заинтересовала тема искусственных нейронных сетей и возможности применения к программированию шахматных программ.

Нашел, что существует несколько программ на этот счет:

Morph: A Learning Program A UCSC project applying "Neural Networks" to chess ([email protected] [email protected])

http://satirist.org/learn-game/projects/morph.html
Morph represents chess knowledge as weighted patterns, which the papers refer to as "pws" for "pattern-weight pairs". The patterns are graphs of attack and defense relationships between pieces on the board and vectors of relative material difference between the players.

Morph uses a wide variety of learning methods to learn the patterns and their weights. Different methods add patterns, delete patterns, and set the weights. The methods include temporal differences, simulated annealing, a genetic algorithm-like method, generalization and specialization of patterns, and explanation-based generalization.

Morph is a learning chess program. MorphII is a programming environment to support experimentation in domains including machine learning of games. Both are results of an ambitious project headed by Robert Levinson <[email protected]> at UC Santa Cruz.



Программа играет где-то в силу 4-ого разряда.

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

У меня минимакс на 5 ходов. Наверно это самая стандартная стратегия из всех, и всем и так понятна.
В исходниках можно поменять эту цифру и ценность фигур тоже.

Наверно речь была про какой-то другой Китай

Schurick:

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

С ГА теоретическая сложность в том, что классический метод выполняет селекцию цепочки ходов только целиком, а фрагменты позиции и небольшие комбинаций ходов отдельно не существуют и не оцениваются. Их оценка завязана на способность всей цепочки их применить. В популяции хорошие ходы будут не шаблоном и числовой оценкой качества, а количеством генов, в которых этот ход используется. Это очень сильно снижает эффективность ГА.
Вообще это довольно абстрактная идея, много разных алгоритмов можно считать ГА, просто там обход какого-то дерева, а только популяция его "листьев".

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

Сделал шахматы на C#. Программа всего 400 строк, выполняет перебор на 5 ходов.
Ходов или полуходов?

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

Cаша:
С помощью ГА можно сделать мышление целыми комбинациями ходов, а не перебор отдельных. Возможно это увеличит скорость т.к. из разных эквивалентных комбинаций будет рассматриваться только одна, и можно будет рассмотреть больше длинных комбинаций, т.е. смотреть дальше. Я не утверждаю, что ГА что-то революционное, просто мне этот подход знаком, пробовал его в других областях, сейчас хочу так сказать взаимообогатиться идеями с культурой вокруг шахмат. Пока все представляю недостаточно ясно чтобы начать кодировать.
Вопрос тут какого рода абстракции вводить, т.е. обобщения. Группу комбинаций ходов можно считать одинаковой и выделить в целостную идею, если все они приводят к одной позиции или к "съедению" одинаковых фигур. Или если любой из них делает возможным или исключают возможность какого-то хода, или комбинации. Больше ничего нет? Хочется все же получать количественные оценки ход-сколько, а не просто результаты проверки цепочек ход-ход.

WinPooh:
UCI пока нет. Если есть, дайте пожалуйста ссылку с готовым кодом, может прикручу.

NS:
1. Полуходов. Вот тут уже засада. Настоящий "полуход" это например "Перевести ладью на клетку, где конь ее бьет только за 2 хода". Второй полу-ход это выбор конкретной клетки. Из них складывается один ход. Или второй полуход это "напасть на короля". Может быть только один ход, удовлетворяющий этим двум полуходам. Полуход это абстракция, о которых я и говорю, из которых складывается ход.

>>Программа не должна разгадывать цели человека, а должна делать лучший ход в текущей позиции.
А разве оценка, будет ли какой-то ход лучшим или худшим, не зависит от действий человека? Если мы хотим выбрать лучший ход, то должны знать ответные ходы человека.

NS:
1. Полуходов. Вот тут уже засада. Настоящий "полуход" это например "Перевести ладью на клетку, где конь ее бьет только за 2 хода". Второй полу-ход это выбор конкретной клетки. Из них складывается один ход. Или второй полуход это "напасть на короля". Может быть только один ход, удовлетворяющий этим двум полуходам. Полуход это абстракция, о которых я и говорю, из которых складывается ход.

>>Программа не должна разгадывать цели человека, а должна делать лучший ход в текущей позиции.
А разве оценка, будет ли какой-то ход лучшим или худшим, не зависит от действий человека? Если мы хотим выбрать лучший ход, то должны знать ответные ходы человека.
Поверьте, невозможно написать нормально играющую шахматную программу не владея ни терминологией, ни элементарными математическими познаниями.
Я бы посоветовал, перед изучением специфических алгоритмов шахматного программирования почитать популярные книжки по теории игр и Дискретному анализу.
А так-же - хотя бы в общих чертах ознакомиться с минимаксом и альфа-бетой.

WinPooh:
Сложновато, пока не буду связываться.

NS:
Спасибо Популярные книжки я уже лет 15 почти не читаю, наверно не уследил за новостями в области минимакса, альфа-беты и Дискретного анализа.

Да нет, уследил, да не в ту сторону.
У тебя на сайте написано, что используется минимакс. А после

А разве оценка, будет ли какой-то ход лучшим или худшим, не зависит от действий человека? Если мы хотим выбрать лучший ход, то должны знать ответные ходы человека.

Становится понятно, что ты даже примерно не знаешь, что это такое...

пиши по теме

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

Не туда роете.
Сейчас основное увеличение силы игры программы достигается увеличением глубины перебора.
Для этого используют селективные методы отсечений.
На данный момент самыми известными и эффективными являются - "Метод пустого хода" и "Хистори прунинг" В итге по сравнению с увеличением времени при расчете на один полуход дальше с Минимаксом (40-50 раз), Чистой Алфа-Бетой (в 7 раз) достигается более крутая селективность (в 2 раза), в итоге программы начинают считать в миттельшпиле на 20+ полуходов....
А Генетические Алгоритмы... Их можно испольховать только для подстройки весов оценочной функции - Это не дает кардинального увеличения силы игры, и генетические алгоритмы подразумевают опыт, тесты. А это слишком долго.

Простейший вариант ГА-шахмат это популяция против популяции. Ограничиваем количество "особей" например до 200, каждую новую особь оцениваем играя ее против 200 особей противника. Это быстро. Особь, в простейшем случае, это последовательность ходов, например 20 штук. Тогда для проверки одного черного гена нужно всего лишь выполнить 4000 уже известных ходов. Один ход это <100 машинных инструкций. То есть проверка практически такая же как в других алгоритмах. Другая только стратегия выбора ходов.
Более сложный ГА работает с абстракциями и вызовами функций. Например можно сделать ген "сейчас сходить по альфа-бете". Если селекция выявит, что альфа-бета всегда лучше, то будет играть по "альфа-бета в оболочке ГА". Можно и другие классические методы добавить, система попробует любые их комбинации.

Альфа-бета это те же самые "опыт, тесты" что и в ГА. Только альфа-бета выполняет за раз один ход, а ГА тестирует целую ветвь дерева. Альфа-бета это дебютизация перебора, она соберет в дереве все бесполезные ветви, отсечет заведомо вредные, потом начинает сравнивать ветви, которые ведут к одинаковым позициям, но которые она считает разными, т.к. они находятся на разных ветвях. Хотя может быть я не знаю и продвинутая Альфа-бета умеет объединять ветви "e2e4 a2a3" и "a2a3 e2e4" в одну. На 20+ полуходах, может быть до 10!=1*2*3*4*5*6*7*8*9*10 одинаковых ветвей, которые классическая альфа-бета считает разными и тратит время на их сравнение между собой.

Генерацию программ я пробовал в www.aicommunity.org/members/no/research.rar, посмотрите, программистам будет забавно.

Так же как и классический ГА.

Альфа-бета это те же самые "опыт, тесты" что и в ГА. Только альфа-бета выполняет за раз один ход, а ГА тестирует целую ветвь дерева. Альфа-бета это дебютизация перебора, она соберет в дереве все бесполезные ветви, отсечет заведомо вредные, потом начинает сравнивать ветви, которые ведут к одинаковым позициям, но которые она считает разными, т.к. они находятся на разных ветвях. Хотя может быть я не знаю и продвинутая Альфа-бета умеет объединять ветви "e2e4 a2a3" и "a2a3 e2e4" в одну. На 20+ полуходах, может быть до 10!=1*2*3*4*5*6*7*8*9*10 одинаковых ветвей, которые классическая альфа-бета считает разными и тратит время на их сравнение между собой.

Я начинаю понимать, что вы не знаете и что такое генетические алгоритмы...
А насчет 10! Вы глубоко ошибаетесь... У нас не минимакс, а Альфа-бета и её вариации...
Не 10 факториал, а где-то четыре (не факторил, а просто четыре)...
А насчет того, что не используется Альфа-бета - имелись в виду NegaScout и MTD(f), и их разновидности (нулевое окно и т.д.)

WildCat:
>Если особь это последовательность ходов, то откуда она берется?

создается генетическим алгоритмом - мутациями, скрещиваниями, селекцией

>Это последовательность только наших ходов? Или наши ходы чередуются с ходами противника.

если по-простому, то только наших

>В любом случае не понимаю как можно "каждую новую особь оцениваем играя ее против 200 особей противника".
Как одна последовательность ходов может играть с другой последовательностью ходов? Может я просто не знаю игру в которую они умеют играть?

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

>"Другая только стратегия выбора ходов" - пока я ничего об этой стратегии не понял

Если интересно, почитайте как работает ГА. Как именно я буду делать пока в деталях сам не знаю, ничего сказать не могу.

>Если честно, то "альфа-бета" - это не алгоритм поиска. Это всего лишь метод позволяющий игнорировать ветки, которые никак не влияют на конечный результат.

Это ведь только предположение, что они не влияют. Мы ведь не проверям каждую ветвь до самого мата и оценка альфа-беты это только результаты работы альфа-беты, как эти цифры связаны с конечным результатом мы точно не знаем.

>Т.е. отказ от альфа-беты - это всего лишь желание рассматривать бесполезные ветки.

нет, будет применяться другой критерий выбора полезных-бесполезных

>Вообще, альфа-бета может быть прикручена практически к любому алгоритму поиска.

Да, очень часто, но не всегда. Не все поиски обходят дерево.


NS:
Вы слишком строго судите, извините, мне такие грубые мнения не интересны. Что лично вам ГА не нужен я понял.

Извините за грубость, у меня такая нехорошая манера разговаривать.))

Насчет ГА... Я применял ГА, например, в Калах-е и Уголках для улучшения оценочной функции.

А так - Вы собрали в своей ветке трех! участников чемпионата СНГ среди шахматных программ!!!
И все хотят вам сказать одно и то-же. Почитайте литературу. Существует куча сайтов, форумов и статей на тему шахматного программирования.....
А вы уперлись - алгоритмов не знаю, и знать не хочу - хочу сразу ГА...)

WildCat:
>И во что же будут играть эти варианты?
эти два не совместимы, просто это сочетание не принимаем во внимание

Всем, еще раз. Читайте внимательно: "В результате выполнения алгоритма Альфа-бета мы получаем результат работы алгоритма Альфа-бета." — Где я тут ошибся?
А теперь посмотрим что нам нужно: "Выиграть". Почувствуйте разницу.
Она же что-то свое считает, мне даже не интересно что. Наверняка я эту альфа-бету когда-то изучал, сейчас даже терминов не помню. И вот я играл против такого простого алгоритма. (В шахматы я играл один раз лет 5 назад. А до этого играл в детстве, правила мы тогда использовали из игры кегельбан - нужно было щелбанами сбить фигурки противника

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