Автоматический подбор параметров движка

Не узнаешь, Каллисто играет слишком сильно чтоб был шанс набрать какое-то количество очков. У Каллисто есть человеческий рейтинг, правда это рейтинг не последней версии.
Попробуй поиграть со Skifi, если что-нибудь наберешь, то можно будет посчитать твою силу.

 

Ладно. Будет время, попробую....Сейчас переписка отнимает много.

 

В шашках вытянула первый ряд - теперь он самый дорогой (есно за исключением a1), и подняла шестой (поле f6 дороже с5) и всё это на старых плохих алгоритмах (я расчет не прерывал, согласно диспетчеру задач считает без перерыва уже 1200 часов, 50 дней) При оценке балансом шашек плохих поля три - b2,e5,h6.
Сходимость лучше, чем выходит на мат. модели.

 

Еще один метод улучшающий сходимость.
Путь ОФ разбита на несколько Таблиц. К каждой таблице применяем с одинаковой вероятностью один из двух метод. Либо прибавка фиксированной случайной величины, либо прибавка случайной величины пропорциональной значению в таблице.
(Все таблицы приведены к виду - сумма всех элементов в таблице равна нулю)
Коэффициенты прибавки не задаем жестко, а выбираем таким образом, чтоб процент новых порождаемых особей более сильных чем прародитель был равен некоторой заданной величине (например 5%)

 

только не 5%, а 25%.
(тестировал на модели - всего 300 особей, оставляем 200 лучших, 100 порождаем от случайных из этих двухсот) На всех тестах лучшая сходимость при подстройке изменений таким образом чтоб процент лучших был 25%.

Тестировал на 6, 28 и 100 параметрах в таблице, на 100 и 1000 итераций.
После каждой итерации вот такой код.
if ch<k then Dob:=Dob/1.2 Else Dob:=Dob*1.2;
Лучший вариант k=25.
Изменяем вот таким образом:

Код:

      ist:=Random(200)+1;
      for j:=1 to Razm do Gen[i].V[j]:=Gen[ist].V[j]+Random*Dob;
      Norm(Gen[i].V); // приводит вектор к виду - сумма элеметов равна нулю,
                             // сумма квадратов элементов равна единице.
      Gen[i].Rod:=ist;

 

Похоже никому не интересно
Буду сам с собой.
Нашел статью где авторы утверждают что смогли заставить программу искать экстремум функции Розенброка от 2000 параметров (Гибридными методами) - основное это часть порождений градиентным спуском от сильнейшей особи.
Мне пока удалось добиться поиска большого числа локальных экстремумов и очень быстрой (по сравнению со старыми алгоритмами) сходимости - пока метод случайных направлением с повторными попытками в направлении наискорейшего спуска и с сложными алгоритмами смерти особей (наиболее отдаленные неприкасаемые + смерть от перенаселения) Попробую добавить градиентный спуск от сильнейшей особи.

 

Блин пропустил - конечно же интересно! Если есть сцылка на эту статью - скинь. Оптимизация моя любимая тема в вышке еще с института.

 

http://paklin.newmail.ru/mater/hybrid.html
только для настройки Оф это не нужно. Не имеет смысла настолько близко подходить к экстремуму, а вдали от экстремума градиентные методы работают не так хорошо. Главное собирать все экстремумы, а это у меня получилось.
(прошлая версия программы собрала все особи в практически в одну точку - нашла один локальный экстремум, правда достаточно хороший )
Новая умеет собирать очень большое количество локальных экстремумов + имеет на порядки лучшую сходимость: правильный расчет шага, плюс повторные шаги в направлении наискорейшего спуска, плюс больше порождений от сильнейшей версии, ну и все остальные алгоритмы улучшены - готов считать тысячи параметров (прошлая за пару месяцев хорошо посчитала чуть больше 80-ти).
Вдобавок почти в 3 раза ускорил (NPS) саму шашечную программу, сделал хорошие сортировки.
Так что готов сделать нечто весьма сильное.

вот, если интересно еще ссылка на метод главных осей (на хороших функциях без аналитической производной просто зверь)
http://alglib.sources.ru/optimization/principalaxis.php

 

Я не понимаю чего обсуждать - делать надо По силе моей программы становится понятно что всё получилось, и настроить ОФ автоматическими методами можно.
И я получил не 10-20 пунктов прибавки, а несколько сотен.

 

В ней нет ничего нового. Только он опять сводит всё к генетике, хотя кто сказал что генетика будет лучше?
Чтоб генетика работала - гены должны быть малосвязанными между собой, чтоб сочетание генов от разных особей могло работать... Мне кажется что классические спуски надежней, они гарантируют появление более сильных особей в направлении локального экстремума. А в случае генетики (брать гены от двух и более особей) - нет такой гарантии.

 

Как я делал - лучше не делать. Я получил сходимость намного меньшую чем можно было бы добиться.
Что лучше написать - как делал, или как лучше делать?

Насчет генетики, что я имею против - допустим у нас два праметра. Разместим особей на плоскости.
Проведем от каждой особи горизонтальные и вертикальные линии (параллельно оси координат).
Что такое предложенный алгоритм - это беганье по узлам нарисованной сетки.
Тяжело придумать вид функции силы движка от этих двух параметров при котором такой метод будет работать.

 

Как делал - 30 особей. Не помню уже сколько начальных позиций.
Каждая с каждой играют микроматчи по две партии (с переменой цвета) по четырем случайным позициям из списка. Потом особи сортируются по результату. 15 (хотя точно не помню сколько, может и не 15) слабейших отбрасываются.
Каждая новая особь формируется от случайной из оставшихся. Генерируется изменением на некоторую дельту каждого из параметров входящих в группу. Группа это случайный узел из дерева признаков...
Вероятности выпадения каждой группы я проставлял вручную, но можно сделать пропорционально количеству элементов в группе.
Дельта расчетная, для каждого из изменяемых признаков случайное число в интервале
-/+ Коэффициент/SQRT(КоличествоИзменяемыхПризнаков);

но лучше конечно делать по-другому...

 

Как думаете, какую можно получить прибавку в силе после автоматической настройки весов по сравнению с теми весами, которые вручную подобраны уже неплохо, как в сильнейших программах типа WildCat? Неужели несколько сотен пунктов?

 

И как было определено что они подобраны "неплохо"?

 

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

 

Тестировались многократно? Да хоть миллион раз протестируй набор весов - это не докажет что они оптимальные, и не покажет их близость к оптимальным.

 

5 и 6 — талантливо (чтоб не сказать — гениально )
На мой диллетантский взгляд, конечно.

 

Да, всё чётко и просто. Правда, очень знакомо по беседем в ICQ :

NS (22:03:10 11/07/2007)
3. После этого началась работа по совершенствованию оценочной функции и алгоритма поиска. Оптимизация оценочной функции выполнялась путем корреляционного анализа. Я добивался максимальной корреляции статической оценки и минимакса.

 

ИМХО Слишком просто, чтобы быть похожим на правду. Известны ли достоверные случаи (кроме Стрелки), когда данные методы приводили к реальному результату (повышению силы)?

 

Дискуссия на эту тему на talkchess как-то слишком быстро сошла на нет...
http://64.68.157.89/forum/viewtopic.php?t=16919

 

NS и его шашечная программа. В кратчайшие сроки, уже вторая по силе в мире. По видимому, Рыбка также использовала указанные методы....ИМХО описать можно просто, а реализовывать явно сложнее и значительно дольше по времени. Хорошее описание всегда должно быть простым и понятным. Что ещё можно от него тербовать?

 

NS использовал один из этих методов?

А еще? И желательно, чтобы не "по видимому", а какой-нибудь реальный пример

Кажется Марков что-то делал в этом направлении. Кто-нибудь знает подробности?

 

По рыбке мы точной правды долго не узнаем. Но заявления Сергея Маркова (общался с Райлихом и тот ему говорил о чём-то подобном), NS (о том, что Райлих так сделал и то, что у него получилось в шашках также) и Юрия Осипова (где он говорил о рыбке), позволяют не воспринимать всерьёз моё "по видимому".

Последный раз, когда я общался с С. Марковым (достаточно давно, до Стрелки), он говорил, что интуитивно настроил веса (те, которые уже были давно) в SmarThink очень хорошо и метод подбора весов по базе партий не дал существенных изменений в силе игры

 

Юрий Осипов:В результате имеем пары чисел: X - статическая оценка, Y - минимаксная оценка. Добиваемся максимальной корреляции между этими величинами. В результате получаем оценочную функцию, которая безо всякого перебора умеет с высокой степенью вероятности угадывать потенциальный минимакс

NS: После этого началась работа по совершенствованию оценочной функции и алгоритма поиска. Оптимизация оценочной функции выполнялась путем корреляционного анализа. Я добивался максимальной корреляции статической оценки и минимакса.

 

Шашечная программа Сергея уже первая в мире по последним данным

 

Реальный пример. Оф у меня была посчитана чисто автоматически, но не корреляционным анализом.
Может программа и не сильнейшая, но одна из сильнейших (среди доступных скорей всего делит первое-второе место с Каллисто)

 

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

 

А работающие алгоритмы, как я понимаю - большой секрет ?

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