Юляша писал(а):Итак, предлагается найти возможность для компьютеров сыграть в только что изобретенную игру "темный пьяница".
Правила игры. В игре участвуют К игроков (K>=3) с использованием N 52-карточных колод (число N оговорено заранее).
Все карты (N*52) замешиваются в общую колоду из которой каждому игроку сдается по одной карте (вариант - по M карт). Ходы делаются по очереди.
Игрок смотрит свои карты, выбирает одну из них и берет из колоды столько карт, каково значение выбранной (Туз - одну, от двойки до девятки - соответствующее число, картинки - 10 карт). Эту стопку карт он не глядя кладет перед собой, а все прежние карты сбрасывает. Другие игроки не знают, сколько именно карт было взято. Ход затем переходит к следующему игроку.
Промоделировать можно ли?
Для примера (масти неважны, поэтому пишу только значения), раздали 4-м игрокам по 2 карты из четверной колоды:
Север: 4, 9
Восток: A, 3
Юг: 5, J
Запад: 8, 9.
В колоде осталось 200 карт. Начинаем с севера, и идем по часовой стрелке.
Север берет из колоды 9 карт и, для удобства, раскладывает их по возрастанию (например, 2, 4, 5, 6, 6, 8, J, J, J) в "руке". А четверку и девятку кидает в "отбой". В колоде остается 191 карта. Но остальным игрокам неизвестно, что Север выбрал девятку (!).
Вопрос первый - таким образом, Востоку неизвестно, что осталась 191 карта? Условно, пусть они выбирают, по очереди: туз, валет, восемь, и тем самым скидывают из колоды 1+10+8=19 карт, оставляя 172. И, следовательно, Север (чей ход настал) не знает, что их 172?
Если ответ "да", то после ряда кругов приходим к возможному состоянию: ход Юга, у него 5 карт (A, 3, 8, K, K). А в колоде (Юг этого не знает) - осталось 6 карт. Значит ли это (и это
второй вопрос), что Юг проиграет с вероятностью 3/5? Ведь если он выберет короля, то он проиграл. Но если тройку - то игра продолжается, и все зависит от того, какие карты у Запада и Севера, и их выбора.
Тактика случайного выбора работает нечестно. То есть либо ИИ выбирает всегда наименьшую карту, либо произвольную, но только до какого-то момента, а потом - только наименьшую. Но это тактика, а не техническое воплощение...
Если использовать сервер, который будет крупье - все легче легкого. Но если крупье нет, то кто-то должен стать дилером, и нужно шифровать больше, чем раньше.
Попробую объяснять "на пальцах". Может быть, путано, но как есть.
Поскольку длинно и текстово, то не прячу шрифт.
Пусть каждый из компьютеров придумает свой собственный шифр на всю колоду: переводит одну карту в другую. Главное условие - коммутативность шифров и единственность обратного перехода. И еще такой же шифр - на этот раз на "мегаколоду" 52*N+1 (N стандартных колод плюс джокер - ниже будет понятно, зачем это). В принципе, это может быть и единый шифр - но у каждого игрока свой.
Ремарка про коммутативность важна: дешифровка должна работать в любом порядке (пусть алгоритм шифровки прописная буква, дешифровки - строчная): Пусть З(Ю(В(С(карта X))))=карта Y, тогда карта X=з(с(в(ю(карта Y))))=в(ю(з(с(карта Y))))=ю(в(с(з(карта Y))))=...
Итак, к раздаче карт из колоды. Север шифрует всю колоду (можно стасовать, чтобы не дать подсказки сопернику), потом Восток, потом Юг, потом Запад. Потом, уже
зашифрованную колоду тасует Север, и создает список из записей (пользуясь паскалевской терминологией).
Каждая запись состоит из: ID (он же UIN, является одной из карт "мегаколоды" - в том числе и джокер), значения карты (4-жды зашифрованного, помните?) и ссылки на ID "следующей" карты. В самый "низ" колоды он "кладет" джокера (его не шифровали ну и пусть), у которого тоже будет свой ID, а поле "ID следующей" можно оставить и пустым.
ID "верхней" карты Север просто запоминает и никому не говорит. Потом Север берет все ссылки на ID "следующей" и шифрует их, потом передает по кругу на шифровку и заменяет все ссылки на зашифрованные ссылки. Список из записей в таком виде выкладывается в открытом доступе. Теперь он устроен так, что без знания дешифровки ссылки узнать, какая карта идет за какой - невозможно. А расшифровать ее можно только всем сразу.
Раздача происходит следующим образом:
Север "берет" себе верхнюю карту (ID он помнит - см. выше), запоминает ее значение и ID следующей - пока зашифрованные! Пускает их по кругу для дешифровки. При этом значение "сданной" ему карты дешифрует первым Восток, потом Юг, потом Запад, а последним - сам Север (путь ВЮЗС). Таким образом, узнает истинное значение своей первой карты. А вот ID следующей карты дешифруется в порядке: Север-Запад-Юг-Восток (СЗЮВ). Таким образом, ID "новой верхней" карты знает только Восток. Он повторяет действия Севера в точности, пока у каждого игрока не будет по M карт, причем по секрету от других. И истинный ID "верхней" карты знает теперь только Север.
Взятки
Север выбирает одну из своих карт (
некая тактика пусть заложена, на этом мы не зацикливаемся) и, согласно ее значению (например, 6), повторяет одно и то же действие несколько раз: снимает "верхнюю" карту и читает "запись":
* смотрит зашифрованное значение - дешифрует его в порядке ВЮЗС (так он узнает дешифрованное значение), запоминает себе в руку
если нужное число "взятых" карт (в нашем примере 6) не достигнуто, то:
** Север смотрит зашифрованный ID "следующей", дешифрует его по ВЮЗС, снимает "следующую верхнюю" карту - возврат в начало цикла
если нужное число карт достигнуто:
*** Север запоминает зашифрованный ID "следующей" в отдельную ячейку памяти, далее имитирует дешифровку по ВЮЗС всех последующих карт и ID, так, как будто бы он хочет взять 10 карт (отсылает случайные значения, не запоминая дешифровку, в нашем примере это будет 5 "следующих ID" и 4 карты).
Потом - запомненный выше ID Север отправляет на дешифровку в порядке СЗЮВ. Теперь Север (и только он) знает 6 своих новых карт, Восток (и только он) - ID "верхней карты", и никто, кроме Севера, не знает, что он "снял" именно 6 карт. Секретность соблюдена.
Конечно, игроки, когда будут получать для дешифровки повторяющиеся карты, что-то заподозрят. Но это не страшно.
Если Восток, допустим, получил при первой взятке Севера, значение "8 червей", которое перевел в "туз пик", а потом то же самое случилось на третьей взятке Севера, то он не может наверняка знать, где именно Север имитировал взятку, а где по-настоящему снимал карту. Так что секретность соблюдена. Север не станет попадаться "глупо" и на одной взятке повторять значения, так что секретность соблюдена.
Если на каком-то этапе, взяв "верхнюю" ("следующую верхнюю") карту, игрок обнаруживает, что это - джокер, то он объявляет, что проиграл. В процессе дешифровки никто не должен догадаться, что ему выпадет именно джокер. Именно для этого в перетасованной колоде лежат записи из 3 полей, а не двух - чтобы в каждой взятой карта дешифровка велась дважды и независимо.
Вот как-то так получается. Вроде.