Optimizing decision-making with the Minimax AI algorithm

movesList.

push({ player: player, targetX: r, targetY: c }) } } } return movesList;}2.

The heuristic function (a little homework for you)function heuristic(board) { // search all three rows – is any one filled by only one player // search all three columns – is any one filled by one player // search the two diagonals – is any one filled by one player // if any row, column, or diagonal is filled solely by one // player – then return 100 if O and -100 if X.

// otherwise, always return 0.

}3.

Defining the maximizer/minimizerfunction maximizer(board, depth) {}function minimizer(board, depth) {}// we'll implement them shortly4.

Evaluatorconst depthLimit = 3;// search upto three moves aheadfunction eval(board, player, depth=0) { // depth is 0 initially if (depth >= depthLimit) return heuristic(board); if (player === 'X') return maximizer(board, depth); else return minimizer(board, depth);}5.

Implementing the maximizer/minimizerfunction copyBoard(board) {// simple helper function let copy = new Array(3); copy[0] = [board[0][0], board[0][1], board[0][2]]; copy[1] = [board[1][0], board[1][1], board[1][2]]; copy[2] = [board[2][0], board[2][1], board[2][2]]; return copy;}function applyMove(board, move) {// simple helper function board[move.

targetX][move.

targetY] = move.

player; return board;}var bestMoveStore;// will be set when best move is found @depth=0function maximizer(board, depth) { let movesList = getAllMoves('O', board); let bestMove, bestMoveScore = Number.

NEGATIVE_INFINITY; // -INFINITY because first move will always be more for (let i = 0; i < movesList.

length; i++) { let movedBoard = applyMove(copyBoard(board), movesList[i]); let moveScore = eval(movedBoard, 'X', depth+1); if (moveScore >= bestMoveScore) { bestMove = movesList[i]; bestMoveScore = moveScore; } } if (depth === 0) bestMoveStore = bestMove;}// Similary minimizer can be implemented, just you find the// bestMoveScore as the least value instead of the max.

function minimizer(board, depth) { let movesList = getAllMoves('O', board); let bestMove, bestMoveScore = Number.

POSITIVE_INFINITY; // +INFINITY because the first score will always be less for (let i = 0; i < movesList.

length; i++) { let movedBoard = applyMove(copyBoard(board), movesList[i]); let moveScore = eval(movedBoard, 'X', depth+1); if (moveScore >= bestMoveScore) { bestMove = movesList[i]; bestMoveScore = moveScore; } } if (depth === 0) bestMoveStore = bestMove;}5.

WrapperWe need an API wrapper that will return the variable bestMoveStore to the client code/UI that actually needs the computer’s result.

This method needs to call eval with depth zero which will eventually call maximizer or minimizer.

export function analyzeAndMoveAsComputer(board, player) { eval(board, player, 0); return bestMoveStore;}I hope this “code-based” review of the algorithm clear stuff up a little.

Where’s the tree of possible moves?The code above doesn’t construct a tree of possible moves and their results.

It uses recursion and checks each case/path-of-moves one-by-one without saving them.

It only retains the best-possible move at each level.

This saves a lot of memory-usage but fails to account for the efficiency of CPU computation.

Known optimizations to the Minimax algorithmNegamaxIn the algorithm’s basic implementation the maximizer/minimizer function essentially does the same thing — find the move with the best score — except look in the opposite directions.

The negamax optimization does away with this and combines the three functions — eval , maximizer , and minimizer — into one function, which can be combined into one API wrapper function (doing away with a separate wrapper too!)The code will look something like this:function dir(player) { return (player === 'O')?.+1 : -1;}function analyzeAndMoveAsComputer(board, player, depth=0) { // NOTE: depth=0 means that depth is an optional arg for // the client.

It is meant only for internal use and not // for the caller.

if (depth === depthLimit) { return heuristic(board) * dir(player);// always positive } let movesList = getAllMoves(player, board); let bestMove, bestMoveScore = Number.

NEGATIVE_INFINITY; for (let i = 0; i < movesList.

length; i++) { let movedBoard = applyMove(copyBoard(board), movesList[i]); let moveScore = analyzeAndMoveAsComputer(board, // opp.

player (player === 'O') ? 'X' : 'O'); // everything is almost same till here!.moveScore *= -1;// moveScore is for opponent!.if (bestScore > bestMoveScore) { bestMove = movesList[i]; bestMoveScore = bestScore; } } if (depth === 0) return bestMove;// for actual caller else return bestMoveScore;}It is hard to wrap your head around the clever usage of -1 by multiplying it with the score every time.

This causes the score to always to be alternating signs up the moves tree.

This algorithm relies on the fact that max(a,b) = −min(− a,−b) to simplify the implementation of the minimax algorithm — WikipediaAlpha-beta pruningThis algorithm keeps two values alpha and beta.

Alpha is the minimum value the “maximizer” or first-player is assured of.

Beta is the maximum value that the “minimizer” or second-player is assured of.

The meaning of these values can be explained as: in ideal play, the played moves will be such that the score is greater than alpha and less than beta.

While searching, if beta becomes greater than alpha (hence, the ideal play doesn’t exist), that means the opposing player won’t make one of the moves being searched (unless a mistake is made), hence it doesn’t have to be searched.

Jez9999 at English Wikipedia: https://commons.

wikimedia.

org/wiki/File:AB_pruning.

svgThe diagram above shows which moves can be discarded from consideration.

The boxes represent the board when it’s the maximizer’s turn.

He wants the score to increase.

The circles represent the board when it’s the minimizer’s turn.

He wants the score to decrease.

For example, in the right-most part, look where the sub-tree 8 is discarded.

This is because the minimizer can make a move with a lower score of 5 till the depth-limit, and will because it’s a better move.

Less implemented optimizationsVariable search depthI’ve implemented this in my Android app — Surakarta.

You can implement variable search depth by keeping more than one depth (and corresponding depth-limits).

I used two depths in my game — absolute search-depth and adjusted search-depth.

The absolute search-depth is the “real” depth at which we are and has a higher limit.

The adjusted search-depth has a lower limit.

However, instead of incrementing the depth at every level, it may remain constant if an important change occurs in the move — like a capture.

Capturing moves are given more attention.

The high limit on the absolute search-depth still stops the program from taking a ridiculous amount of time to complete.

Transposition tablesWhen I play chess, and my opponent plays the move I anticipated while making my move, I don’t have to think a lot.

I’ve already done the research on the arising position, right!However, the computer algorithm starts over.

A transposition table solves this problem by the storing moves in a tree structure.

If the move that the player was already searched through, then the sub-tree could be extracted.

Then the leaf-nodes could be extended through.

Something I’d like to add in the algorithm one day!I think a level concurrency would immensely reduce the computation time!.Just as multiple threads can simultaneously divide-and-conquer sorting & searching algorithms and then merge the results — multiple worker threads should be able also to build the search-tree simultaneously.

I’ll write another article once I implement this feature for sure.

Please stay tuned till then!!!The Minimax is primarly used in chess engines like Stockfish!.It can be used in almost any two-player board game!Further reading:A full overview of the HTML CanvasHow non-integer values are stored in a float (and why it floats)Removing circular dependencies in JavaScriptHow to synchronize your app across multiple devices (Android)How to use Firebase for building multiplayer Android gamesFollow me on Twitter for more CS-related fun stuff!Shukant Kumar Pal (@ShukantP) | TwitterThe latest Tweets from Shukant Kumar Pal (@ShukantP).

OSS High Schoolertwitter.

com.. More details

Leave a Reply