2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


В этом разделе нельзя создавать новые темы.



Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3, 4, 5, 6  След.
 
 Re: теория игр, угадывание числа
Сообщение16.03.2015, 13:15 
Заслуженный участник
Аватара пользователя


15/10/08
12515
Слишком часто здесь звучит "я не понимаю". Давайте-ка ещё раз пробежимся по условию. Итак, игрок у нас один, а оптимальность стратегии понимается в смысле минимизации числа попыток. Если стратегия вероятностная - в минимизации среднего числа попыток.

 Профиль  
                  
 
 Re: теория игр, угадывание числа
Сообщение16.03.2015, 13:19 
Заслуженный участник
Аватара пользователя


01/09/13
4656
Euler7 в сообщении #990982 писал(а):
Рекурсивно из более маленьких матриц

Что означает эта матрица? Где там стратегии? Почему такая разница между 1 и 4 в этой матрице?

 Профиль  
                  
 
 Re: теория игр, угадывание числа
Сообщение16.03.2015, 13:28 
Аватара пользователя


21/09/12

1871
Утундрий в сообщении #990986 писал(а):
Давайте-ка ещё раз пробежимся по условию. Итак, игрок у нас один, а оптимальность стратегии понимается в смысле минимизации числа попыток. Если стратегия вероятностная - в минимизации среднего числа попыток.

Игроков у нас два. Один загадывает число, другой его угадывает. Надо найти наилучшую стратегию второго игрока при активном противодействии первого. И да, критерий оптимальности - среднее число попыток.

 Профиль  
                  
 
 Re: теория игр, угадывание числа
Сообщение16.03.2015, 13:39 


30/03/12
130
Geen в сообщении #990989 писал(а):
Что означает эта матрица? Где там стратегии? Почему такая разница между 1 и 4 в этой матрице?

Это матрица игры, как по столбцу восстановить стратегию второго игрока я описывал тут. Краткая инструкция по решению матричных игр есть тут.
Утундрий писал(а):
Итак, игрок у нас один, а оптимальность стратегии понимается в смысле минимизации числа попыток.

Игрока у нас 2 - один загадывает, а другой отгадывает. Первый минимизирует средний выигрыш второго, а второй наоборот его максимизирует.
Оптимальная стратегия игрока — стратегия,которая при многократном повторении игры обеспечивает данному игроку максимально возможный средний выигрыш(или, что тоже, минимально возможный средний проигрыш).

 Профиль  
                  
 
 Re: теория игр, угадывание числа
Сообщение16.03.2015, 13:51 
Заслуженный участник
Аватара пользователя


01/09/13
4656
Euler7 в сообщении #990998 писал(а):
как по столбцу восстановить стратегию второго игрока я описывал тут
.

Euler7 в сообщении #990766 писал(а):
Значит выбираем 3.
Получаем ответ "больше", теперь стратегии с номерами с 1 до 3 включительно недоступны


Смотрим на Вашу матрицу из первого поста для $n=4$, выбираем "первый столбец", находим в нём максимум 2, получаем ответ "больше"... "теперь стратегии с номерами от 1 до 2 включительно надоступны" - но их всего две в приведённой Вами матрице.

 Профиль  
                  
 
 Re: теория игр, угадывание числа
Сообщение16.03.2015, 14:01 


30/03/12
130
Geen в сообщении #991000 писал(а):
Смотрим на Вашу матрицу из первого поста для $n=4$, выбираем "первый столбец", находим в нём максимум 2, получаем ответ "больше"... "теперь стратегии с номерами от 1 до 2 включительно надоступны" - но их всего две в приведённой Вами матрице.

да, их две. Вы для данной партии выбрали первую из них(которая описывается вектором {3, 4, 2, 3}, после ответа 2 на первом шаге будет {3, 4, 2, 3} и ответ 4 на втором).

 Профиль  
                  
 
 Re: теория игр, угадывание числа
Сообщение16.03.2015, 14:33 
Заслуженный участник
Аватара пользователя


01/09/13
4656
Euler7 в сообщении #991002 писал(а):
Geen в сообщении #991000 писал(а):
Смотрим на Вашу матрицу из первого поста для $n=4$, выбираем "первый столбец", находим в нём максимум 2, получаем ответ "больше"... "теперь стратегии с номерами от 1 до 2 включительно надоступны" - но их всего две в приведённой Вами матрице.

да, их две. Вы для данной партии выбрали первую из них(которая описывается вектором {3, 4, 2, 3}, после ответа 2 на первом шаге будет {3, 4, 2, 3} и ответ 4 на втором).

Понятно, спасибо.
Но тогда следующий вопрос. Зачем при $n=7$ Вам считать, что имеется 25 стратегий, начинающихся с вопроса 4?

 Профиль  
                  
 
 Re: теория игр, угадывание числа
Сообщение16.03.2015, 14:57 


30/03/12
130
Geen в сообщении #991013 писал(а):
Но тогда следующий вопрос. Зачем при $n=7$ Вам считать, что имеется 25 стратегий, начинающихся с вопроса 4?

При ответе "больше" будет выбор из трёх чисел, т.е. 5 вариантов стратегий останется. Аналогично при ответе "меньше" 5 вариантов. И любой из ответов после "больше" можно сочетать с любым ответом после "меньше", значит всего 5*5. Это все возможные варианты развития событий.
Изображение

 Профиль  
                  
 
 Re: теория игр, угадывание числа
Сообщение16.03.2015, 15:48 
Аватара пользователя


21/09/12

1871
Не понял, как ТС решил игру на трёх числах. Всё сложнее.
Игрок А загадывает число, игрок В угадывает. Составляем матрицу игры, элементами которой являются числа попыток.
Если В с первого раза угадал число, то число попыток $1$. Это диагональные элементы $a_{11}, a_{22}, a_{33}$.
Если В начал угадывание с числа $2$, а А загадал $1$ или $3$, то на следующем ходу решение будет найдено. Т.е. для элементов $a_{12}$ и $a_{32}$ число попыток равно $2$.
А вот если А загадал $1$, а В первым назвал $3$, или наоборот А загадал $3$, а В первым назвал $1$, то на втором ходе число можно не угадать. И для В опять нужна стратегия. Как её получить? - Ясно, что первым надо называть число, имеющее бо`льшую вероятность быть названным А. Но эту вероятность мы пока не знаем. Поэтому назову пока эти элементы $x, y, z, k$.
Имеем матрицу:
Изображение
Что дальше?

 Профиль  
                  
 
 Re: теория игр, угадывание числа
Сообщение16.03.2015, 16:03 


30/03/12
130
atlakatl
составляем платёжную матрицу:
Изображение
строки - чистые стратегии первого игрока, столбцы - второго. Восстановление стратегий второго по столбцу объяснялось выше, для первого тривиально - номер строки и есть загаданное число. На пересечении стратегий стоит выигрыш второго игрока, он же проигрыш первого. Дальше решаем как и любую матричную игру. По этой ссылке можно воспользоваться онлайн-калькулятором игр. Кроме того случай n=3 разобран в книге Дрешер М. - Cтратегические игры Теория и приложения - 1964 со страницы 54.

 Профиль  
                  
 
 Re: теория игр, угадывание числа
Сообщение16.03.2015, 17:06 
Аватара пользователя


21/09/12

1871
Euler7 в сообщении #991049 писал(а):
случай n=3 разобран в книге Дрешер М. - Cтратегические игры Теория и приложения - 1964
со страницы 54.

Три страницы убористых вычислений. И это для простейшего - на первый взгляд - случая.

 Профиль  
                  
 
 Re: теория игр, угадывание числа
Сообщение16.03.2015, 17:13 
Заслуженный участник
Аватара пользователя


15/10/08
12515
Книжку я сейчас посмотреть не могу. Но потыкав наугад склоняюсь к использованию треугольника Паскаля.

-- Пн мар 16, 2015 18:32:31 --

Кстати, а как здесь формируется платёж? Я считал очки передаваемыми монетками.

 Профиль  
                  
 
 Re: теория игр, угадывание числа
Сообщение16.03.2015, 17:37 
Заслуженный участник


13/12/05
4604
Euler7
Вы стратегии задаете в виде вектора из $n$ чисел. Как такое задание соотносится c моим понимание стратегии:
Padawan в сообщении #990788 писал(а):
Как я понимаю, что такое стратегия второго игрока: Это граф-дерево, в первой вершине которого стоит число, которое игрок должен назвать в первый раз, и из каждой вершины выходит от одного до трех ребер, соответствующих возможным ответам первого игрока: "больше", "меньше", "угадал", эти ребра ведут в вершины, где стоит очередное число, которое должен назвать второй игрок.

 Профиль  
                  
 
 Re: теория игр, угадывание числа
Сообщение16.03.2015, 18:48 
Аватара пользователя


21/09/12

1871
Padawan в сообщении #991086 писал(а):
Как такое задание соотносится c моим понимание стратегии:

По Дрешеру получается так:
Например, вектор $(4, 2, 6, 1, 3, 5, 7)$ означает: первым ходом называется $4$. Если следует ответ "много", то называется $2$, если "мало" - $6$. Дальше рассматривается выбор после второго ответа: $1$, если на предыдущее $2$ последовало "много", $3$ - если "мало", и т.д.

 Профиль  
                  
 
 Re: теория игр, угадывание числа
Сообщение16.03.2015, 19:15 
Заслуженный участник
Аватара пользователя


15/10/08
12515
Глянул, платёж там выдаётся только первому игроку и это таки да - количество попыток второго. О платеже второму - ни слова. Поэтому я ещё раз внимательно спрашиваю, что это за сто очков за угадывание и вообще, огласите правила целиком, пжалста.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 77 ]  На страницу Пред.  1, 2, 3, 4, 5, 6  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

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


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group