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