Построение эвристических оценочных функций.
Выделение параметров.
Реализованная программа игры за компьютер состоит из двух частей. Первая часть генерирует все возможные ходы (при текущем броске костей) доступные из текущей позиции. Вторая часть – оценочная функция, с помощью которой выбирается наилучший ход. Учитывая то, что у нард очень большой коэффициент ветвления дерева игровых позиций (достигает 200-300 доступных ходов из одной позиции) и наличие случайности (броски костей) перебор в глубину не представляется целесообразным, вследствие ограниченности вычислительных ресурсов. Для примера, в шахматах коэффициент ветвления составляет порядка 40 ходов, а для шашек 8-15. Таким образом, применение «грубой силы» (“brute force”) для нард неэффективно.
В качестве оценочной функции используются линейные модели (линейная комбинация некоторых параметров) и нейронные сети (трехслойная нейронная сеть).
В простейшей модели в качестве параметров можно взять просто количество фишек на каждом поле, получив в сумме 26 параметров. Реально же используют некоторые вычисляемые параметры, представляющие определенные стратегические аспекты игры.
Одним из основных параметров является подсчет пипсов (pips) – это число, которое нужно выбросить на игральных костях, чтобы вывести все свои фишки. По этому параметру определяют лидерство и близость победы.
Число одинарных фишек (blots) также является важным параметром, который стремятся сокращать все игроки, так как только одинарные фишки можно побить в нардах, тем самым откинув противника в гонке за вывод фишек из доски.
|
|
|
Число полей с двумя и более фишками (hold) является противоположностью предыдущему параметру, его стремятся максимизировать. Чем больше таких полей, тем устойчивее позиция и тем сложнее через нее пройти.
Связанным параметром является построение блокад – несколько смежных полей, занятых двойными или более фишками. С этим параметром можно связать изменение стратегии – нужно проводить свои фишки вперед, если их запирают.
Также считают число прямых возможностей взятия (direct shot) – это число одинарных фишек на расстоянии 6 или меньше полей. Есть схожий с этим параметр indirect shots – число одинарных фишек на расстоянии меньшем 12. Схожим параметром является вероятность взятия одинарной фишки, которая в большинстве случаев рассчитывается по предварительно посчитанной таблице.
Равномерность распределения фишек по полям. Например, гораздо выгоднее иметь три фишки на одном поле и еще три на другом, чем две и четыре на тех же полях. В случае выпадения определенных костей может потребоваться сдвинуть фишку с первого поля и тем самым сделать как минимум одну одинарную фишку.
|
|
|
Анализируя сыгранные партии можно заметить, что занятие определенных позиций (golden point) на доске способствует победе. Такими позициями является 4-я и 5-я клетки и соответственно 20-я и 21-я симметричные клетки. Таким образом, в простейшем случае можно ввести факт занятия этих клеток в оценочную функцию. В более общем случае, вводят весовые коэффициенты для всех полей доски.
Также часто используется параметр коммуникации – нужно стремиться располагать свои фишки на расстоянии не более 6 пипсов друг от друга. Тем самым препятствовать разделению своих фишек.
При выводе своих фишек, нужно стремиться оставлять четное число фишек на каждом поле, чтобы минимизировать шансы оставления одиночной фишки после очередного хода.
Очень часто вводятся понятия контакта фишек – наличие хотя одной вражеской фишки в направлении движения. Наличие факта контакта влияет на используемую стратегию и может предполагать разные оценочные функции.
В целом можно отметить, что с ростом числа параметров в модели росло и время обучения, но также росло и качество оценки позиции.
Определение более сильного игрока из двух.
|
|
|
В силу того, что и в игре присутствует элемент везения возможна ситуация, когда слабый соперник может выиграть у более сильного, что ставит вопрос об определении более сильного игрока из двух. В случае, когда один соперник заведомо сильнее другого эффект везения практически не проявляется и выбрать сильнейшего можно сыграв незначительное число партий. К тому же данная ситуация случается не так часто. Когда же силы игроков примерно равны (такое часто случается при подборе весов оценочной функции) выбирать сложнее. Соответственно требуется оценить число партий, которые необходимо сыграть, чтобы достоверно определить победителя. Можно доказать, что число побед одного игрока над другим распределено по нормальному закону. В этом случае для получения доверительного интервала для оценки математического ожидания вероятности победы первого игрока можно воспользоваться следующим выражением: 
, где 
-выборочное среднее, 
- “исправленное” среднее квадратическое отклонение, 
- коэффициент Стьюдента с надежностью 
, 
- объем выборки. Так как силы игроков примерно равны, можно считать, что вероятности выпадения 1 (победа белых) или 0 (победа черных) равны. Тогда задавшись 
, получим доверительный интервал для 
: 
. А для 
: 
. Основываясь на полученных данных, сравнивать силу двух игроков, примерно равных по силе, корректно только при числе сыгранных партий близком к тысяче и более.
|
|
|
Дата добавления: 2018-05-02; просмотров: 316; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!