ти програмний засіб для вирішення стохастичних ігор на прикладі гри В«Герб - РешіткаВ»
стохастичний гра програмний
1. Стохастичні ігри
Різновидом багатокрокових ігор є стохастичні ігри, в яких є декілька ігрових позицій, і перехід від однієї позиції до іншої відбувається з певною ймовірністю. У правилах гри передбачаються виграші на кожному кроці гри. Таким чином, в стохастичною грі можливі повернення до попередньої позиції і теоретично можливо нескінченне продовження гри і нескінченно великий виграш. Однак, щоб виключити таку можливість, у правилах гри передбачається завдання таких перехідних ймовірностей, що нескінченне продовження гри може бути з ймовірністю нуль, а математичне сподівання виграшу звичайно. p align="justify"> Гра розігрується протягом ряду етапів. На початку кожного етапу гра знаходиться в деякому стані. Гравці вибирають свої дії і отримують виграші, що залежать від поточного стану і дій. Після цього система переходить випадковим чином в інший стан, розподіл ймовірності переходів залежить від попереднього стану і дій гравців. p align="justify"> Ця процедура повторюється протягом кінцевого або нескінченного числа кроків. Загальний виграш гравців часто визначається як дисконтована сума виграшів на кожному етапі або нижня межа середніх виграшів за кінцеве число кроків. p align="justify"> При кінцевому числі гравців, кінцевих множинах дій і станів гра з кінцевим числом повторень завжди має рівновагу Неша.
Це справедливо також для ігор з нескінченним числом повторень, якщо виграші учасників представляють собою дисконтовану суму. Учасник не може збільшити виграш, змінивши своє рішення в односторонньому порядку, коли інші учасники не змінюють рішення. Така сукупність стратегій обраних учасниками та їх виграші називаються рівновагою Неша в грі Курно. p> Стохастична гра задається набором ігрових елементів або позицій кожен ігровий елемент представляється матрицею порядку, де - число стратегій першого гравця, - число стратегій другого гравця.
Елементи матриці задаються в наступному вигляді:
(1)
де - номер стратегії першого гравця (); - номер стратегії другого гравця (; - виграш першого гравця на-му кроці, якщо перший гравець застосує стратегію, а другий; - ймовірність переходу на позицію з позиції, якщо на-й позиції перший гравець застосував свою стратегію, а другий, причому з вірогідністю
(2)
здійснюється перехід на ігровий елемент, а з імовірністю
(3)
гра закінчується.
Умова (2) або (3) показує, що ймовірність нескінченного продовження гри дорівнює 0, а математичне сподівання виграшу звичайно.
Змішаної стратегією першого гравця називається повний набір ймовірностей застосування його чистих стратегій на-му кроці гри в ігровому елементі. p> Очевидно, задовольняє співвідношенням
<...
