Как эффективно вычислять экспозицию пятен в нардах

Question

Я пытаюсь реализовать алгоритм для нард, аналогичный td-gammon, как описано here.

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

экспозиции блот определяется как here:

Для данного блота, количество рулонов из 36, которые позволили бы противник ударить блот. Общая вероятность блоттинга - это количество рулонов из 36, что позволило бы противнику ударить по любому пятну. Эффект пятен зависит от: (а) местоположения всех вражеских мужчин перед пятном; (b) количество и расположение точек блокировки между пятном и вражескими людьми и (c) количество вражеских мужчин на баре и броски, которые позволяют им повторно войти в доску, поскольку мужчины на баре должны повторно -центр, прежде чем пятна могут быть удалены.

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

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

Некоторые приблизительные цифры: при условии, что на ход ходят приблизительно 30 позиций на стойке, а средняя игра длится 50 оборотов, мы получаем, что для запуска 1 000 000 игровых симуляций требуется: (x * 30 * 50 * 1,000,000)/(1000 * 60 * 60 * 24) дней, где x - количество миллисекунд, чтобы вычислить эту функцию. Полагая x = 0,7, мы получаем приблизительно 12 дней для моделирования 1 000 000 игр.

Я действительно не знаю, разумно ли это, но я считаю, что должен быть значительно более быстрый подход.

Так вот что я пытался:

подхода 1 (по костям рулона)

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

private bool HitBlot(int[] dieValues, Checker.Color checkerColor, ref int depth) 
    { 
     Moves legalMovesOfDie = new Moves(); 

     if (depth < dieValues.Length) 
     { 
      legalMovesOfDie = LegalMovesOfDie(dieValues[depth], checkerColor); 
     } 

     if (depth == dieValues.Length || legalMovesOfDie.Count == 0) 
     { 
      return false; 
     } 

     bool hitBlot = false; 

     foreach (Move m in legalMovesOfDie.List) 
     { 
      if (m.HitChecker == true) 
      { 
       return true; 
      } 

      board.ApplyMove(m); 
      depth++; 
      hitBlot = HitBlot(dieValues, checkerColor, ref depth); 
      board.UnapplyMove(m); 
      depth--; 

      if (hitBlot == true) 
      { 
       break; 
      } 
     } 

     return hitBlot; 
    } 

Что эта функция делает это принять в качестве входных данных массива значений в костях (т.е., если игрок выбрасывает 1,1 массив будет [1,1,1,1] . затем эта функция рекурсивно проверяет, есть ли удар, и если да, выходит с правдой. функция LegalMovesOfDie вычисляет правовые шаги для этого конкретного значения матрицы.

подход 2 (по-блоттинга)

при таком подходе Сначала я нахожу все пометки, а затем для каждого пятна I, за исключением каждого возможного значения кости, и вижу, произошло ли поражение. Функция оптимизирована так, что как только кубик va lue регистрирует хит Я не использую его снова для следующего блота. Он также оптимизирован только для рассмотрения движений, которые перед блотом. Мой код:

public int BlotExposure2(Checker.Color checkerColor) 
    { 
     if (DegreeOfContact() == 0 || CountBlots(checkerColor) == 0) 
     { 
      return 0; 
     } 

     List<Dice> unusedDice = Dice.GetAllDice(); 

     List<int> blotPositions = BlotPositions(checkerColor); 

     int count = 0; 

     for(int i =0;i<blotPositions.Count;i++) 
     { 
      int blotPosition = blotPositions[i]; 

      for (int j =unusedDice.Count-1; j>= 0;j--) 
      { 
       Dice dice = unusedDice[j]; 

       Transitions transitions = new Transitions(this, dice); 

       bool hitBlot = transitions.HitBlot2(checkerColor, blotPosition); 

       if(hitBlot==true) 
       { 
        unusedDice.Remove(dice); 

        if (dice.ValuesEqual()) 
        { 
         count = count + 1; 
        } 
        else 
        { 
         count = count + 2; 
        } 
       } 
      } 
     } 


     return count; 
    } 

Метод transitions.HitBlot2 принимает параметр blotPosition, который гарантирует, что только движется считаются те, которые находятся в передней части пятно.

Оба этих реализаций были очень медленными, и когда я использовал профайлер я обнаружил, что рекурсия была причина, поэтому я попытался рефакторинга их следующим образом:

1. Чтобы использовать для петель вместо рекурсии (некрасиво код, но он намного быстрее)
2. Использовать parallel.foreach, чтобы вместо проверки значения 1 кости за один раз я проверял их параллельно.

Ниже приведены средние результаты синхронизации моих трасс для 50000 вычислений функции (обратите внимание на моменты времени для каждого подхода было сделано из тех же самых данных):

1. Подход 1 с помощью рекурсии: 2,28 мс на вычисление
2. подход 2 с помощью рекурсии: 1.1 мс на вычисление
3. подход 1, используя для циклов: 1,02 мс на вычисление
4. подход 2, используя для петель: 0,57 мс на вычисление
5. подход 1 с использованием Parallel.ForEach: 0,75 мс на вычисление 6 Подход 2 с использованием Parallel.ForEach: 0,75 мс на вычисление

Я нашел тайминги весьма изменчивы (Может зависеть от случайной инициализации вес нейронной сети), но около 0,7 мс кажется достижимым, что, если вы помните, приводит к 12 дням обучения для 1 000 000 игр.

Мои вопросы: Кто-нибудь знает, если это разумно? Есть ли более быстрый алгоритм, о котором я не знаю, что может сократить обучение?

Один последний фрагмент информации: Я бегу на довольно новой машине. Intel Cote (TM) i7-5500U CPU @ 2,40 ГГц.

Дополнительная информация, пожалуйста, дайте мне знать, и я предоставлю.

Спасибо, Офира

Answer 1

Да, вычисление этих функций делает действительно волосатый код. Посмотрите на код GNU Backgammon. найдите eval.c и посмотрите на строки от 1008 до 1267. Да, это 260 строк кода. Этот код подсчитывает количество рулонов, на которые попадает хотя бы одна контрольная сумма, а также количество рулонов, на которые попадает не менее 2 шашек. Как видите, код волосатый.

Если вы найдете лучший способ рассчитать это, отправьте свои результаты. Чтобы улучшить, я думаю, вам нужно взглянуть на представление совета. Можете ли вы представить плату по-другому, что делает этот расчет быстрее?