Цу-е-фа

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

Любой элемент что-то побеждает и чем-то побеждается, а чтобы чаще выигрывать - либо надейтесь на удачу, либо развивайте интуицию и наблюдательность. Но: 1) если у игроков выпадают одинаковые элементы, 2) если играет не менее 3 человек и выпали все 3 элемента хотя бы по разу - ход получается ничейным, и в теории ничейная серия может продолжаться до бесконечности. А что же на практике? Подключим теорию вероятности и посчитаем среднюю длину розыгрыша (в ходах).


В КНБ может быть неограниченное количество участников - от двух и более. При этом в зависимости от цели игра идет либо до победителя (определяется 1 человек), либо до распределения всех мест (например, очередности). Возможен вариант "до единственного проигравшего", но он идентичен первому с точностью до зеркальной симметрии.

Чем больше игроков, тем дольше будет игра и тем чаще будут выпадать ничьи. Ниже привожу подсчеты:

2 игрока. Ничейных исходов P = 1/3 (3 из 9), средняя длина розыгрыша L = 1 / (1-P) = 1,5 хода.

3 игрока. Ничейных исходов P = 1/3 (9 из 27), средняя длина первого розыгрыша L = 1 / (1-P) = 1,5 хода.

До победителя: 1/2, что первый розыгрыш его определил, 1/2 - что он определил проигравшего и осталось двое. В первом случае нужно 1,5 хода, во втором - два раза по 1,5, в среднем - 2,25 хода.

До всех мест: в любом случае розыгрыш разделяет троих на 1 и 2, которые должны сыграть между собой. В среднем распределение всех мест длится 1,5 + 1,5 = 3 хода.

4 игрока. Ничейных исходов P = 13/27 (39 из 81), средняя длина первого розыгрыша L = 1 / (1-P) = 27/14 ~ 1,929 хода.

До победителя: 3/7 (18 исходов из 42), что он уже определен, 3/7 - что в игре осталось трое, 1/7 - что двое. Общая длина партии = 3/7 * 27/14 + 1/7 * (27/14 + 1,5) + 3/7 * (27/14 + 2,25) = 27/14 + 3/14 + 27/28 = 87/28 ~ 3,107 хода.

До всех мест: 6/7, что первый розыгрыш разделил четверых на 1 и 3, 1/7 - что на 2 и 2. Общая длина розыгрыша всех мест = 6/7 * (27/14 + 3) + 1/7 * (27/14 + 1,5 + 1,5) = 69/14 ~ 4,929 хода.

Два раза прибавляется 1,5, потому что нужно провести розыгрыш в каждой из двух образовавшихся пар. Да, и при этом ходы в двух разделившихся группах считаются по отдельности, хотя могут происходить одновременно.

Далее провел аналогичные расчеты. Итоги:
5 игроков - первый розыгрыш 2,7 хода, до победителя - 1251/280 ~ 4,468 хода, до всех мест - 257/35 ~ 7,343 хода;
6 игроков - первый розыгрыш 243/62 ~ 3,919 хода, до победителя - 13437/2170 ~ 6,192 хода, до всех мест - 22539/2170 ~ 10,387 хода.
7 игроков - первый розыгрыш 243/42 ~ 5,786 хода, до победителя - 448537/52080 ~ 8,612 хода, до всех мест - 15507/1085 ~ 14,292 хода.

Дальше получаются совсем уж некрасивые дроби, так что не считал. Да и очень редко видел, чтобы в КНБ играли более чем всемером.
___

Теперь можно оценить эффективность игры средствами теории информации. При выявлении победителя из N игроков (то есть просто определении одного элемента из N) нам необходимо получить lb N бит информации, где lb - двоичный логарифм (он же log2). Распределение всех мест - это выбор одной перестановки N элементов изо всех возможных, которых, как известно, N! - факториал от количества элементов, то есть объем получаемой информации равен lb N! Вычислив общий объем, можно определить среднее количество информации, которое приносит 1 ход.

Кол-во игроков	Ходов в среднем	Общее кол-во информации, бит	Информация от 1 хода, бит
2	1,5	1	0,667
3, до победы	2,25	1,585	0,704
4, до победы	3,107	2	0,644
5, до победы	4,468	2,322	0,520
6, до победы	6,192	2,585	0,417
7, до победы	8,612	2,807	0,326
3, все места	3	2,585	0,862
4, все места	4,929	4,585	0,930
5, все места	7,343	6,907	0,941
6, все места	10,387	9,492	0,914
7, все места	14,292	12,299	0,861

Итак, если игра в КНБ идет до выявления победителя (либо проигравшего - ситуация симметричная, главное, что определяется 1 человек), наилучшая эффективность в получении нужной информации от каждого хода достигается при 3 игроках; при игре до расстановки всех мест - при 5 игроках.


Непонятно только одно - зачем я это делаю. Даже не спрашивайте, сам не знаю.