Игра "Очко". Расчет вероятности компьютером

[The_Immortal]

Всех приветствую!

Друзья, возникла задача написать игрушку, эмитирующую игру "21" против компьютера.

Сейчас дело дошло до составления алгоритма принятия решения компьютером брать очередную карту или нет.

Посмотрел блуждающие в инете исходники по этой игре. В основном алгоритм принятия решения следующий:

Если Кол-во_Очков < N То БратьКарту() 

, где N = [15,16,17]
Вероятно, при общем количестве очков равном 15, я бы тоже тянул очередную карту, ничего не считая, но вот при 16 (17) - задумался бы.

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

Пример.
Игрок (на руках): Валет♥, Туз♣ (2 + 11 = 13 очков)
Компьютер (на руках): 10♣, Валет♦, Король♠ (10 + 2 + 4 = 16 очков)
Колода: 36 - 4 = 32 карты

Ходит Компьютер. Задача: рассчитать вероятность того, что следующей вытянутой картой будет либо Валет (2 очка), либо Дама (3 очка), либо Король (4 очка), либо Туз (1 очко).

Решение. Общее кол-во нужных карт в колоде: 4 х 4 = 16. Учитываем карты на руках: 16 - 2 (у Игрока) - 2 (у Компьютера) = 12. Делим полученное значение на оставшееся кол-во карт в колоде: 12 / 32 = 0,375.

Как-то слишком просто. Где я обшибся?


Спасибо!

[svv]

А разве честно, что компьютер использует информацию о картах игрока?

[gris]

Странное очко. Кто там банкует? Если компьютер, то он не должен знать карты игрока. То есть, он, конечно, знает, что брал игрок, но обязан игнорировать это знание. Иначе зачем ему ещё одна карта, если у него уже больше очков. И странно, что игрок остановился на 13.

[The_Immortal]

svv, я тоже задумался об этом. Но ведь Игрок также видит карты компьютера :)
Но в условии задачи об этом, честно говорят, ничего не сказано, поэтому я пошел искать онлайновые "21". Первой попалась реализация этой игры на небезызвестном ресурсе mail.ru: там видны карты оппонента, если я ничего не напутал. Потом я наткнулся на другую реализацию: у оппонента видна только одна первая карта, оставшиеся кладутся рубашкой вверх.
И все же я решил сделать карты открытыми. Хотя... Если Компьютер, имея у себя на руках 19 очков, будет наблюдать у Игрока кол-во очков, равное, скажем, 20, то НЕ рисковать будет глупо - уже терять будет нечего.

Но вопрос все же был не в этом, а в расчетах.


gris,

gris в сообщении #824981 писал(а):

Кто там банкует?

А банка-то и нет :) Просто считается кол-во побед и минимальное кол-во ходов, за которое Игрок набирает нужное количество очков (см. ниже).

gris в сообщении #824981 писал(а):

И странно, что игрок остановился на 13.

А Игрок и не остановился. Я промоделировал ситуацию, когда ходили: Компьютер, Игрок, Компьютер, Игрок. Теперь ход Компьютера, после которого будет ходить Игрок.

В общем, вот условия (составлял их не я):

Цитата:

Двадцать одно (игра с компьютером). Правила: Игроки по очереди берут карту (6,7,8,9,10, В, Д, К, Т). Каждой карте соответствуют очки: 6-10 – соответственно 6-10 очков, В – 2, Д – 3, К – 4, Т – 11 или 1. Цель: первым набрать 21 очко. Кто первый набрал, тот победитель. Необходимо так же подсчитывать количество ходов, за которое игрок набирает нужное количество очков. Минимальное количество ходов записывается в таблицу рекордов.

[gris]

А, всё ясно. Это другая игра. И игрок и комп видят всё. Ну тогда можно перед очередным ходом посчитать все нужные вероятности. Даже заглянуть на несколько ходов вперёд.

[The_Immortal]

gris, так то, что я выше считал - правильно? Или бессмысленно?

gris в сообщении #824991 писал(а):

Ну тогда можно перед очередным ходом посчитать все нужные вероятности

Ну до 15 очков включительно вероятность я ставлю равной 1. А вот уже после - считать.

gris в сообщении #824991 писал(а):

Даже заглянуть на несколько ходов вперёд.

Эм... А как это? :)

gris в сообщении #824981 писал(а):

Кто там банкует? Если компьютер, то он не должен знать карты игрока.

Хм, так вообще по уму: банкир должен знать какие карты игрока или нет? Вот все тот же пример с mail.ru. Банкир выкладывает одну карту, которую видит игрок. Далее ходит игрок и все карты игрока Банкир видит. После того как игрок сходил (не перебрав лишнего или не схватив очко), ходит Банкир, видя при этом те карты, которые вытащил игрок.

[gris]

Вы почти правильно посчитали. Только в колоде осталась 31 карта. Можно обсчитать все случаи, построить таблицу, например, для Вашего случая: на руках 10 В В К Т (масти же не важны). Кстати, почему у Вас Туз имеет разную стоимость? 11 очков и 1 очко.
2 очка — вероятность $2/31$
3 очка — вероятность $4/31$
4 очка — вероятность $3/31$
6 очков — вероятность $4/31$
...
11 очков — вероятность $3/31$

Ну а что потом? Можно посчитать матожидание прихода.

Шаг вперёд — это подсчёт всех условных вероятностей получения очков партнёром. Он не имеет особого смысла, так как у игрока только два варианта: брать или не брать карту.
Ну, конечно, надо начинать с чёткого перечисления всех правил игры.

[The_Immortal]

gris,

gris в сообщении #825010 писал(а):

Ну, конечно, надо начинать с чёткого перечисления всех правил игры.

Изиняюсь :(

gris в сообщении #825010 писал(а):

Только в колоде осталась 31 карта.

Упс, действительно... Совсем вручную считать разучился :)

gris в сообщении #825010 писал(а):

Кстати, почему у Вас Туз имеет разную стоимость? 11 очков и 1 очко.

А по тем же Правилам. Если общее кол-во очков больше 10 и нам приходит Туз, то он считается равным 1. Это условие вроде как и в нормальных правилах присутствует.

gris в сообщении #825010 писал(а):

2 очка — вероятность $3/31$
3 очка — вероятность $2/31$

Не поясните? Немного не понял, почему вероятность появления Валетов (или Вальтов?) равна $3/31$? Их же осталось в колоде всего два. И с Дамами также не ясно - их вообще не задействовали.

gris в сообщении #825010 писал(а):

Ну а что потом? Можно посчитать матожидание прихода.

Какие-то страшные слова :) Пойду вспоминать, что это и нужно ли оно вообще :)

[gris]

Я немного перепутал с ценой карт
Ну тогда можно добавить
1 очко — вероятность $3/31$
Я думаю, тут можно много мудрить.

[The_Immortal]

gris, честно говоря, Вы немного меня озадачили матожиданием... Я вспомнил, что это такое, но так и не понял, зачем оно может понадобится Компьютеру при принятии решения... Знать на что в среднем рассчитывать при раскрытии следующей карты? Но ведь, наверняка, будут попадаться значения типа 3,5 - их в какую сторону округлять? :)
И коль пошла такая пьянка, то имеет ли смысл рассматривать дисперсию? Правда, не очень понимаю, что это мне даст...

gris в сообщении #825021 писал(а):

Я думаю, тут можно много мудрить.

А например? Хоть умные мысли послушать...

[gris]

Кстати, когда я говорил, что надо вначале правила писать, то это не в этой теме, а вообще при составлении программы. А то получилось, что я Вас упрекнул . Вовсе нет. Правила меняются и от этого меняются стратегии.
Я сам игрывал бывалыча в обыкновенное очко с двумя лбами, переборами и прочими делами. Да и то не впомню, что там насчёт использованных карт? Кладутся они в низ колоды, или колода каждый раз собирается и тасуется? Да, пришла худая череда. Зашибло...
А в этой игре мне и вовсе не понятно, какова цель игры.

[The_Immortal]

gris

gris в сообщении #825045 писал(а):

Да и то не впомню, что там насчёт использованных карт?

У того же Майла:

Цитата:

Примечание: перед началом игры колода делится произвольно на две части. Играют карты из верхней части колоды, отыгранные карты в дальнейшей игре не принимают участия. Если карты закончились, а игра продолжается, то отыгранные карты перетасовываются и используются в игре повторно.

У меня же в каждом новом раунде идет перетасовка и формируется полноценная колода.

gris в сообщении #825045 писал(а):

А в этой игре мне и вовсе не понятно, какова цель игры.

Вообще, нет банка - нет игры. Но лично я установил условную цель. Есть некое нечетное количество раундов (фреймов), скажем, 11. При достижении одной из сторон 6 выигранных раундов, ему присваивается победа

И все-таки как быть с этим (значение матожидания)

The_Immortal в сообщении #825026 писал(а):

Но ведь, наверняка, будут попадаться значения типа 3,5 - их в какую сторону округлять? :)

я не знаю... Включать псевдослучайный генератор, который будет решать в какую сторону округлять при вероятности 50/50?

[gris]

Зачем округлять? Просто прибавляем матожидание к текущему значению. Если получаем перебор, то не берём карту. Или что-то в этом роде.

[The_Immortal]

gris

gris в сообщении #825152 писал(а):

Зачем округлять?

Поясню.

Рассмотрел следующую ситуацию:

Игрок: 6, 10.
Компьютер: 6, 10.

Ходит Компьютер.

Считаем.
1 очко — вероятность $4/32$
2 очка — вероятность $4/32$
3 очка — вероятность $4/32$
4 очка — вероятность $4/32$
6 очков — вероятность $2/32$
...
10 очков — вероятность $2/32$

$M(x)=5,25$

gris в сообщении #825152 писал(а):

Просто прибавляем матожидание к текущему значению. Если получаем перебор, то не берём карту.

Если (ТекущееЗначение + M(x) > 21) Тогда Пас()
Иначе БеремКарту()

Получается: 16 + 5,25 = 21,25 > 21.

Следовательно, при наличии 16 и более очков (и при равном счете с Игроком), Компьютер никогда не будет брать карту... А вот живой человек бы рискнул, по крайней мере в данной ситуации.

[nikvic]

The_Immortal в сообщении #825192 писал(а):

Следовательно, при наличии 16 и более очков (и при равном счете с Игроком), Компьютер никогда не будет брать карту... А вот живой человек бы рискнул, по крайней мере в данной ситуации.

Наверное, программёр был плохим математиком

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