Як вигравати в грі камінь-ножиці-папір? (Реалізація оптимальної стратегії в Wolfram Mathematica)

       
 
 Переклад поста Джона Маклуна (Jon Mcloone, директор департаменту міжнародного бізнесу та стратегічного розвитку Wolfram Research). Оригінал посту: How to Win at Rock-Paper-Scissors
 Завантажити пост у вигляді документа Mathematica
 
З точки зору математики гра камінь-ножиці-папір (див. Додаток 1 в кінці) не є особливо цікавою. Стратегія рівноваги Неша дуже проста: випадково і з однаковою ймовірністю вибирайте з трьох варіантів, і за умови проведення великого числа ігор ні ви, ні ваш суперник не зможете здобути перемогу. Хоча, при обраховування стратегії за допомогою комп'ютера все ще можливо виграти у людини після великого числа ігор.
 
Моя дев'ятирічна дочка показала мені програму, створене нею за допомогою Scratch, яка вигравала абсолютно кожен раз просто відстежуючи, який вибір зробили ви, перед тим, як зробити свій! Але я познайомлю вас з простим рішенням, яке виграє у людини в камінь-ножиці-папір без обману.
 
 
 
Оскільки того, хто завжди робить абсолютно випадковий вибір перемогти неможливо, ми будемо розраховувати на те, що люди не дуже-то й випадкові. Якщо комп'ютер зможе помітити якийсь шаблон, по якому ви дієте у своїх спробах бути випадковим, він стане на крок ближче до того, щоб передбачити ваші майбутні дії.
 
Я думав про створення алгоритму в якості однієї з тем нашого курсу статистики в рамках концепції Computer-Based Math ™. Але перша ж стаття, на яку я наткнувся в пошуках Предсказательная алгоритмів, розглядала рішення за допомогою складної конструкції на основі копули-розподілів. Це рішення було важким для розуміння школяра (а можливо, і для мене), тому я вирішив розробити більш просте рішення, яке я міг би пояснити простими словами. І нехай навіть воно вже й було розроблено раніше, набагато веселіше створювати речі по-своєму, ніж знаходити їх готову реалізацію.
 
Для початку нам необхідно просто мати можливість почати гру. На той момент вже була розроблена і доступна демонстрація , що дозволяє грати в камінь-ножиці-папір, але це було не зовсім те, що мені потрібно, тому я написав свою версію. Цей пункт не вимагає особливих пояснень:
 
 In [1]: =
 
 
 
 Out [1] =
 
 
 
Здебільшого цей код описує користувальницький інтерфейс і правила гри. Вся стратегія комп'ютерного гравця міститься в цій функції:
 
 In [2]: =
 
 
 
де 1 відповідає каменю, 2 — папері і 3 — ножицям. Це оптимальне рішення. Як би ви не грали, ви виграєте стільки ж ігор, скільки і комп'ютер, і ваш показник перемог буде коливатися в районі нуля.
 
Отже, тепер було б цікаво переписати функцію chooseGo щоб здійснювати передбачення стосовно вашого вибору, використовуючи дані про останніх іграх, що зберігаються у змінній history . Першим кроком буде аналіз скоєних протягом останніх декількох ігор виборів і пошук всіх випадків входження якої послідовності. Спостерігаючи за тим, що людина робила в кожній наступній грі, ми можемо виявити якийсь шаблон поведінки.
 
 In [3]: =
 
 
 
Перший аргумент функції являє собою історію минулих ігор. Наприклад, в наборі даних, представлених нижче, комп'ютер (друга колонка — другий елемент кожного подсписка) щойно зіграв папір (їй відповідає число 2) проти каменю, зіграного людиною (число 1). Це видно по останньому елементу списку. Також видно, що така ситуація вже виникала двічі, і обидва рази наступним ходом людини був знову камінь.
 
 In [4]: ​​=
 
 
 
 Out [4] =
 
 
 
Другий аргумент це кількість останніх елементів історії, по яких і буде вестися пошук. У даному випадку в якості аргументу функції передано число 1, що здійснює пошук в даних лише випадків входження {1,2}. Якщо ми виберемо 2, то функція буде шукати входження послідовності {3,2}, {1,2} і поверне порожній список, оскільки така послідовність раніше не зустрічалася.
 
Третій аргумент, All , вказує на те, що в шуканих послідовностях повинні збігатися і ходи людини, і ходи комп'ютера. Аргумент можна змінити на 1, щоб дивитися тільки на історію ходів людини (тобто припускаючи, що людський вибір залежить тільки від його ж попередніх ходів), або 2, щоб звертати уваги тільки на другий стовпець, тобто на історію ходів комп'ютера (тобто припускаючи, що людина відповідає на попередні ходи комп'ютера незалежно від того, які сам здійснював ходи і, отже, незалежно від того, виграв він чи програв).
 
Наприклад, в даному випадку ми знаходимо, що людина вибирав після каменю, незалежно від того, що в тих же іграх вибирав комп'ютер.
 
 In [5]: =
 
 
 
 Out [5] =
 
 
 
Маючи велику кількість даних, ми можемо обійтися тільки аргументом All , і програма зможе сама вирішити, чиї ходи, комп'ютера або людини, більш важливі. Наприклад, якщо історія ходів комп'ютера ігнорується людиною в ході здійснення вибору, тоді набір даних, отриманий для якої-небудь історії ходів комп'ютера матиме той же розподіл, що і для будь-якої іншої історії ходів комп'ютера, за умови, що даних про попередніх іграх достатньо. Здійснюючи пошук по всіх парах ігор, отримаємо той же результат, як і якби ми спочатку вибирали дані з історії ходів комп'ютера, а потім використовували це підмножина для показаної вище функції. Те ж станеться у випадку, якщо має значення тільки історія ходів комп'ютера. Але при цьому, виробляючи пошук при обліку обох цих припущень окремо можна отримати більш вірні збіги в історії, і найбільше це проявляється у випадках, коли набір даних про ігри спочатку малий.
 
Таким чином з цих двох перевірок ми можемо виявити, що перший дає оцінку в 100%, що наступним вибором людини буде камінь, а другий показує, що з 75% ймовірністю людина вибере камінь і з 25% ймовірністю — ножиці.
 
І тут я кілька застопорився у вирішенні завдання.
 
У даному випадку два передбачення по украй мірі більш менш близькі по результату, хоча і розходяться в численних значних ймовірностей. Але якщо ви проводите пошук по трьох «зрізах» даних c рядом різних довжин історії, і результати пророкувань суперечливі — як їх об'єднати?
 
Я помістив замітку про цю проблему в папку «Написати про це в блог» і забув про неї до тих пір, поки кілька тижнів назад не відбулася суперечка про те, як висвітлити концепцію " статистичної значущості " в курсі Computer-Based Math ™.
 
Я зрозумів, що питання полягає не в тому, як скомбінувати отримані передбачення, а в тому, як визначити, яке з пророкувань найбільш значуще. Одне з пророцтв могло б бути більш значущим, ніж інші, оскільки воно відображає більш виражену тенденцію або, може бути, засноване на більшому наборі даних. Це було неважливо для мене, і тому я просто використав p-значення тесту на значимість (з нульовою гіпотезою про те, що обидва гравці грають випадково), щоб упорядкувати отримані передбачення.
 
Думаю, мені слід було б прислухатися до нашого ж першому принципу про те, що першим кроком у вирішенні будь-якої математичної проблеми є "правильна постановка питання".
 
In [6]: =
 
 
 
Тепер, якщо ми візьмемо останній отриманий нами результат, виявляється, що найкраще пророкування — камінь, що має p-значення 0.17. Це означає, що лише з імовірністю 0.17, дані, які використовуються для даного передбачення, відхиляються від дискретного рівномірного розподілу (DiscreteUniformDistribution [{1,3}] ), причому скоріше випадково, ніж через систематичної помилки, виробленої людському або з якої -чи іншої причини, яка могла змінити розподіл.
 
 In [7]: =
 
 
 
 Out [7] =
 
 
 
Чим менше це p-значення, тим більш впевненими ми можемо бути в тому, що знайшли справжній шаблон поведінки. Так що ми просто здійснюємо передбачення для різних довжин історії та зрізів даних і вибираємо пророкування з найменшим p-значенням.
 
 In [8]: =
 
 
 
І робимо такий вибір, який поб'є вибір людини.
 
 In [10]: =
 
 
 
Тут ви бачите результат. Ви можете скачати і самостійно випробувати його з сайту Wolfram Demonstrations.
 
 In [11]: =
 
 
 
 Out [11] =
 
 
 
Коли програма має занадто мало даних, вона грає випадково, так що починаєте ви на рівних. Спочатку, коли вона тільки починає навчатися, вона приймає кілька дурні рішення, тому ви можете вирватися вперед. Але після 30-40 ігор вона починає отримувати дійсно значущі передбачення, і ви побачите, як ваш показник перемог опуститься в негативну область і так там і залишиться.
 
Звичайно, таке рішення добре тільки проти примітивних спроб здаватися випадковим. Його передбачуваність робить його схильним можливого програшу проти добре прорахованою і наміченої стратегії. Вкрай цікаво спробувати перемогти цю програму за допомогою інтуїції. Це можливо, але якщо ви перестанете думати або будете думати дуже старанно, ви скоро відстанете. Звичайно, програма могла б з легкістю це зробити, застосовуючи той же алгоритм з метою передбачити наступний хід цієї програми.
 
Такий підхід веде до початку якоїсь «гонки озброєнь», змагань з написання алгоритмів, які будуть вигравати в камінь-ножиці-папір у алгоритму суперника, і єдиний спосіб припинити це — повернутися до стратегії рівноваги Неша, здійснюючи вибір через RandomInteger [{1, 3}] .
 
 Доповнення 1
У тому випадку, якщо ви не знаєте, як грати в цю гру, правила такі: ви вибираєте камінь, ножиці або папір, використовуючи один з трьох жестів, показаних одночасно вами і вашим суперником. Камінь перемагає ножиці (робить їх тупими), ножиці перемагають папір (вони її ріжуть), а папір перемагає камінь (вона його загортає). Переміг отримує одне очко, у разі нічиєї обидва гравці не отримують очок.
 
 Дякую Сергія Шевчука за допомогу, надану в перекладі даного поста.
  
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.