recursionstackminimaxstructured-text

How to use minimax alalgorithm without recursion?


I'm developing a program that people can play "tic tac toe" with a computer. I choose structured text as my develop language, but it doesn't have recursion, so I have to develop it without recursion. As the result, I decide to use the stack to instead, but I don't know how to change recursion into the stack.

I try to use stack like BFS, and also I wanna that minimax can make the best move.


Solution

  • I don't know Structured Text, but maybe it helps to see a solution in another language.

    You need a stack with moves, so that when backtracking, you know from where to start to search for a next, alternative move for it.

    You also need a stack of scores, so you know the best score so far at every depth of the minimax search tree.

    The two stacks could be combined into one stack when you can store the two data in one structure to be placed on the single stack. But in the below implementation in JavaScript I have tried to keep the data structures as simple as possible and used two stacks (fix-sized arrays with a separate size variable). All variables are declared at the top of the functions (as in Structured Text), and return statements are always at the end of the function bodies (since there is no return statement in Structured Text).

    function gameWon(board) {
        /* Looks at all possible lines of 3,
         * to see if they are occupied by three of the same symbols
         * board: is a 1D array with 9 integers: 
         * 1 = "X" (first player), 0 = free, 1 = "O"
         * Returns boolean.
         */
        let value;
        let i;
        // In Structured Text you'd not have gameWonReturn, 
        //    as you would use `gameWon` instead for returning a value
        let gameWonReturn = false; 
        
        for (i = 0; i < 3; i++) {
            value = board[i*3];
            if (value != 0 && value == board[i*3+1] && value == board[i*3+2]) {
                gameWonReturn = true;
                break;
            }
            value = board[i];
            if (value != 0 && value == board[i+3] && value == board[i+6]) {
                gameWonReturn = true;
                break;
            }
            if (value != 0 && value == board[4] && value == board[8-i]) {
                gameWonReturn = true;
                break;
            }
        }
        return gameWonReturn;
    }
    
    function play(board, moveStack, moveCount, move) {
        let playReturn;
        
        // Derive played symbol from number of moves played
        board[move] = 1 - (moveCount % 2) * 2; // Use MOD operator. Result is 1 or -1
        moveStack[moveCount] = move; // Log move in stack
        playReturn = moveCount + 1;
        return playReturn;
    }
    
    function minimax(board, moveStack, moveCount) {
        const scoreStack = Array(10); // Array of signed integers
        const originalMoveCount = moveCount;
        let move;          // -1..9
        let score;         // -10..10
        let player;        // -1 or 1
        let minimaxReturn = -1; // -1..9
    
        while (true) {
            // Current player can be derived from the number of moves that were played
            player = 1 - (moveCount % 2) * 2; // 1 = First, maximizing player. -1 = Second, minimizing player
            // Check for game-over
            if (gameWon(board)) { // Preceding move resulted in win for previous player
                scoreStack[moveCount] = -(10 - moveCount) * player; // Earlier wins get greater score
            } else if (moveCount == 9) { // It's a draw
                scoreStack[moveCount] = 0;
            } else {
                moveStack[moveCount] = -1; // Prepare for iterating moves for current player
                scoreStack[moveCount] = -player * 10; // Initialize with worst possible score for current player
                moveCount++;
            }
            do { // Repeat:
                moveCount--;
                if (moveCount < originalMoveCount) { // All done
                    break; // Exit point
                }
                // Look for a next, valid move
                move = moveStack[moveCount];
                if (move >= 0) { // Was a valid move: derive score from deeper results
                    score = scoreStack[moveCount + 1]; // Best score opponent can get
                    if ((board[move] == 1) == (score > scoreStack[moveCount])) { // Improvement
                        scoreStack[moveCount] = score;
                        if (moveCount == originalMoveCount) {
                            minimaxReturn = move; // For now this is a best move...
                        }
                    }
                    // Take back move
                    board[move] = 0;
                }
                // Look for next valid move
                do {
                    move++;
                } while (move < 9 && board[move] != 0) // Occupied
            } while (move == 9); // Backtrack (i.e. repeat loop) when all moves were tried
    
            if (moveCount < originalMoveCount) { // All done
                break; // Exit point
            }
            // Play move
            moveCount = play(board, moveStack, moveCount, move);
        }
        return minimaxReturn;
    }
    
    function main() {
        const board = Array(9).fill(0); // An empty 3x3 board as 1 dimensional array
        const moveStack = Array(10);    // History of played moves (indices in board)
        let moveCount = 0;              // Number of moves played
        let bestMove;
        
        /* Demo:
         * Play moves to arrive at this board:
         *  
         *     X | O | 
         *    ---+---+---
         *     O |   |
         *    ---+---+---
         *     X |   |
         */     
        moveCount = play(board, moveStack, moveCount, 0); // Play X in top-left
            moveCount = play(board, moveStack, moveCount, 1); // Play O next to it
        moveCount = play(board, moveStack, moveCount, 6); // Play X in bottom-left
            moveCount = play(board, moveStack, moveCount, 3); // Play O in middle row
        
        // Run minimax for suggesting where to play an "X":
        bestMove = minimax(board, moveStack, moveCount);
        console.log(bestMove); // 4 (center of the board)
    }
    main();