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

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

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

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

Опитайте сами в следващата игра, за предпочитане с помощта на браузър Chrom.

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

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

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

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

Минимакс в кода

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

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

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

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

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

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

/* the original board O | | X --------- X | | X --------- | O | O */ var origBoard = [“O”,1 ,”X”,”X”,4 ,”X”, 6 ,”O”,”O”]; // human var huPlayer = “O”; // ai var aiPlayer = “X”; // returns list of the indexes of empty spots on the board function emptyIndexies(board){ return board.filter(s => s != "O" && s != "X"); } // winning combinations using the board indexies function winning(board, player){ if ( (board[0] == player && board[1] == player && board[2] == player) || (board[3] == player && board[4] == player && board[5] == player) || (board[6] == player && board[7] == player && board[8] == player) || (board[0] == player && board[3] == player && board[6] == player) || (board[1] == player && board[4] == player && board[7] == player) || (board[2] == player && board[5] == player && board[8] == player) || (board[0] == player && board[4] == player && board[8] == player) || (board[2] == player && board[4] == player && board[6] == player) ) { return true; } else { return false; } }

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

// the main minimax function function minimax(newBoard, player){ //available spots var availSpots = emptyIndexies(newBoard);

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

 // checks for the terminal states such as win, lose, and tie //and returning a value accordingly if (winning(newBoard, huPlayer)){ return {score:-10}; } else if (winning(newBoard, aiPlayer)){ return {score:10}; } else if (availSpots.length === 0){ return {score:0}; }

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

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

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

И накрая, Минимакс нулира newBoard на това, което е било преди и избутва ход обект на ходове масив.

// an array to collect all the objects var moves = []; // loop through available spots for (var i = 0; i < availSpots.length; i++){ //create an object for each and store the index of that spot var move = {}; move.index = newBoard[availSpots[i]]; // set the empty spot to the current player newBoard[availSpots[i]] = player; /*collect the score resulted from calling minimax on the opponent of the current player*/ if (player == aiPlayer){ var result = minimax(newBoard, huPlayer); move.score = result.score; } else{ var result = minimax(newBoard, aiPlayer); move.score = result.score; } // reset the spot to empty newBoard[availSpots[i]] = move.index; // push the object to the array moves.push(move); }

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

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

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

// if it is the computer's turn loop over the moves and choose the move with the highest score var bestMove; if(player === aiPlayer){ var bestScore = -10000; for(var i = 0; i  bestScore){ bestScore = moves[i].score; bestMove = i; } } }else{ // else loop over the moves and choose the move with the lowest score var bestScore = 10000; for(var i = 0; i < moves.length; i++){ if(moves[i].score < bestScore){ bestScore = moves[i].score; bestMove = i; } } } // return the chosen move (object) from the moves array return moves[bestMove]; }
Това е за функцията minimax. :) можете да намерите горния алгоритъм на github и codepen. Поиграйте с различни дъски и проверете резултатите в конзолата.

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

Minimax в действие

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

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

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

2. While the first FC is still running, the second one starts by making a list of the two empty spots it finds, checks for terminal states, and loops through the empty spot starting from the first one. Then, it changes the newBoard by placing the huPlayer in the first empty spot.After thatit calls itself with newBoard and the aiPlayer and waits for the FC to return a value.

3. Finally the algorithm makes a list of the empty spots, and finds a win for the human player after checking for terminal states. Therefore, it returns an object with a score property and value of -10.

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

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

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

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

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

6. Шестият FC започва, като прави списък с две празни места, които намира, проверява за състояния на терминала и прелиства през двете празни места, започвайки от първото. След това променя newBoard, като поставя huPlayer на първото празно място.След това,it calls itself with newBoard and the aiPlayer and waits for the FC to return a score.

7. Now the algorithm is two level deep into the recursion. It makes a list of the one empty spot it finds, checks for terminal states, and changes the newBoard by placing the aiPlayer in the empty spot.After that,it calls itself with newBoard and the huPlayer and waits for the FC to return a score so it can evaluate it.

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

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

9. Next, the algorithm makes a list of the empty spots, and finds a win for the aiPlayer after checking for terminal states. Therefore, it returns an object with score properties and value of +10.

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

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

Край!

By now you should be able to understand the logic behind the Minimax algorithm. Using this logic try to implement a Minimax algorithm yourself or find the above sample ongithub or codepen and optimize it.

Thanks for reading! If you liked this story, don't forget to share it on social media.

Special thanks to Tuba Yilmaz, Rick McGavin, and Javid Askerovfor reviewing this article.