Как да направите играта си Tic Tac Toe непобедима с помощта на алгоритъма на minimax

С часове се борех с превъртане по уроци, гледане на видеоклипове и блъсках главата си по бюрото, опитвайки се да изградя непобедима игра Tic Tac Toe с надежден изкуствен интелект. Така че, ако преминавате през подобно пътуване, бих искал да ви запозная с алгоритъма на Minimax.

Подобно на професионален шахматист, този алгоритъм вижда няколко стъпки напред и се поставя в обувките на своя опонент. Продължава да играе напред, докато не достигне терминална подредба на дъската (състояние на терминала), което води до равенство, печалба или загуба. Веднъж в терминално състояние, AI ще определи произволен положителен резултат (+10) за печалба, отрицателен резултат (-10) за загуба или неутрален резултат (0) за равенство.

В същото време алгоритъмът оценява ходовете, които водят до терминално състояние въз основа на оборота на играчите. Той ще избере ход с максимален резултат, когато е ред на AI и ще избере ход с минималния резултат, когато е ред на човека играч. Използвайки тази стратегия, Minimax избягва загубата на човека играч.

Опитайте сами в следващата игра.

Алгоритъмът на Minimax може да бъде най-добре дефиниран като рекурсивна функция, която прави следните неща:

  1. върнете стойност, ако се намери състояние на терминал (+10, 0, -10)
  2. преминете през наличните петна на дъската
  3. извикайте функцията minimax на всяко налично място (рекурсия)
  4. оценка на връщащите се стойности от функционалните повиквания
  5. и върнете най-добрата стойност

Ако сте нови за концепцията за рекурсия, препоръчвам да гледате това видео от CS50 на Харвард.

За да разберете напълно мисловния процес на Minimax, нека го приложим в код и да го видим в действие в следващите два раздела.

Minimax в Code

За този урок ще работите върху състоянието на играта в близък край, което е показано на фигура 2 по-долу. Тъй като minimax оценява всяко състояние на играта (стотици хиляди), състояние в близост до края ви позволява да проследявате по-лесно рекурсивните обаждания на minimax (9).

За следващата фигура, приемете, че AI е X, а човешкият играч е O.

фигура 2 извадка от състоянието на играта

За да работите с дъската Ti Tac Toe по-лесно, трябва да я определите като масив с 9 елемента. Всеки елемент ще има своя индекс като стойност. Това ще ви бъде полезно по-късно. Тъй като горната дъска вече е запълнена с някои X и Y ходове, нека да определим дъската с движенията X и Y, които вече са в нея (origBoard).

var origBoard = ["O", 1, "X", "X", 4, "X", 6, "O", "O"];

След това декларирайте променливите aiPlayer и huPlayer и ги задайте съответно на „X“ и „O“.

Освен това се нуждаете от функция, която търси печеливши комбинации и връща вярно, ако намери такава, и функция, която изброява индексите на наличните петна в дъската.

Сега нека се потопим в добрите части, като определим функцията Minimax с два аргумента newBoard и player. След това трябва да намерите индексите на наличните петна в таблото и да ги зададете на променлива, наречена availSpots.

Също така, трябва да проверите за състоянията на терминала и съответно да върнете стойност. Ако O спечели, трябва да се върнете -10, ако X печели, трябва да се върнете +10. Освен това, ако дължината на наличния масив от точки е нула, това означава, че няма повече място за игра, играта е довела до равенство и трябва да върнете нула.

След това трябва да съберете оценките от всяко от празните места, за да оцените по-късно. Следователно, направете масив, наречен движения и прекарайте през празни места, докато събирате индекса на всеки ход и отбелязвате в обект, наречен ход.

След това задайте номера на индекса на празното място, което беше запазено като число в origBoard, на свойството index на обекта за преместване. По-късно задайте празното място на дъската на текущия плейър и извикайте функцията minimax с друг плейър и току-що променената нова дъска. След това трябва да съхраните обекта, получен от повикването на функцията minimax, което включва свойство за оценка, към свойството за оценка на обекта за преместване.

Ако функцията minimax не намери състояние на терминал, тя продължава рекурсивно да върви ниво на ниво по-дълбоко в играта. Тази рекурсия се случва, докато достигне терминално състояние и върне резултат едно ниво нагоре.

И накрая, Minimax възстановява newBoard до това, което е било преди, и натиска обекта за преместване в масива от движения.

След това алгоритъмът на minimax трябва да оцени най-добрия ход в масива от движения. Той трябва да избере ход с най-висок резултат, когато AI играе, и ход с най-нисък резултат, когато човекът играе. Следователно, ако играчът е aiPlayer, той задава променлива, наречена bestScore на много нисък брой и преминава през масива от движения, ако ходът има по-висок резултат от bestScore, алгоритъмът съхранява този ход. В случай, че има ходове с подобен резултат, ще се съхранява само първият.

Същият процес на оценка се случва, когато играчът е huPlayer, но този път bestScore би бил зададен на висок брой и Minimax търси ход с най-ниския резултат, който да запази.

В края Minimax връща обекта, съхраняван в bestMove.

Това е за функцията minimax. :) можете да намерите горния алгоритъм в github и codepen. Играйте с различни дъски и проверете резултатите в конзолата.

В следващия раздел, нека преминем над кода ред по ред, за да разберем по-добре как се държи функцията minimax, като се има предвид дъската, показана на фигура 2.

Minimax в действие

Използвайки следната фигура, следваме едно след друго извикванията на функциите на алгоритъма (FC).

Забележка: На фигура 3 големите числа представляват всяко обаждане на функция, а нивата се отнасят до колко стъпки преди играта, която алгоритъмът играе.

Фигура 3 Функция Minimax извикване чрез функционално повикване

1.origBoard и aiPlayer се подават към алгоритъма. Алгоритъмът прави списък на трите открити празни места, проверява за състоянията на терминала и преглежда през всяко празно място, започвайки от първото. След това тя променя новатаBoard, като поставя aiPlayer на първото празно място. След това той се обажда с newBoard и huPlayer и чака FC да върне стойност.

2. Докато първият FC все още работи, вторият започва с изготвяне на списък на двете празни места, които намира, проверява за състоянията на терминала и преминава през празното място, започвайки от първото. След това тя променя новатаBoard, като поставя huPlayer на първото празно място. След това той се обажда с newBoard и aiPlayer и чака FC да върне стойност.

3. Накрая алгоритъмът прави списък на празните места и намира печалба за човека играч след проверка за терминални състояния. Следователно той връща обект със свойство за оценка и стойност -10.

Тъй като вторият ФК изброява две празни места, Minimax променя новатаBoard, като поставя huPlayer на второто празно място. След това той се обажда с новата дъска и aiPlayer.

4. Алгоритъмът прави списък на празните места и намира печалба за човека играч след проверка за терминални състояния. Следователно той връща обект със свойство за оценка и стойност -10.

На втория FC алгоритъмът събира стойностите, идващи от по-ниски нива (3-ти и 4-ти FC). Тъй като обратът на huPlayer доведе до двете стойности, алгоритъмът избира най-ниската от двете стойности. Тъй като и двете стойности са сходни, той избира първия и го връща до първия FC.
В този момент първият ФК е оценил резултата от преместването на aiPlayer на първото празно място. На следващо място, тя променя новатаBoard, като поставя aiPlayer на второто празно място. Тогава той се обажда с новияBoard и huPlayer.

5. На петия FC Алгоритъмът прави списък на празните места и намира печалба за човека играч след проверка за терминални състояния. Следователно той връща обект със свойство за оценка и стойност +10.

След това, първият FC преминава, като сменя новатаBoard и поставя aiPlayer на третото празно място. След това, той се обажда с новата дъска и huPlayer.

6. Шестият ФК започва със съставяне на списък от две празни места, които намира, проверява за терминални състояния и преглежда през двете празни точки, започвайки от първото. След това тя променя новатаBoard, като поставя huPlayer на първото празно място. След това той се обажда с newBoard и aiPlayer и чака FC да върне резултат.

7. Сега алгоритъмът е на две нива дълбоко в рекурсията. Той прави списък на едното празно място, което намира, проверява за състоянията на терминала и променя новата табло, като поставя aiPlayer на празното място. След това той се обажда с newBoard и huPlayer и чака FC да върне резултат, за да може да го оцени.

8. На 8-ми FC алгоритъмът прави празен списък от празни петна и намира печалба за aiPlayer след проверка за терминални състояния. Следователно, той връща обект с оценка свойство и стойност от +10 едно ниво нагоре (7-мо FC).

Седмият ФК получи само една положителна стойност от по-ниски нива (8-ми ФК). Тъй като обратът на aiPlayer доведе до тази стойност, алгоритъмът трябва да върне най-високата стойност, която е получил от по-ниски нива. Следователно тя връща единствената си положителна стойност (+10) с едно ниво нагоре (6-то FC).
Тъй като 6-ият ФК изброи две празни места, Minimax сменя newBoard, като поставя huPlayer на второто празно място. След това се обажда с новата дъска и aiPlayer.

9. След това алгоритъмът прави списък на празните точки и намира печалба за aiPlayer след проверка за терминални състояния. Следователно той връща обект с оценка на свойства и стойност от +10.

В този момент 6-те FC трябва да избират между резултата (+10), изпратен от 7-ия FC (върнат първоначално от 8-ия FC) и резултата (-10), върнат от 9-ия FC. Тъй като обратът на huPlayer доведе до тези две върнати стойности, алгоритъмът намира минималния резултат (-10) и го връща нагоре като обект, съдържащ свойства на показатели и индекси.
Накрая и трите клона на първия ФК са оценени (-10, +10, -10). Но тъй като обратът на aiPlayer доведе до тези стойности, алгоритъмът връща обект, съдържащ най-високата оценка (+10) и неговия индекс (4).

В горния сценарий Minimax заключава, че придвижването на X до средата на дъската води до най-добрия резултат. :)

Край!

До този момент вече бихте могли да разберете логиката зад алгоритъма Minimax. Използвайки тази логика, опитайте сами да внедрите алгоритъм на Minimax или да намерите горната извадка в github или codepen и да я оптимизирате.

Благодаря за четенето! Ако тази история ви е харесала, моля, препоръчайте я, като щракнете върху бутона ❤ отстрани и я споделите в социалните медии.

Специални благодарности на Tuba Yilmaz, Rick McGavin и Javid Askerov за прегледа на тази статия.