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

Question

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

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

Блот-экспозиция определяется здесь как:

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

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

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

Некоторые приблизительные цифры: если предположить, что на борде примерно 30 позиций на доске, а средняя игра длится 50 ходов, мы получаем, что для запуска 1 000 000 игровых симуляций требуется: (х * 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]. Затем функция рекурсивно проверяет, есть ли попадание, и если поэтому завершается с true. Функция LegalMovesOfDie вычисляет допустимые ходы для этого конкретного значения кубика.

Подход 2 (по пятно)

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

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. Чтобы использовать параллелизм, чтобы вместо проверки значения 1 кости за раз я проверял их параллельно.

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

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

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

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

И последняя информация: я работаю на довольно новой машине. Процессор Intel Cote ™ i7-5500U с тактовой частотой 2,40 ГГц.

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

Спасибо Офир

Answer 1

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

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