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

Код алгоритма проведения турнира. Алгоритмы неоптимизированы, так как основное время уходит на сами партии.

var rez:array[1..100,1..1000] of Double;
Первое измерение - номер итерации (текущая 1, предыдущая 2 и т.д.)

Особи нумеруются с единицы.

kolOst - количество оставляемых особей.
kolO - Всего особей.

Это мат. модель, поэтому в массиве Rating - хранится реальная сила особи.

Code:

// очистим Таблицу результатов.
-100000 означает что данная особь на данной итерации не существовала.
for i:=1 to 100 do
  for j:=1 to kolO do
  Begin
  rez[i,j]:=-100000;
  end;

// цикл итераций, для модели сделано ограничение на количество партий.
  kolPart:=0;
  while kolPart<10000000 do
    Begin
      NewRating; // Генерация новых особей.
     
     // сдвиг результатов 
     for j:=1 to kolO do
      Begin
        for i:=100 downto 2 do rez[i,j]:=rez[i-1,j];
        rez[1,j]:=0;
      end;
     
      // Обнуление результатов предыдущих туров для новых особей
      for j:=KolOst+1 to kolO do
      for i:=2 to  100 do
        rez[i,j]:=-100000;

      // проведем турнир
      // сначала "крутки"

      for k:=1 to kolOst-1 do
        for l:=k+1 to kolOst do
          Begin
          kolPart:=kolpart+1;
          if rezPart(Rating[k]-Rating[l])=1 then
            Begin
              rez[1,k]:=rez[1,k]+1;
              rez[1,l]:=rez[1,l]-1;
            end else
            Begin
              rez[1,k]:=rez[1,k]-1;
              rez[1,l]:=rez[1,l]+1;
            end;
            end;

       // "теперь новички"
        for k:=1 to kolOst do
        for l:=kolOst+1 to kolO do
          Begin
          kolPart:=kolpart+1;
          if rezPart(Rating[k]-Rating[l])=1 then
            Begin
              rez[1,l]:=rez[1,l]-1;
            end else
            Begin
              rez[1,l]:=rez[1,l]+1;
            end;
          end;

        // отсортируем рейтинги и участников
      maxrez:=0;
      for k:=1 to kolO  do
      Begin
      rez[1,k]:=rez[1,k]+Random()/100;
      if rez[1,k]>maxrez then maxrez:=rez[1,k];
      end;
      
     //Коэффициент 0.8 позволяет улучшить сходимость метода,
      for k:=kolOst+1 to kolO do rez[1,k]:=rez[1,k]-maxrez*0.8;

      for m:=1 to 100 do
      for k:=1 to kolO-1 do
        for l:=k+1 to kolO do
         if rez[m,k]>-99999 then
         if rez[m,l]>-99999 then
         Begin
           sum1:=0;
           for i:=1 to m do sum1:=sum1+rez[i,k];
           sum2:=0;
           for i:=1 to m do sum2:=sum2+rez[i,l];
           if sum1<sum2 then
           Begin
             for i:=1 to 100  do
              Begin
                tmpRez:=Rez[i,k];
                Rez[i,k]:=rez[i,l];
                Rez[i,l]:=tmpRez;
              End;
             tmpRat:=Rating[k];
             Rating[k]:=Rating[l];
             Rating[l]:=tmpRat;
           end;
         end;
      end;

Турнир проводится в один круг, так как для сходимости и так нужно мало партий, а увеличив количество кругов придется так-же уменьшить количество особей, что плохо.

Количество оставляемых особей должно быть значительно больше количества порождаемых. Могу привести найденные значения Экстремума, если сила новых особей подчиняется закону:

Code:

for i:=kolOst+1 to kolO do
  Begin
  Nom:=Random(kolOst)+1;
  if Random()>0.95 Then Rating[i]:=Rating[Nom]+Random(11)
                   Else Rating[i]:=Rating[Nom]-Random(51);
  end;

При меньшем проценте порождения хороших особей (<5%) У меня не получается поднять скорость роста силы выше Одного пункта за 10000 партий. Поэтому наверно не стоит настраивать алгоритмы на такой процент.

Вот средняя прибавка в расчете на 10000 партий (последний столбец) в зависимости от Общего количества особей и оставляемых при коэффициенте "защиты от слабачков" равном 0.8

Code:

kolO    28  KolOst    20  0.81
kolO    28  KolOst    22  1.00
kolO    28  KolOst    24  1.04
kolO    28  KolOst    26  0.81
kolO    32  KolOst    22  1.00
kolO    32  KolOst    24  1.15
kolO    32  KolOst    26  1.21
kolO    32  KolOst    28  0.94
kolO    32  KolOst    30  0.64
kolO    36  KolOst    24  0.96
kolO    36  KolOst    26  1.04
kolO    36  KolOst    28  0.97
kolO    36  KolOst    30  0.92
kolO    36  KolOst    32  0.78
kolO    36  KolOst    34  0.47
kolO    40  KolOst    26  0.99
kolO    40  KolOst    28  1.19
kolO    40  KolOst    30  1.01
kolO    40  KolOst    32  0.98
kolO    40  KolOst    34  0.88
kolO    40  KolOst    36  0.60

Игорь, а тяжело будет вывести настройки WildCat (чтоб их в ручную можно было менять) в зависимости от типа центра, как Сергей советует? Лучше вместе с позиционными, но можно и просто с весами фигур.

Это должно много давать. Шахматы - искусство разменов. А если таблично задать веса фигур в зависимости от стадии партии и центра - программа будет значительно лучше эти размены понимать. Лучше чем Фрукт

А то сейчас играю - не понимают они что нужно менять, а что оставить.
Из-за этого хромает и техника реализации, и умение правильно упростить в плохой позиции.

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

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

Из мат. модели - Если целевая функция это расстояние до экстремума (и нужно её минимизировать) - то метод усереднения всегда дает особь лучше одной из тех которые порождали. (Медиана треугольника всегда имеет длину меньшую длины одной из двух сторон)

И тест - согласно тестовому стенду - 5%-10% порождений методом усереднения улучшает сходимость в несколько раз. При большем проценте происходит вырождение.

Как это? Экстремум в точке 0,0
Два родителя - один в точке 5,1 Второй в точке -5,1
Расстояние от обоих больше 5, растояние от усередненной точки 1.
Медиана всегда короче одной из сторон, но далеко не всегда длинее одной из сторон. Далеко не всегда.

Но в любом случае - у меня написан Тест. Проверял на 28-мерной Сфере. Могу либо выслать программу, либо выложить результат на форум. Только вечером.

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

Если бы это было так, то сходимость на мат. модели (Целевая Функция - расстояние до конкретной точки на 28-мерной сфере) не улучшалась бы почти в 10 раз от добавления 5%-10% порождений усереднением.

Напряженный - неясно к какому типу перейдём
Открытый - нет пешек в центре
Фиксированный пешки е4(белая) е5(чёрная), на линии d нет пешек. И наоборот (d4-d5, на линии е5 нет пешек
Закрытый или запертый. Тут сложнее. Запертым считается просто наличия пешечной цепи в центре ("центр разорвать нельзя" © Котов).... с4-d3-e4 против c5-d6-е5( ну, и d4-e3-f4 против d5-e6-f5) считается закрытым цетром. Вдобавок к этому, NS предлагает разделять закрытый центр d4-e5 против d5-e6 и d5-e4 против d6-e5 (аналигично для другого цвета), так как, разные слоны будут считаться "сильными".
С изолированной пешкой - тут думаю понятно. Одна пешка в центре, нет пешек на соседних вертикалях, акромя вражеских.
Подвижный или пешечный - у одной из сторон пешечная пара в центре при том, что у другой нет пешек в центре. Кстати, WildCat плохо играет такие позиции. Он не блокирует и не разрушает такой центр, позволяя противнику продвигать их на d5 и е5 одновременно.

Вроде ничего не забыл, но можно кто-нить ещё что-нить добавит или улучшит.

На счёт весов...Я думал, что в других программах настройки такие же, как и у Pro Deo. Просто авторы их не вытаскивают для простых пользователей. Получается, у WildCat не так? Вот напр кусок из Pro Deo:

[Pawn Value = 100] * Tune value Pawn
[Knight Value = 100] * Tune value Knight
[Bishop Value = 100] * Tune value Bishop
[Rook Value = 100] * Tune value Rook
[Queen Value = 100] * Tune value Queen
[My Queen = 101] * Tune value Own Queen
*
[King Safety = 150] * Tune King Safety.
*
[Mobility = 100] * Overall tuning Mobility
[Minimum Knight Mobility = 100] * Penalty for bad developed knights
[Minimum Bishop Mobility = 100] * Penalty for bad developed bishops
[Knight Mobility = 100] * Tune Knight Mobility
[Bishop Mobility = 25] * Tune Bishop Mobility
*
[Pawn Structure = 100] * Overall tuning pawn structure
[Pawn Formation = 100] * Part (1) of [Pawn Structure] parameter
[Weak Pawns = 100] * Part (2) of [Pawn Structure] parameter
[Pawn Pressure = 100] * Tune Pressure on opponent weak pawns
[Double Pawns = 100] * Tune Penalty for double pawns
[Double Isolated Pawns = 100] * Tune Penalty for isolated double pawns
[Passed Pawns = 100] * Tune Passed Pawns
[Passed Pawn Tropism (1) = 100] * Tune King tropism to OWN passed pawns
[Passed Pawn Tropism (2) = 100] * Tune King tropism to OPPONENT passed pawns
*
[Bad Bishop = 100] * Tune Bishops caught in pawn chains
[Bishop Pair = 100] * Tune Bishop Pair evaluation
[Pins = 100] * Tune pins evaluation
[Center Control = 25] * Tune Center Control evaluation
[Right to Move = 75] * Tune bonus for Right to Move
[Strong Squares = 125] * Tune Knight Outpost evaluation
[Rook 7th Rank (1) = 50] * When opponent king is on the 8th rank

Тут даже больше, чем нужно

Остальные настройки нужны в рекламных целях!

Хм.... я не понял вопроса, очевидно....Думал, без типов центра всё, более или менее, хорошо настроено.

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

Ты уже это проходил? Или это только твое предположение?

Обработать 1000 партий тяжело! Так, можно и самому мастером стать. Но есть вариант, который может помочь. Достаточно исправлять не все ошибки, а часто повторяющиеся, типовые. Даже 100 партий (с длинным контролем) хватит, чтобы найти таковые в достаточном размере.

Проверил сходимость на пяти параметрах. Каждый в интервале [0,+бесконечность)
Настроил на случайных искомых точках.
Потом проверка поиска значений 1,4,4,6,12
50 итераций, на каждой 15 новых особей - 750 новых особей:
Полученные значения (50 разных запусков теста)
Значения приведены к стоимость пешки=1.00

Так что при грамотном подходе материал сходится достаточно легко.

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

Попробуй на настоящей программе (на Анечке) настроить. А то, у нас тоже всё сходилось, пока 0.pst, зараза, не стала побеждать на всех компьютерах.
Если серьёзно, то, пожалуй, ты прав: параметров нужно было меньше ставить!

Зачем мне проверять на Анечке, если я проверяю на шашках

+1

Отчего же? Шашки мне нравятся, но шахматы мне нравятся больше!

Он наверно в них играть не умеет
Я вот поиграл со Skifi и Kallisto, и научился.
Не знаю в какую силу, но у Скифи могу и выиграть сам, а Каллисто далеко не всегда у меня выигрывает...

Умею. Однажды обыграл друга со счётом 20:0. Вот такой я умелец. NS, ты прислал мне версию, которая сама с собой играет, притом, что нет никакой графики и доски не видно. Как там учится?

Эта... Ведь ветка давно есть, я сразу после того как выслал тебе сделал версию под протокол Каллисто.
Причем она не просто играет, а играет в Мастерскую силу.

http://kasparovchess.crestbook.com/viewtopic.php?id=1296
http://www.igorkorshunov.narod.ru/Draughts/

ЧессСлово, делаю ничьи иногда и белыми и черными (из начальной позиции)

Жаль. Я после такого успеха не играл лет 8.

А можно с помошью, Каллисто напр, шашечной программы узнать свой примерный уровень? Рейтинги есть? Как узнать свой?