У 2012 році дослідники з лабораторії Ісікава Ватанабе Токійського університету створили робота-руку, який може грати в камінь-ножиці-папір із 100%-ним коефіцієнтом перемоги проти людини. Використовуючи високошвидкісну камеру, робот протягом однієї мілісекунди розпізнає, яку форму створює людська рука, а потім створює відповідну виграшну форму. © Вікіпедія.
Історія з епіграфу чудово демонструє, що до однієї тої самої події можна підходити по-різному. З точки зору алгоритму швидкого розпізнавання жестів достатно різних по фізиології людей — то можна привітати дослідників з успіхом. Якщо подивитися з точки зору справедливості, то тих би самих японських розробників в справедливому селі беззлобно побили б, а робота-руку втопили б у найближчій річці. Бо нечесно. Це так само, коли на Паску хтось хитрий намагається стукатися фарбованим дерев’яним яйцем.
Варто зауважити, що існує інший підхід і навіть змагання алгоритмів для цієї гри. Наприклад, Iocaine Powder, який виграв Перший міжнародний конкурс програмістів RoShamBo у 1999 році, використовує евристично розроблену компіляцію стратегій. Оптимальна стратегія або метастратегія вибирається на основі минулих результатів. Основними стратегіями, які він використовує, є зіставлення історії, частотний аналіз і випадкове вгадування. Його найсильніша стратегія, зіставлення історії, шукає послідовність у минулому, яка збігається з кількома останніми ходами, щоб передбачити наступний хід алгоритму. У частотному аналізі програма просто визначає хід, який найчастіше грають. Випадкова здогадка — це запасний метод, який використовується для запобігання нищівним втратам у разі невдачі інших стратегій.
Чого тільки не дізнаєшся у Вікіпедії! Привіт. Розглянемо задачу, створену за мотивами відомої гри. В старій версії сайту eolymp.com було вказано джерело задачі: 2007 ACM North America - Pacific Northwest, Problem A.
Умова:
Камінь, Ножиці чи Папір?
https://basecamp.eolymp.com/uk/problems/1215
У гру Камінь, Ножиці, Папір грають двоє. Кожен гравець на рахунок три одночасно вибирає один з трьох предметів. Гра триває певну наперед встановлену кількість раундів. Гравець, який виграє більшу частину раундів, оголошується переможцем. За заданою кількістю раундів та їх результатам необхідно визначити переможця.
Наступні правила описують правила перемоги:
- Камінь завжди перемагає Ножиці (Камінь раздавлює Ножиці)
- Ножиці завжди перемагають Папір (Ножиці ріжуть Папір)
- Папір завжди перемагає Камінь (Папір покриває Камінь)
Вхідні дані
Перший рядок містить кількість тестів t (0 < t < 1000). Перший рядок кожного тесту містить кількість раундів n (0 < n < 100), зіграних у гру Камінь, Ножиці, Папір. Кожен з наступних n рядків містить одну з великих літер R (Камінь), P (Папір) або S (Ножиці), пропуск і знову велику літеру R, P чи S. Перша літера позначає вибір першого гравця; друга літера - вибір другого гравця.
Вихідні дані
Для кожного тесту в окремому рядку вивести ім'я переможця (Player 1 чи Player 2). Якщо гра завершується унічию, вивести TIE.
Приклади
Вхідні дані:
3
2
R P
S R
3
P P
R S
S R
1
P R
Відповідь:
Player 2
TIE
Player 1
Пропоную залишити без розгляду питання кількості тестів і раундів. Вкладені цикли це чудово розв’язують і матеріалів в цьому напрямку — море. Давайте розглянемо задачу по суті.
Одна гра — це коли два учасники одночасно викидують фігуру. Це може бути або Камінь (Rock), або папір (Paper) або ножиці (Scissors). Зліва записується буква фігури першого гравця, справа — буква фігури другого.
Пропоную піти простим шляхом. Записати всі можливі варіанти, які можуть випасти:
R R
R P
R S
P P
P R
P S
S R
S P
S S
Вісім варіантів. Чому саме вісім? Всі бачуть формулу? Якщо два учасника і три фігури (R P S), то виходить вісім. Якщо було б тих самих два учасника і чотири фігури, наприклад, RPSF то скільки було б варіантів? Можна виписати на листочку всі можливі і тоді, думаю, ви точно побачите формулу-залежність.
Пропоную вилучити «нічійні» варінти з наших восьми, залишилось шість:
R P
R S
P R
P S
S R
S P
Ділимо ці варінти на дві групи. Нагадаю, що як зветься: камінь (R), папір (P), ножиці (S).
Запишемо ті варіанти, коли виграє перший гравець:
R S
P R
S P
Запишемо ті варіанти, коли виграє другий гравець:
R P
P S
S R
Формулюємо:
Якщо випадає комбінація R S або P R або S P, то додаємо один бал до кількості виграшів першого гравця, якщо випадає комбінація R P або P S або S R, то додаємо один бал до кількості виграшів другого гравця. Коли раунд завершується, аналізуємо кількості виграшів гравців і виводимо відповідне повідомлення, скидуємо лічильники виграшів і починаємо новий раунд.
Для тих, хто готовий писати код, успіхів. Для тих, хто не готовий — варіант кода є тут.
Успіхів!