Войти
ПрограммированиеСтатьиИгровая логика и ИИ

Элементы игрового ИИ на основе табличной логики и марковских цепей. (2 стр)

Автор:

Марковские цепи дискретного времени

Более продвинутой схемой табличной логики являются Марковские цепи. При достаточно детальной проработке данный метод позволяет компьютерным оппонентам строить прогнозы развития событий для любых игровых ситуаций, выдвигать собственные оценки и гипотезы насчёт дальнейшего их развития. Этот метод также хорош тем, что в сходных ситуациях AI всегда будет принимать сколько-нибудь различающиеся решения, что делает поведение управляемых им персонажей более живым и непредсказуемым.

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

Кратко о вероятностях

Согласно теории вероятностей, вероятность наступления какого-либо события – это отношение количества наблюдений, когда ожидаемое событие наступило, к общему количеству наблюдений, когда событие ожидалось. Классический пример – игра в кости. В идеальном случае и при большом числе попыток цифра 5 на кубике будет выпадать, в среднем, один раз на 6 бросков. Записать это можно так:


- ожидаемое событие (здесь – выпадение цифры 5);

- численная мера возможности наступления того или иного события.

Величина P, называемая вероятностью, может, при этом, принимать значения от 0 - событие невозможно, до 1 – событие точно совершается.

Рассмотрим более сложный случай – жеребьёвка. Пусть в шапке лежит шесть бумажек, одна из них помечена крестиком. Шестеро игроков вслепую по очереди вытягивают из шапки по одной бумажке и оставляют вытянутую бумажку у себя. Какова же вероятность того, что идущий третьим игрок не вытянет бумажку с крестиком?

Обозначим возможные исходы:

- бумажку вытянул первый игрок;

- бумажку вытянул второй игрок;

………………………………………………………………

- бумажку вытянул шестой игрок.

Рассмотрим все варианты развития событий:

• Меченую бумажку вытягивает первый игрок. Вероятность этого . В этом случае игрок номер три никак уже не вытянет бумажку с крестиком, следовательно, тут вероятность попадания бумажки к нему будет нулевой.

• Меченую бумажку вытягивает второй игрок. Это значит, что данная бумажка не досталась первому игроку; вероятность этого .
В шапке при этом останется 5 бумажек.
Если всё сложилось именно так, то вероятность вытянуть меченую бумажку для второго игрока равна . Казалось бы, это больше, чем полученное выше значение , однако, не следует забывать, что такова будет вероятность события только при том условии, что событиене реализовалось. Такая вероятность называется условной вероятностью события и записывается как ; читается как “вероятность наступления события при не наступлении события ”.

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

.

В этом случае вероятность того, что игрок три вытянет меченую бумажку, также будет равна нулю.

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

Вероятность события - третий игрок вытянет меченую бумажку – будет такова:

.

Отсюда можем найти искомую вероятность того, что третий игрок не вытянет бумажки с крестиком:

.

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

Таковы основы математического аппарата Марковских цепей.

Страницы: 1 2 3 Следующая »

#движок, #математика, #матрицы, #скрипты

6 августа 2012 (Обновление: 24 дек 2018)

Комментарии [26]