1.1: Гравці та стратегії

Last updated
Save as PDF

Page ID: 65714

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)

У цій книзі більшу частину ігор зіграють двоє гравців. Кожен гравець повинен вирішити, як він або вона буде грати в гру. Для того, щоб вивчати ігри математично, нам потрібно зробити деякі припущення про те, як гравці повинні грати в гру. Це дозволяє нам краще передбачити, що повинні робити наші гравці. Наступний приклад ілюструє характеристики, які ми будемо вважати щодо наших гравців.

1.1.1: Приклад - поділ тортів

Як двоє дітей можуть неабияк розділити торт? Одне класичне рішення полягає в тому, щоб одна дитина розрізала торт, а інша дитина вибрати шматок.

Чому це працює? Іншими словами, чому обидва діти повинні відчувати, що вони отримали неабияку частку торта?

Які основні припущення змушують цей процес працювати?

Мета кожного гравця - отримати найбільшу фігуру. Ми можемо думати про це як про кожного гравця, який діє в своїх інтересах.
Обидва гравці знають, що інший гравець має ту ж мету, і будуть діяти для досягнення цієї мети. Таким чином, ми знаємо, що кожен гравець раціональний. Навіть більше, кожен гравець знає, що інший гравець раціональний.

Нам потрібно як (1), так і (2), щоб досягти розчину, щоб торт розділився рівномірно, і обидві діти отримують однакові за розміром шматочки.

Ідея про те, що гравці зацікавлені в собі, має вирішальне значення для теорії ігор. Є багато інших способів грати в ігри, і їх, можливо, варто вивчити. Але щоб почати роботу з теорією ігор, ми повинні зробити конкретні припущення і розробити математичний контекст з цих припущень.

Припущення 1: Гравці зацікавлені в собі. Мета полягає в тому, щоб виграти найбільше або програти найменше. Але що значить перемогти?

Виплата гравця - це сума (очки, гроші або щось, що цінує гравець), яку гравець отримує за певний результат гри. Ми говоримо, що мета гравця - максимізувати його або її виграш. Слід зазначити, що максимальний виграш для гравця може бути навіть негативним, і в цьому випадку гравець хоче найменш негативного (або найближчого до\(0\)) виграшу.

Важливо визнати різницю між тим, щоб мати мету максимізувати виграш і мати мету просто перемогти. Ось кілька прикладів.

Якби два гравці були в гонках, гравець не просто хотів би фінішувати першим, вона хотіла б закінчити з якомога більшим відривом.
Якби дві команди грали в баскетбол, команда не хотіла б просто мати більш високий бал, вони хотіли б виграти найбільшу кількість очок. Іншими словами, команда вважала за краще вигравати\(10\) очками, а не\(1\) очками.
У виборчому опитуванні кандидат не просто хоче випередити свого опонента, вона хоче вести якомога більший запас (особливо якщо їй потрібно враховувати помилки в опитуваннях).

Важливо пам'ятати, що мета кожного гравця - виграти найбільше (або програти найменше). Буде спокусливо шукати стратегії, які просто запевняють гравця в позитивному виграші, але ми повинні переконатися, що гравець не може зробити ще краще з іншою стратегією.

Припущення 2: Гравці цілком логічні. Гравець завжди врахує всю наявну інформацію і прийме рішення, яке максимізує його виграш. Це включає в себе знання того, що його опонент також приймає найкраще рішення для себе. Наприклад, у грі різання торта гравець не вирізав би один великий шматок, сподіваючись, що його опонент випадково забере менший шматок. Гравець повинен припустити, що її суперник завжди вибирає більшу фігуру.

Тепер вам може бути цікаво, що ці припущення мають відношення до реальності. Адже ніхто не ідеальний. Але ми часто вивчаємо ідеальні ситуації (особливо в математиці!). Наприклад, ви всі вивчили геометрію. Чи може хтось тут намалювати ідеально пряму лінію? Тим не менш, ви всі вивчили такий об'єкт!

Наша мета: Розробити стратегії для наших абсолютно логічних, зацікавлених в собі гравців.

1.1.2: Розвиваючі стратегії: Tic Tac Toe

Вправа Template:index: Грати в гру.

Грайте в кілька ігор Tic Tac Toe з суперником. Переконайтеся, що ви по черзі є першим гравцем і другим гравцем. Розробіть стратегію перемоги в Tic Tac Toe. У вас може бути інша стратегія для першого гравця і для другого гравця. Будьте максимально конкретними. Можливо, вам доведеться розглянути кілька можливостей, які залежать від того, що робить ваш опонент.

Хто виграє? Гравець 1 або гравець 2?
Що повинен зробити кожен гравець, щоб мати найкращий можливий результат?
Як ви розробили свою стратегію?
Звідки ви знаєте, що це завжди буде працювати?

Відзначимо деякі характеристики Tic Tac Toe.

Є два гравці.
Гравці мають досконалу інформацію. Це означає, що кожен гравець знає, що всі його або її власні варіанти, які всі варіанти його або її суперника, і обидва гравці знають, який результат кожного варіанту. Крім того, гравці знають, що обидва гравці мають всю цю інформацію.
У цій грі є рішення. Рішення для гри складається з стратегії для кожного гравця та результату гри, коли кожен гравець грає свою стратегію. У Tic Tac Toe, якщо обидва гравці грають якнайкраще, гра завжди закінчиться нічиєю.
Гра кінцева. Це означає, що гра повинна закінчитися після кінцевої кількості ходів ходів ходів. Іншими словами, гра не може тривати вічно. Гра, яка не є кінцевою, називається нескінченною. Зверніть увагу, нескінченна гра може закінчитися після кінцевої кількості ходів, але немає максимальної кількості ходів або процесу, щоб забезпечити закінчення гри. У Tic Tac Toe гра повинна закінчитися після\(9\) або менше поворотів.

Вправа Template:index: Ідеальна інформація, більше прикладів.

Чи можете ви придумати ще один приклад гри з ідеальною інформацією? Що є прикладом гри, яка не має досконалої інформації?

Вправа Template:index: скінченне і нескінченне, більше прикладів.

Наведіть кілька прикладів кінцевих ігор і нескінченних ігор.

Визначення: Стратегія

Стратегія для гравця - це повний спосіб грати в гру незалежно від того, що робить інший гравець.

Вибір того, що робить гравець, може залежати від суперника, але цей вибір заздалегідь визначається перед геймплеєм. Наприклад, у грі на різання торта не має значення, який шматок «вибирає», «різак» завжди буде різати рівномірно. Аналогічно, не має значення, як різак ріже, вибирач завжди підбере найбільший шматок. У Tic Tac Toe стратегія гравця 2 повинна визначати його перший хід незалежно від того, який гравець 1 грає першим. Наприклад, якщо гравець 1 грає центральну площу, де гравець 2 повинен грати? Якщо гравець 1 грає кутовий, де гравець 2 повинен грати?

Вправа Template:index: Опишіть улюблену гру

Яка ваша улюблена гра?

Дайте короткий опис гри, в тому числі, що означає «виграти» або «програти» гру.
Скільки гравців вам потрібно?
Чи мають гравці ідеальну інформацію для гри?
Гра кінцева або вона може тривати назавжди?
Дайте деякі можливі стратегії для гравця (ів). Зверніть увагу, що в залежності від гри, ці стратегії не завжди можуть призвести до певного виграшу, але вони повинні запропонувати спосіб збільшити шанси гравця на виграш (або не програти).

Ми встановили кілька припущень і розглянули, як описувати стратегії в деяких знайомих іграх. Не всі ігри легко вписуються в контекст, який ми будемо використовувати протягом усього цього тексту. Але ви можете мати на увазі деякі з ваших улюблених ігор і побачити, наскільки добре стратегії та рішення можуть бути застосовані до них. У наступному розділі ми розробляємо кілька корисних позначень для опису більшості ігор, які ми будемо вивчати.