Как плохому шахматисту победить хорошего

Аватар пользователя
Ian
Сообщений: 960
Зарегистрирован: 18 янв 2016, 19:42

Как плохому шахматисту победить хорошего

Сообщение Ian » 21 фев 2021, 17:03

Assume that you play a chess match with a friend. If you play timid your probability of making a draw is p = 0.9, the probability to win is 0 and the probability to lose is 0.1. If you play bold you either win with probability q = 0.45, or you lose. Each win brings one point to the score of the winner. The match consists of 5 games. If the score is a tie after the fifth game, then a “sudden death” rule is adopted; that is, whoever wins the next game is a winner of the math; if it is a draw, then the game is repeated with the same rule.

Formulate a Markov decision problem to determine the optimal strategy of your play (to maximize the probability of winning the match) and solve it. Clearly describe the state space, control space, transition probabilities, and the reward function.
Кратко смысл: В матче из 5 партий мы можем в любой игре придерживаться "осторожной" стратегии, при которой вероятность ничьей 0.9, а вероятность нашего проигрыша 0.1, а можем рискованной, где у нас вероятность выигрыша 0.45, а проигрыша 0.55. И оказывается, есть тактика с вероятностью выигрыша матча 0,526 (в этой задаче для простоты игнорируется преимущество белых фигур)

zykov
Сообщений: 1393
Зарегистрирован: 06 янв 2016, 17:41

Как плохому шахматисту победить хорошего

Сообщение zykov » 21 фев 2021, 18:51

Тут интуитивно понятно, что "осторожную" надо выбирать, только если уже есть преимущетсво по очкам, т.к. по этой стратегии вообще не выигрываешь, а только медленно проигрываешь (но есть шанс сохранить преимущество до 5ой партии - $0.9^4 = 0.6561$).
Так например, если после пятой партии ноль очков, то нет смысла быть "осторожным", т.к. точно не выиграешь. Иначе выигрываешь с вероятностью 0.45.

Т.е. стратегия - если ноль или минус очков, то рискуем, если плюс очков, то осторожно играем. Это можно строго доказать, если перебрать все 32 варианта для 5 бинарных выборов.

Для этой стратегии (при пяти партиях) можно ограничится состояниями {-3, -2, -1, 0, 1}. При этом -3 означает проигрышь, т.к. уже не отигратся, т.е. из этого состояния автомат обратно в него переходит (чтобы не учитывать детали). Больше 1 мы с этой стратегией не поднимемся.
Автомат:
1: 0.9 в 1, 0.1 в 0
0: 0.45 в 1, 0.55 в -1
-1: 0.45 в 0, 0.55 в -2
-2: 0.45 в -1, 0.55 в -3
-3: всегда в -3
Матрица:
$$M=\begin{pmatrix}0.9 & 0.45 & 0 & 0 & 0\\ 0.1 & 0 & 0.45 & 0 & 0\\ 0 & 0.55 & 0 & 0.45 & 0\\ 0 & 0 & 0.55 & 0 & 0\\ 0 & 0 & 0 & 0.55 & 1\end{pmatrix}$$
Начальный вектор:
$$b=\begin{pmatrix}0\\ 1\\ 0\\ 0\\ 0\end{pmatrix}$$

Тогда
$$M^5 \cdot b = \begin{pmatrix}\frac{801171}{1600000}\\ \frac{22599}{400000}\\ \frac{278883}{1600000}\\ \frac{9801}{800000}\\ \frac{102487}{400000}\end{pmatrix}$$

Значит вероятность выиграть $$\frac{801171}{1600000} + 0.45 \frac{22599}{400000} = \frac{2104623}{4000000} = 0.52615575$$.
Последний раз редактировалось zykov 21 фев 2021, 20:34, всего редактировалось 3 раз.

zykov
Сообщений: 1393
Зарегистрирован: 06 янв 2016, 17:41

Как плохому шахматисту победить хорошего

Сообщение zykov » 21 фев 2021, 19:05

Если обозначить $p=0.9$ и $q=0.45$, то в общем виде вероятность выиграть $2 {{q}^{5}}+\left( 2 {{p}^{2}}-6\right) \, {{q}^{4}}+\left( 2 {{p}^{3}}-6 {{p}^{2}}+5\right) \, {{q}^{3}}+\left( -{{p}^{4}}-2 {{p}^{3}}+4 {{p}^{2}}\right) \, {{q}^{2}}+{{p}^{4}} q$.
Можно посмотреть для каких $p$ и $q$ эта вероятность больше 0.5 (интересует $q<0.5$).

zykov
Сообщений: 1393
Зарегистрирован: 06 янв 2016, 17:41

Как плохому шахматисту победить хорошего

Сообщение zykov » 21 фев 2021, 19:29

Вобщем критический $q \approx 0.37232$ (корень многочлена ${{q}^{5}}-4 {{q}^{4}}+{{q}^{3}}+{{q}^{2}}+q-\frac12$).
Ниже этого $q$ для любых $p$ вероятность выигрыша менее 0.5.
Выше - критическое $p$ будет приближатся к 1 по мере приближения к этому критическому $q$. Если $p$ выше критического, то выигрышь более 0.5.

Для $q=0.45$ критическое $p \approx 0.8661$.

Аватар пользователя
Ian
Сообщений: 960
Зарегистрирован: 18 янв 2016, 19:42

Как плохому шахматисту победить хорошего

Сообщение Ian » 21 фев 2021, 19:33

zykov писал(а):Т.е. стратегия - если ноль или минус очков, то рискуем, если плюс очков, то осторожно играем. Это можно строго доказать, если перебрать все 32 варианта для 5 бинарных выборов.

Для этой стратегии (при пяти партиях) можно ограничится состояниями {-3, -2, -1, 0, 1}. ....

У нас похожие выводы, но у вас беда с обозначениями. Вы считаете, что (проигрыш, ничья, выигрыш) это (-1; 0;1), а весь шахматный мир (0;0,5;1) -см историю шахматных матчей за последние 150 лет. Можно отредактировать в эту сторону?

zykov
Сообщений: 1393
Зарегистрирован: 06 янв 2016, 17:41

Как плохому шахматисту победить хорошего

Сообщение zykov » 21 фев 2021, 19:37

А зачем?
Это же просто линейное преобразоваение. Я специально в качестве метрики выбрал разность очков (а не пару очков) в целых значения (для удобства).
Т.е. моя метрика - это $2(x_1 - x_2)$.

Аватар пользователя
Ian
Сообщений: 960
Зарегистрирован: 18 янв 2016, 19:42

Как плохому шахматисту победить хорошего

Сообщение Ian » 21 фев 2021, 19:40

zykov писал(а):...

Значит вероятность выиграть $$\frac{801171}{1600000} + 0.45 \frac{22599}{400000} = \frac{2104623}{4000000} = 0.52615575$$.

У меня все знаки совпали с Вашими. Доказательство другое (уравнения динамического программирования)

Аватар пользователя
Ian
Сообщений: 960
Зарегистрирован: 18 янв 2016, 19:42

Как плохому шахматисту победить хорошего

Сообщение Ian » 21 фев 2021, 19:46

Я как бы следовал общей теории, в которой и задали эту задачку в США. Там желательно чтобы множество возможных состояний было естественным, и я выбрал состояние -это набранные очки (0; 0.5; 1; 1.5; 2; 2.5; W) где W поглощающее марковское состояние (победа), включающее в себя все очки не меньше 3 (причем после 5й партии при равном счете не прибавляются очки, а просто отдается нам 0,45 призового фонда, ясно же , что осторожной стратегии не будет)

zykov
Сообщений: 1393
Зарегистрирован: 06 янв 2016, 17:41

Как плохому шахматисту победить хорошего

Сообщение zykov » 21 фев 2021, 19:55

Ну обозначить состояния автомата можно любыми именами (хоть "банан", "апельсин" и т.д.).
Мне было удобно целыми числами обозначить, так чтобы либо изменялось на 1 (вниз или вверх), либо не изменялось. Состояние "ничьи" соответсвует нулю.
Ian писал(а):Source of the post Доказательство другое (уравнения динамического программирования)

А можно подробнее посмотреть?

zykov
Сообщений: 1393
Зарегистрирован: 06 янв 2016, 17:41

Как плохому шахматисту победить хорошего

Сообщение zykov » 21 фев 2021, 21:21

zykov писал(а):Source of the post Это можно строго доказать, если перебрать все 32 варианта для 5 бинарных выборов.

Тут я не прав, эти 32 варианта не помогут.
Нужно с конца начинать разматывать подбирая максимум для каждого состояния (из 7: от -3 до +3), учитывая что предыдущий шаг дал максимум для следующей партии.

Аватар пользователя
Ian
Сообщений: 960
Зарегистрирован: 18 янв 2016, 19:42

Как плохому шахматисту победить хорошего

Сообщение Ian » 22 фев 2021, 04:25

USA это страна ломаного английского, таким и написано
Problem1_copy.pdf
(101.3 KiB) Загружено 400 раз

Аватар пользователя
Ian
Сообщений: 960
Зарегистрирован: 18 янв 2016, 19:42

Как плохому шахматисту победить хорошего

Сообщение Ian » 22 фев 2021, 08:36

zykov писал(а):Source of the post
Нужно с конца начинать разматывать подбирая максимум для каждого состояния (из 7: от -3 до +3), учитывая что предыдущий шаг дал максимум для следующей партии.
Это принцип оптимальности динамического программирования, как для детерминированных процессов, так и стохастических. Разные люди регулярно делают попытки применять его повсюду в жизни, и тем более в роботов закладывать. Например, в поиске стратегии для коммерческой фирмы. Но тут есть два препятствия : как оценить вероятности, участвующие в решении, а от них сильно зависит ответ; какой выбрать конечный момент времени, в который наблюдается целевая функция, бывают решения, которые первые несколько лет убыточны, но выводящие на максимальную прибыль. Вот еще их типовой пример
Problem 2. A software manufacturer can be in one of two states. In state 1 their software sells well, and in state 2, the product sells poorly. While in state 1, the company can invest in development of upgraded version of the software, in which case the one-stage reward is 4 units, and the probability of degrading to state 2 is 0.2. If no investment in new development occurs, then the reward is 6 units, but the probability of transition to state 2 is 0.5. While in state 2, if the company invests in software development, then the reward is -2 units, but the probability of transition to state 1 is 0.7. Without special efforts to improve, the reward is 1 and the probability of upgrading to state 1 is 0. Formulate a dynamic programming problem to determine an optimal reserch and development policy. Solve the problem for a time horizon of 12 time intervals.

zykov
Сообщений: 1393
Зарегистрирован: 06 янв 2016, 17:41

Как плохому шахматисту победить хорошего

Сообщение zykov » 22 фев 2021, 08:41

Ian писал(а):Source of the post
Problem1_copy.pdf

Понятно.
Я просто посчитал вероятность не доказывая оптимальности стратегии.
Они и считают, и доказывают. Как я и думал, разматывая с конца (сначала $V_5^*$, потом $V_4^*$ и т.д.).

zykov
Сообщений: 1393
Зарегистрирован: 06 янв 2016, 17:41

Как плохому шахматисту победить хорошего

Сообщение zykov » 06 мар 2021, 08:33

zykov писал(а):Source of the post Тут интуитивно понятно, что "осторожную" надо выбирать, только если уже есть преимущетсво по очкам

Конечно эту интуицию нужно строго обосновывать.
Для 5 партий оно всё правильно, но вот при 12 партиях будет перелом.
Для 12 - если в первой партии выиграл, то во второй партии тоже выгодно рискнуть. В остальном, всё так же.
Такая стратегия даёт вероятность выиграть примерно 0.50080205.
А интуитивная стратегия даст вероятность примерно 0.49831495.


Вернуться в «Математика»

Кто сейчас на форуме

Количество пользователей, которые сейчас просматривают этот форум: нет зарегистрированных пользователей и 4 гостей