Тэорыя гульняў: Minimax на C#
Прахалодны вечар сакавіка пагрузіў горад у звычайную цемру. Вулічны шум практычна сышоў на нішто. І толькі лёгкі вясновы дождж рытмічна стукаў у акно старэйшага распрацоўшчыка Васіля. Гукі дажджу прыемна супакойвалі, асабліва пасля нервовага працоўнага дня. Васіль мацней захінуўся ў цёплую коўдру. Сёння ён цвёрда вырашыў легчы спаць крыху раней, і здавалася, усё спрыяла яму ў гэтым пачынанні.
— Тук-тук, тук-тук. Нібыта барабаншчык! Ці не, як быццам хтосьці ў офісе стукае па клавіятуры. Цікава, калі яны зноў адкрыюцца?
Васіль успомніў свой працоўны стол, кухню, кавамашыну, сваіх калегаў: Алекса, Антона, Майка. Майка? Толькі не ён! Васіль паспрабаваў выкінуць думкі з галавы, але нічога не атрымлівалася. Працоўны дзень зноў усплыў перад вачыма: чарговая важная анлайн сустрэча, менеджэр Алекс задае пытанне і … Васіль падскочыў: “Ох ужо гэты Алекс! Не мог ён пачакаць са сваім пытаннем? Я б у гэты раз дакладна абыграў Майка!”
Майк быў старэйшым распрацоўшчыкам з аддзелу фронтэнда і часцяком перасякаўся з Васілём на гэтых важных сустрэчах, а на адной з іх зарадзілася традыцыя — гуляць у крыжыкі-нулікі. Гэта дазваляла не толькі праводзіць час на сустрэчы з карысцю, але і захоўваць сур’ёзны і задумлівы выраз твару, што вызначана адпавядала агульнаму фармату і падабалася менеджэрам.
Васіль ужо меў некалькі паражэнняў запар, таму яму была неабходная перамога. Але нечаканае пытанне парушыла канцэнтрацыю, і ён выканаў прыкрую памылку. “Дзякуй за гульню!” — напісаў Майк, што вядома азначала “як гэта ў чарговы раз прайграць?”. “Табе дзякуй!” — адказаў Васіль, маючы на ўвазе “нічога, я аддзячу цябе ў наступны раз”.
Сон быў канчаткова перабіты. Васіль зразумеў, што да наступнага разу трэба добра падрыхтавацца, і вырашыў напісаць бота-памочніка. План быў просты і прыгожы. Васіль злавесна зарагатаў і прыступіў да працы.
Minimax на прыкладзе крыжыкаў-нулікаў 3х3
Будзем разглядаць гульню з боку першага гульца (які ставіць крыжыкі). Хай за кожную перамогу гулец атрымлівае 1 ачко, за паражэнне -1, а нічыя эквівалента 0. Разгледзім наступную расстаноўку на поле гульні (ходзіць першы гулец). Ніжэй прывядзём розныя развіцця гульні для магчымых хадоў 1 і 2, дзе 1 — ход крыжыкам налева, а 2 — ход крыжыкам уніз (ход крыжыкам направа аналагічны выпадку 1):
Калі другі гулец будзе гуляць аптымальна, то першы гулец прайграе (атрымае -1 ачко) пры хадах 1 або 3, і згуляе ў нічыю (атрымае 0 ачкоў) пры ходзе 2. Таму правільным ходам для першага гульца будзе ход 2. У гэтым і заключаецца ключавая ідэя алгарытму:
Minimax – гэта алгарытм мінімізацыя страт пры развіцці сітуацыі па найгоршаму сцэнарыю (у нашым выпадку – пры аптымальнай гульні саперніка).
Агульны выпадак і рэалізацыя
З поўнай рэалізацыяй алгарытму на C# можна азнаёміцца на GitHub праекта coding-interview. Ніжэй спынімся на самых цікавых момантах. Хай бягучы стан апісваецца наступным наборам параметраў і метадаў:
- Спісам магчымых хадоў для бягучага гульца
GetPossibleMoves; - Параметрам, які сігналізуе, ці з’яўляецца бягучы стан завяршальным (перамога аднаго з гульцоў, альбо нічыя)
IsTerminal; - Бягучым актыўным гульцом
ActivePlayer. Калі стан з’яўляецца завяршальным, то актыўнага гульца не будзе; - А таксама дададзім метады для здзяйснення і адмены ходу
MakeMove / UndoMove.
public interface IState<Player, Move>
where Player: class
where Move: class
{
IList<Move> GetPossibleMoves();
void MakeMove(Move move);
void UndoMove();
bool IsTerminal { get; }
Player? ActivePlayer { get; }
}Паколькі паняцці Player і Move могуць быць унікальнымі для кожнай гульні, мы іх апісваем Generic параметрамі.
Пяройдзем непасрэдна да рэалізацыі алгарытму. Як ужо гаварылася вышэй, мы спрабуем мінімізаваць страты, гэта значыць абраць такі ход, які пры аптымальнай гульні другога гульца прывядзе да найменшых страт. Іншымі словамі, калі мы можам атрымаць ацэнкі для ўсіх магчымых станаў пры здзяйсненні ходу, то мы выбіраем той ход, які дае нам максімальную ацэнку.
Увядзём паняцце ацэначнай функцыі ў кантэксце нашага алгарытму:
Ацэначная функцыя — гэта функцыя, якая для абранага гульца дае ў агульным выпадку прыкладную ацэнку бягучаму стану.
public interface IScoreFunction<State, Player>
{
double Calculate(State state, Player player);
}У прыкладзе, якой апісаны вышэй, мы ўжо давалі базавую паняцце ацэнкі для канчатковых станаў (-1, 0, 1). Прыклад рэалізацыі такой ацэначнай функцыі прадстаўлены ніжэй:
public class MinimaxScoreFunction : IScoreFunction<State, Player>
{
public double Calculate(State state, Player player)
{
if (player == state.Game.FirstPlayer)
{
return CalculateForFirstPlayer(state);
}
else
{
return CalculateForSecondPlayer(state);
}
}
private static double CalculateForFirstPlayer(State state)
{
return state.Game.State switch
{
GameState.FirstPlayerVictory => 1.0,
GameState.SecondPlayerVictory => -1.0,
_ => 0.0
};
}
private static double CalculateForSecondPlayer(MinimaxAdapter state)
{
return state.Game.State switch
{
GameState.FirstPlayerVictory => -1.0,
GameState.SecondPlayerVictory => 1.0,
_ => 0.0
};
}
}Узнікае пытанне: што рабіць для прамежкавых хадоў? Як адзначалася вышэй, ацэначная функцыя дае прыкладныя ацэнкі бягучага стану ў агульным выпадку, другімі словамі — гэта нейкая эўрыстыка. Напрыклад, мы можам меркаваць, што два крыжыка запар для першага гульца лепш, чым адсутнасць такіх і даваць за такую пазіцыю ацэнку 0.5, але, як паказвалася ў прыкладзе вышэй (хады 1 і 3 задавальняюць гэтай умове), такі падыход можа прывесці да паразы.
Гэтую праблему і вырашае алгарытм minimax. Разгледзім якія задачы вырашае гулец (Гулец1) і апанент (Гулец2) падчас свайго ходу з пункту гледжання Гульца1:
Падчас свайго ходу (Гульца1), Гулец1 павінен выбраць такі ход, які прывядзе яго да перамогі, гэта значыць максымізаваць вынік для Гульца1.
Падчас ходу апанента (Гульца2), Гулец2 павінен выбраць такі ход, які прывядзе яго да перамогі. Гэта эквівалентна паразы Гульца1. Гэта значыць з пункту гледжання Гульца1, Гулец2 павінен выбраць такі ход, які мінімізуе вынік для Гульца1.
Рэалізуем гэта ў выглядзе рэкурсіўнай функцыі. Дадзеная функцыя прымае бягучы стан гульца, для якога вылічаецца ацэнка, і вяртае пару — колькаснае значэнне ацэнкі і ход, які неабходна здзейсніць для атрымання гэтай ацэнкі.
(double Score, Move? NextMove) Estimate(State state, Player player)
{
if (state.IsTerminal)
{
return
(
Score: _scoreFunction.Calculate(state, player),
NextMove: null
);
}
var possibleMoves = state.GetPossibleMoves();
var estimations = possibleMoves.Select((move) => {
state.MakeMove(move);
var (score, _) = Estimate(state, player, depth.HasValue ? depth - 1 : null);
state.UndoMove();
return (Score: score, Move: move);
});
var isOpponentTurn = player != state.ActivePlayer;
return isOpponentTurn
? estimations.Aggregate((e1, e2) => e1.Score < e2.Score ? e1 : e2)
: estimations.Aggregate((e1, e2) => e1.Score > e2.Score ? e1 : e2);
}Ацэнка складанасці і аптымізацыі
Так як у залежнасці ад гульні будзе рознае разнастайнасць і колькасць хадоў для кожнага гульца, то ацэнка будзе будавацца на аснове нейкага прыкладу.
Вернемся да крыжыкаў-нулікаў 3х3. Выкажам здагадку, што гульня вядзецца не да перамогі аднаго з гульцоў, а да поўнага запаўнення поля — так будзе прасцей атрымаць ацэнку. Тады ў першага гульца ёсць 9 варыянтаў здзяйснення ходу. У другога гульца застаецца толькі 8. Затым у першага гульца 7. І гэтак далей. Гэта значыць 9! або O (n!) варыянтаў, дзе n – колькасць клетак.
Калі мы разгледзім больш складаны варыянт гульні з вялікім полем (напрыклад, 20х20), дзе трэба сабраць 5 у шэраг крыжыкаў або нулікаў, то, відавочна, што 400! варыянтаў перабору становіцца занадта шмат, таму неабходна ўводзіць нейкія аптымізацыі.
Напрыклад, можна пашырыць нашу ацэначную функцыю для разліку прамежкавых хадоў з дапамогай эўрыстыкі і абмежаваць глыбіню пошуку. Ці адразу адсяваць на этапе перабору найменш выгадныя хады. Але як паказвалася вышэй, паколькі эўрыстыка дае толькі прыкладную ацэнку, то дакладнасць алгарытму стане ніжэй.
(double Score, Move? NextMove) Estimate(State state, Player player, int? depth)
{
if (state.IsTerminal)
{
return
(
Score: _scoreFunction.Calculate(state, player),
NextMove: null
);
}
if (depth.HasValue && depth <= 0)
{
return
(
Score: _scoreFunction.Calculate(state, player),
NextMove: null
);
}
var possibleMoves = state.GetPossibleMoves();
var estimations = possibleMoves.Select((move) => {
state.MakeMove(move);
var (score, _) = Estimate(state, player, depth.HasValue ? depth - 1 : null);
state.UndoMove();
return (Score: score, Move: move);
});
var isOpponentTurn = player != state.ActivePlayer;
return isOpponentTurn
? estimations.Aggregate((e1, e2) => e1.Score < e2.Score ? e1 : e2)
: estimations.Aggregate((e1, e2) => e1.Score > e2.Score ? e1 : e2);
}Існуе таксама падыход, названы альфа-бэта адсячэннем, які дазваляе без памяншэння дакладнасці моцна скараціць колькасць варыянтаў да перабору. Але разгляд дадзенага метаду заслугоўвае ўжо асобнага артыкула.
