Оптимизация программы для анализа игры в слова

Question

Я являюсь частью сообщества Speedrunning для игры P C под названием Bookworm Adventures. Я написал несколько утилит, чтобы помочь людям изучить / попрактиковаться в игре. В данный момент я пытаюсь написать что-то, что может проанализировать игровое состояние, чтобы определить лучшую игру, аналогично утилитам, которые существуют для игроков в Эрудит.

Доска игры представляет собой квадрат плиток 4х4. Воспроизведение слова удаляет эти буквенные плитки с игрового поля и заменяет их произвольно сгенерированными буквенными плитками с максимум 4 одинаковыми плитками. «Цюй» существует вместе как одна плитка. (Я заменил все вхождения Qu на Q в списке слов, чтобы упростить это). Я не знаю официальных вероятностей каждой буквы, но я их приблизительно аппроксимировал.

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

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

Так что мой текущий поток выглядит примерно так:

struct word{
 string name;  // The word itself
 string leave; // The letters left behind ('?' for blank spaces)
};

vector<word> words;
// Dump all valid plays into words
int size = words.size();

for (int i=0; i<size; i++)
{
 word curWord = words[i];
 cout << curWord.name << ": " << leaveValue(curWord.leave);
}

С функцией, похожей на

float leaveValue(string leave)
{
 float sum = 0;
 /*
  Here I used multithreading to split the job among all available threads.
  It helps a little bit but my computer is pretty wimpy.
 */
 for (int i=0; i<MAX_SIMS; i++)
 {
  string simBoard = randomBoard(leave); // Fills in blanks w/ random letters based on letter probability
  sum += findBest(simBoard); // Traverses the dictionary tree to find the best scoring word
 }
 return sum / MAX_SIMS;
}

Однако если я запускаю это с MAX_SIMS = 1000, мои результаты меняются довольно широко. Похоже, мне нужно как минимум 100 тыс. Симов на слово (может быть, даже 1 млн.), Чтобы получить стабильное среднее значение.

Одна вещь, которую я подумал сделать, это собрать список случайных досок, сохраняя только уникальные доски но отслеживая, сколько раз они появляются. Таким образом, я не оцениваю стоимость одних и тех же плат несколько раз. Есть ли что-то еще очевидное, что мне не хватает, чтобы ускорить это?

РЕДАКТИРОВАТЬ: Что касается предложения о просмотре словаря и взятия средневзвешенного значения на основе% вероятности получения каждого слова: проблема в том, что я Заботьтесь о слове только в том случае, если это определенно игра с наибольшим количеством очков на этой доске. Таким образом, процент вероятности, который мне нужно рассчитать, - это не только вероятность появления этого слова в процентах, но и вероятность того, что это лучшее слово. Это хорошее начало, хотя.

Answer 1

Сначала отсканируйте весь словарь, чтобы найти слово с наибольшим значением, которое может быть сформировано из букв в leave.

let minVal = highest value word in dictionary that can be formed by 'leave'

Теперь мы снова просканируем словарь, но рассмотрим только слова, значение которых превышает minVal. Из этого мы определяем взвешенную вероятность всех таких слов.

let numBlanks = 16 - length(leave)
sum_pv = 0

for word in dictionary
    if value(word) > minVal
        let letters = remove from word all letters in leave
        assert(letters not empty) // else its value <= minVal
        let p = probability(letters, numBlanks)
        let v = value(word)
        sum_pv += p*v

Теперь мы определяем значение оставленных букв, которое может быть не меньше, чем minValue:

leaveValue = max(minValue, sum_pv)

Настоящий трюк здесь - это вычисление probability(letters, n), которое вычисляет вероятность того, что вы можете получить все оставшиеся буквы с пробелами n, основываясь на вероятностном распределении символов в игре. Это похоже на раздачу определенной «покерной руки» из length(letters) карт из колоды n карт (повторы разрешены).

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