Камень, ножницы, бумага

[vlad_light]

Проходит турнир по игре "Камень, ножницы, бумага". Правила турнира такие:
1) в турнире участвет $N$ человек, из них призы получат $M (M<N)$ первых мест;
2) призы распределены таким образом, что за каждое следующее место выплачивается в $C$ раз больше, чем за предыдущее;
3) перед турниром игроки могут потренироваться друг с другом (никто не в праве отказать в тренировке);
4) после окончания тренировки, игроки случайным образом разбиваются на пары и проводят серию из $X$ игр. Игрок, одержавший большее количество побед, переходит в следующий раунд, а его соперник покидает турнир.
В нашем распоряжении есть серии из $Y+kX$ игр с каждым участником турнира ($Y$ - тренировочных игр и $k$ по $X$ турнирных игр). Более того, все участники - живые люди, поэтому они не могут действовать абсолютно случайно.
Задача - выиграть турнир. Суть в том, что чем дальше мы продвигаемся по турниру, тем большей информацией владеем. Расскажите, пожалуйста, какие есть способы анализа данных выборок?
Первое, что приходит в голову - всегда ставить доминирующий знак наиболее частого знака в выборке оппонента. Но такая стратегия, очевидно, не будет выиграшной.

[ASP]

В этом виде спорта проводились соревнования среди ботов, см "International RoShamBo Programming Competition"
Некоторые боты, в том числе победители, доступны в исходном коде: http://webdocs.cs.ualberta.ca/~darse/rsbpc.html#LINKS .

[vlad_light]

Спасибо, попробую разобраться в коде. А вообще меня больше интересовала не данная игра, а общий подход для анализа подобных выборок.
Можете на пальцах объяснить, в каком направлении стоит думать при прогнозировании подобных результатов? Спасибо!

[PAV]

Достаточно общий и вполне разумный метод в подобных задачах такой. Вы хотите вероятностным образом предсказать поведение системы в некоторой ситуации. Предсказание будет делаться на основе нескольких предыдущих шагов - состояний, в которых находилась система до этого момента. Берется известная история и в ней ищутся все похожие ситуации. Смотрим, как вела себя система в этих ситуациях, и по этой статистике делаем прогноз. Чем больший объем наблюдений нам доступен, тем большее количество шагов можно брать.

[vlad_light]

Спасибо, но это слишком уж общий метод... Я хотел бы услышать пусть даже простые, но конкретные методы анализа. Для начала, например, скажите, какую в данной игре выборку стоит анализировать (одно- или двухмерную, если двух-, то какие?)?
Я нашёл по-моему схожую тему на вики -- анализ псевдослучайных последовательностей. Там есть алгоритмы для проверки последовательности на случайность, но проблема в том, что они очень сложные для понимания. Я хотел бы посмотреть с чего всё начиналось, от самых простых тестов к сложным (насколько я понял, сложная проверка является лишь хитрой комбинацией простых).
Также я читал на каком-то форуме, что предугадывать нужно не конкретную фигуру (К, Н или Б), а две фигуры, т.е. выдвигать гипотезу о том, что соперник поставит "К или Н", а не просто К.

Цитата:

... и в ней ищутся все похожие ситуации

Это что-то типа в выборке
К Н Б Н Б К Б Н Б Б К Н Н Б Н Б К Н Б Б Н К Б Н Б Н Б ?
соперник выберет К или я не так понял?

[PAV]

vlad_light в сообщении #583589 писал(а):

Это что-то типа в выборке
К Н Б Н Б К Б Н Б Б К Н Н Б Н Б К Н Б Б Н К Б Н Б Н Б ?
соперник выберет К или я не так понял?

Да, примерно так. Вы же просили общий принцип - я его предложил. Точнее даже общую идею. Разумеется, в каждой конкретной ситуации имеется много своих технических (и идейных) деталей, которые нужно додумывать.

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

[vlad_light]

Спасибо. А можете помочь посчитать количество операций для вычисление предложенного Вами алгоритма для выборки размера N? У меня получилось что-то порядка $N^2$, немного меньше. Попробую написать такую программу...

Цитата:

и все замечательные стратегии могут совершенно замечательно не работать.

Конечно! Если, например, соперник будет равновероятно ставить К, Н или Б, то у него будет невозможно выиграть... впрочем, проиграть ему также будет невозможно. Другое дело -- как только соперник пытается применить какую-то стратегию или контр-стратегию, то его последовательность автоматически перестаёт быть случайной, следовательно, её можно анализировать. Т.е. фактически нам нужно определить случайность последовательности соперника и выявить в ней некоторые закономерности. Вы можете подсказать ещё какие-нибудь идеи по этому поводу?

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