04:53 18-04-2005 Программистское -- проект
Написать АИшник для шахмат. Из двух кусков:
1) Если текущая позиция ранее встречалась -- делаем ход в соответствии с теми партиями, где встречалась.
2) Если текущей позиции не встречалось -- перебираем все варианты на, пусть, 5 ходов вперед, юзаем примерную оценочную функцию.
Update 1: поскольку мы в шахматы играть не умеем, оценочную функцию пусть нам пишет комп (хотя параметры оценки придется выбирать самим):
Берем базу партий. Разбиваем каждую партию на доски (новый ход = новая доска). Для каждой доски собираем инфу обо всех параметрах, по которым оцениваем. Пишем уравнение:
Первый параметр (например, 3 черные фигуры под атакой)*его цена + второй параметр*его цена +... = max(70 - число ходов до конца, 0) * (-1)^(черные победили)
И так для каждой доски.
Получаем систему из ~100000 уравнений с ~100 неизвестными. Загоняем ее в метод наименьших квадратов. Получаем цену для каждого параметра.
1) Если текущая позиция ранее встречалась -- делаем ход в соответствии с теми партиями, где встречалась.
2) Если текущей позиции не встречалось -- перебираем все варианты на, пусть, 5 ходов вперед, юзаем примерную оценочную функцию.
Update 1: поскольку мы в шахматы играть не умеем, оценочную функцию пусть нам пишет комп (хотя параметры оценки придется выбирать самим):
Берем базу партий. Разбиваем каждую партию на доски (новый ход = новая доска). Для каждой доски собираем инфу обо всех параметрах, по которым оцениваем. Пишем уравнение:
Первый параметр (например, 3 черные фигуры под атакой)*его цена + второй параметр*его цена +... = max(70 - число ходов до конца, 0) * (-1)^(черные победили)
И так для каждой доски.
Получаем систему из ~100000 уравнений с ~100 неизвестными. Загоняем ее в метод наименьших квадратов. Получаем цену для каждого параметра.
Комментарии:
Anafay
08:35 18-04-2005
Попробуй формализовать, и сразу увидишь проблему в (1) - а что такое "ранее встречалось"? Если под этим имеется в виду полное повторение позиции, то можно сразу (1) выбросить, ибо вариантов слишком много. Если нет - то по какому принципу определять схожесть позиций. Итого - дополнительная функция номер раз.
Далее, надо использовать не "где встречалось", а "где встречалось и пошло на пользу". Это предполагает либо обучение, долгое обучение, с указанием полезности хода вручную, либо еще одну нетривиальную функцию - оценки полезности хода
По отношению 5 ходов вперед тоже есть сомнения: так как весовая функция будет, предположительно, минмаксной, то это обозначает полный перебор без применения, например, метода ветвей и границ.
Далее, надо использовать не "где встречалось", а "где встречалось и пошло на пользу". Это предполагает либо обучение, долгое обучение, с указанием полезности хода вручную, либо еще одну нетривиальную функцию - оценки полезности хода
По отношению 5 ходов вперед тоже есть сомнения: так как весовая функция будет, предположительно, минмаксной, то это обозначает полный перебор без применения, например, метода ветвей и границ.
08:43 18-04-2005
Anafay
Полное повторение. Позиций, конечно, много, но большинство повторяются
Можно "где пошло на пользу" простенько: выиграл -- пошло на пользу
Оценка только текущей позиции, ибо не гении 5 ходов с полным перебором, поскольку я пока лучше ничего не придумал
См.апдейт
Полное повторение. Позиций, конечно, много, но большинство повторяются
Можно "где пошло на пользу" простенько: выиграл -- пошло на пользу
Оценка только текущей позиции, ибо не гении
5 ходов с полным перебором, поскольку я пока лучше ничего не придумал См.апдейт
08:59 18-04-2005
Дарю ещё идею. Программа выполняет перебор позиций в ширину (breadth-first) в отдельном потоке. В том числе пока юзер думает. В первую очередь рассматривается поддерево для того первого хода юзера, который сейчас наиболее вероятен (скажем, юзер занёс мышь над определённой фигурой).
Если юзер сделал предусмотренный ход, то у нас уже построено дерево перебора до некоторой глубины. Откидываем всё лишнее (если у нас нет функции Undo) и продолжаем поиск/оценку.
Если юзер сделал предусмотренный ход, то у нас уже построено дерево перебора до некоторой глубины. Откидываем всё лишнее (если у нас нет функции Undo) и продолжаем поиск/оценку.
Anafay
11:22 18-04-2005
Xirax
Полное повторение
Тогда хранимая информация абсолютно бесполезна. Сам посчитай количество вариантов расстановки фигур. На половинной доске - без проблем. На полной - проблемы...
Можно "где пошло на пользу" простенько: выиграл -- пошло на пользу
Расточительно. Это условие достаточное, но оно слишком сильное: сотня полезных ходов может быть испорчена одним плохим ходом.
См.апдейт
IMHO вариация нейронной сети (типа натуральный АИ) с хорошим алгоритмом распознавания ситуации были бы идеальным вариантом. И обучение, обучение, обучение... А указанный вариант с определением весовой функции, по моему, бесперспективен.
Полное повторение
Тогда хранимая информация абсолютно бесполезна. Сам посчитай количество вариантов расстановки фигур. На половинной доске - без проблем. На полной - проблемы...
Можно "где пошло на пользу" простенько: выиграл -- пошло на пользу
Расточительно. Это условие достаточное, но оно слишком сильное: сотня полезных ходов может быть испорчена одним плохим ходом.
См.апдейт
IMHO вариация нейронной сети (типа натуральный АИ) с хорошим алгоритмом распознавания ситуации были бы идеальным вариантом. И обучение, обучение, обучение... А указанный вариант с определением весовой функции, по моему, бесперспективен.
05:36 19-04-2005
Centaur
в отдельном потоке.
Учиться, учиться и еще раз учиться! (multithreading пока не умею)
Вначале бы это работать заставить, а потом бум оптимизировать, если выживем
Anafay
Сам посчитай количество вариантов расстановки фигур.
Множество позиций повторяется. Т.е. дебюты например -- сплошные повторения. Можно исследование по этому поводу провести вначале -- прогнать базу партий через счетчик и посмотреть сколько уникальных досок.
Расточительно. Это условие достаточное, но оно слишком сильное: сотня полезных ходов может быть испорчена одним плохим ходом.
Не совсем понял... Ну можно по косвенным параметрам, например по рейтингу игрока, делающего этот ход (в стандартном формате баз партий они записаны).
вариация нейронной сети
обучение, обучение, обучение...меня
Это что за зверь?
в отдельном потоке.
Учиться, учиться и еще раз учиться! (multithreading пока не умею)
Вначале бы это работать заставить, а потом бум оптимизировать, если выживем
Anafay
Сам посчитай количество вариантов расстановки фигур.
Множество позиций повторяется. Т.е. дебюты например -- сплошные повторения. Можно исследование по этому поводу провести вначале -- прогнать базу партий через счетчик и посмотреть сколько уникальных досок.
Расточительно. Это условие достаточное, но оно слишком сильное: сотня полезных ходов может быть испорчена одним плохим ходом.
Не совсем понял... Ну можно по косвенным параметрам, например по рейтингу игрока, делающего этот ход (в стандартном формате баз партий они записаны).
вариация нейронной сети
обучение, обучение, обучение...меня
Это что за зверь?
09:40 19-04-2005
офтоп.
заказывай А85+128М. А510 отменяй.
Его успеют доставить. В последнее время мои желания имеют склонность исполнятся. Не знаю почему. Наверное, я Вершитель.
заказывай А85+128М. А510 отменяй.
Его успеют доставить. В последнее время мои желания имеют склонность исполнятся. Не знаю почему. Наверное, я Вершитель.
10:55 19-04-2005
vakito
Типа заказал... с 17ой попытки
Чувствую, бегать мне по Нью-Йорку
Типа заказал... с 17ой попытки
Чувствую, бегать мне по Нью-Йорку Anafay
11:43 19-04-2005
Xirax
Множество позиций повторяется. Т.е. дебюты например -- сплошные повторения.
В том-то и дело, что окромя дебютов повторов крайне мало. Следствие - достаточно делать один нестандартный ход, чтобы шахматбот стал играть существенно хуже. Грубо говоря, не будет применения решения по аналогии, то есть распространения решения не только на ситуацию, находящуюся в базе знаний, но и на похожие на нее.
Ну можно по косвенным параметрам, например по рейтингу игрока, делающего этот ход
Это можно. Но тут не будет обучения на ходу.
Это что за зверь?
Начинай с библии ИИ: Марвин Мински, "Фреймы в теории представления знаний".
Множество позиций повторяется. Т.е. дебюты например -- сплошные повторения.
В том-то и дело, что окромя дебютов повторов крайне мало. Следствие - достаточно делать один нестандартный ход, чтобы шахматбот стал играть существенно хуже. Грубо говоря, не будет применения решения по аналогии, то есть распространения решения не только на ситуацию, находящуюся в базе знаний, но и на похожие на нее.
Ну можно по косвенным параметрам, например по рейтингу игрока, делающего этот ход
Это можно. Но тут не будет обучения на ходу.
Это что за зверь?
Начинай с библии ИИ: Марвин Мински, "Фреймы в теории представления знаний".