User Tools

Site Tools


lab_5_milestone_1

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

lab_5_milestone_1 [2019/05/07 12:16] (current)
hutch created
Line 1: Line 1:
 +==== Milestone 1: minimax ====
 +In this milestone you will implement the algorithm for the computer player. If you are successful, it will be impossible to beat the computer when you play against it. We will be using an algorithm called minimax (or something close, anyway). The algorithm is often used to create a computer-player in a two-player game such as Tic-Tac-Toe.
 +
 +A very good description using minimax to implement a computer-player for Tic-Tac-Toe can be found [[http://​www.neverstopbuilding.com/​minimax|here]]. I also archived it as {{::​tic_tac_toe_understanding_the_minimax_algorithm_-_never_stop_building.pdf|PDF}}.
 +
 +I have annotated some of the figures and will discuss these in class.
 +
 +{{ tictactoegametreenotes1.jpg?​800 }}
 +
 +------------
 +
 +{{ tictactoegametreenotes2.jpg?​800 }}
 +
 +=== Tic-Tac-Toe Minimax Pseudocode ===
 +
 +Here is some pseudocode that describes the algorithm in more detail. This should be helpful after you have carefully studied how the algorithm works and you start writing '​C'​ code.
 +
 +Notes: ​
 +  * For the pseudocode shown below, **choice** is a global variable that will hold the move computed by minimax. Minimax must return at least a score because that is how you build the move-score table recursively. However, minimax must also compute the move because it is associated with the score. So, when doing the max calculation for example, you find the index of the highest score in the list and then save the move associated with that score in **choice**. **choice** will be overwritten many times as minimax executes but that is OK. The only move you care about is the move associated with the max score at the first call of minimax. That will also be the last time that **choice** is written so it will contain the move you care about - the move associated with the highest score (assuming that you are '​X'​).
 +  * move can be implemented as a struct containing a row and a column.
 +  * You can store your moves and scores in two arrays: a moves array and a scores array. Use one index for both.
 +
 +<​code>​
 +// current_player_is_x == true means X, current_player_is_x == false means O
 +int minimax(board,​ bool current_player_is_x) {
 +  if (game is over)   // Recursion base case, there has been a win or a draw.
 +    // If game is over, you need to evaluate board based upon previous player/​opponent.
 +    return score(board,​ !current_player_is_x);  ​
 +  // Otherwise, you need to recurse.
 +  // This loop will generate all possible boards.
 +  for all rows {
 +    for all columns {
 +      if (board[row][column] == EMPTY_SQUARE) {
 +        // Assign the square to '​X'​or '​O'​.
 +        if (current_player_is_x) ​
 +          board[row][column] = X_SQUARE
 +        else 
 +          board[row][column] = O_SQUARE
 +        score = minimax(board,​ !current_player_is_x)
 +        add score to move-score table
 +        add move to move-score table
 +        // Undo the change to the board (return the square to empty) prior to next iteration of for-loops.
 +        board[row][column] = EMPTY_SQUARE
 +      }
 +    }
 +  }
 +  // Once you get here, you have iterated over empty squares at this level. All of the scores have been computed
 +  // in the move-score table for boards at this level. ​
 +  // Now you need to return the score depending upon whether you are computing min or max.
 +  if (current_player_is_x) {
 +    choice <= get the move with the highest score in the move-score table.
 +    score <= highest score in the move-score table.
 +  } else {
 +    choice <= get the move with the lowest score in the move-score table.
 +    score <= lowest score in the move-score table. ​
 +  }
 +  return score;
 +}
 +</​code>​
 +=== Helps ===
 +  - I suggest that you develop your minimax algorithm on a regular computer. minimax doesn'​t rely on anything provided by the 330 board and you will be able to debug more quickly because you won't need to wait for downloads, etc. Once you get minimax working it is easy to bring it over to the Xilinx SDK.
 +  - It is a good idea to have a printBoard routine that prints out a board. This is very useful when debugging.
 +  - I found it helpful to break down a winning board into row-based wins, column-based wins, and diagonal-based wins.
 +  - You can add a depth argument to minimax that can be helpful during debugging. You invoke minimax with a depth of 0 and have minimax print the depth variable when invoked and then incrementing the depth variable when recursing.
 +
 +=== Debugging Recursive Minimax ===
 +Often the best way to debug recursive programs is to print out an execution trace. Adding a "​depth"​ argument that you increment at each invocation makes it much easier to follow program execution.
 +
 +A debug dump of my minimax program is shown below. The starting board is the same as the board we used in class and is the same one in the game-trees shown above. I have annotated the dump with the board-numbers used in the example shown above.
 +
 +<​code>​
 +Invoking minimax @ depth = 0
 +**Board 1**
 +0 X
 +X  ​
 +X00
 +adding player @ (0, 1)
 +
 +Invoking minimax @ depth = 1
 +**Board 3**
 +0XX
 +X  ​
 +X00
 +adding opponent @ (1, 1)
 +
 +Invoking minimax @ depth = 2
 +**Board 5**
 +0XX
 +X0 
 +X00
 +opponent wins, returning score: -10
 +adding opponent @ (1, 2)
 +
 +Invoking minimax @ depth = 2
 +**Board 6**
 +0XX
 +X 0
 +X00
 +adding player @ (1, 1)
 +
 +Invoking minimax @ depth = 3
 +**Board 9**
 +0XX
 +XX0
 +X00
 +player wins, returning score: 10
 +adding player @ (1, 1)
 +
 +Invoking minimax @ depth = 1
 +**Board 2**
 +0 X
 +XX 
 +X00
 +player wins, returning score: 10
 +adding player @ (1, 2)
 +
 +Invoking minimax @ depth = 1
 +**Board 4**
 +0 X
 +X X
 +X00
 +adding opponent @ (0, 1)
 +
 +Invoking minimax @ depth = 2
 +-- Starting board -- **Board 8**
 +00X
 +X X
 +X00
 +adding player @ (1, 1)
 +
 +Invoking minimax @ depth = 3
 +**Board 10**
 +00X
 +XXX
 +X00
 +player wins, returning score: 10
 +adding opponent @ (1, 1)
 +
 +Invoking minimax @ depth = 2
 +**Board 7**
 +0 X
 +X0X
 +X00
 +opponent wins, returning score: -10
 +final score: 10
 +final choice: (row: 1, column: 1)
 +
 +</​code>​
 +
 +=== Requirements ===
 +  - You will write one file: ''​minimax.c''​. The contents of minimax.h must be exactly what is provided below.
 +  - You must provide the functions listed below via the .h file. You must use these data-structures,​ #define, etc., for the listed functions. Please implement helper functions in the .c file (not advertised in the .h file) to make your code modular and easier to read and to debug.
 +  - You must test your minimax algorithm by writing at least 10 additional test-boards (see provided test code below). The TA will check for this.
 +
 +
 +<file C minimax.h>​
 +#include <​stdint.h>​
 +// Defines the boundaries of the tic-tac-toe board.
 +#define MINIMAX_BOARD_ROWS 3
 +#define MINIMAX_BOARD_COLUMNS 3
 +
 +// These are the values in the board to represent who is occupying what square.
 +#define MINIMAX_X_SQUARE 2    // player-square means X occupies the square.
 +#define MINIMAX_O_SQUARE 1  // opponent-square means O occupies the square.
 +#define MINIMAX_EMPTY_SQUARE 0
 +
 +// Scoring for minimax.
 +#define MINIMAX_X_WINNING_SCORE 10     // This means that X will win.
 +#define MINIMAX_O_WINNING_SCORE -10  // This means that O will win.
 +#define MINIMAX_DRAW_SCORE 0                // Nobody wins.
 +#define MINIMAX_NOT_ENDGAME -1              // Not an end-game.
 +
 +
 +// Boards contain just an array of squares. I used a struct to provide additional abstraction
 +// in case I wanted to add something to the board type.
 +typedef struct {
 + uint8_t squares[MINIMAX_BOARD_ROWS][MINIMAX_BOARD_COLUMNS]; ​ // State of game as passed in.
 +} minimax_board_t;​
 +
 +// A move is simply a row-column pair.
 +// Use this syntax to assign values to the struct.
 +// If the struct is passed via &, my_struct->​row = some value
 +// If the struct is passed without the &, my_struct.row = some value.
 +typedef struct {
 + uint8_t row;
 + uint8_t column;
 +} minimax_move_t;​
 +
 +// Define a score type.
 +typedef int16_t minimax_score_t;​
 +
 +// This routine is not recursive but will invoke the recursive minimax function. ​
 +// You will call this function from the controlling state machine that you will implement in a later milestone.
 +// It computes the row and column of the next move based upon:
 +// the current board,
 +// the player. true means the computer is X. false means the computer is O.
 +// When called from the controlling state machine, you will call this function as follows:
 +// 1. If the computer is playing as X, you will call this function with current_player_is_x = true.
 +// 2. If the computer is playing as O, you will call this function with current_player_is_x = false.
 +// minimax_computeNextMove directly passes the current_player_is_x argument into the minimax() (helper) function.
 +// To assign values to the row and column arguments, you must use the following syntax in the body of the function:
 +// *row = move_row; *column = move_column;​ (for example).
 +void minimax_computeNextMove(minimax_board_t* board, bool current_player_is_x,​ uint8_t* row, uint8_t* column);
 +
 +// Determine that the game is over by looking at the score.
 +bool minimax_isGameOver(minimax_score_t score);
 +
 +// Returns the score of the board, based upon the player and the board.
 +// This returns one of 4 values: MINIMAX_X_WINNING_SCORE, ​
 +// MINIMAX_O_WINNING_SCORE,​ MINIMAX_DRAW_SCORE,​ MINIMAX_NOT_ENDGAME
 +// Note: the player argument makes it possible to speed up this function.
 +// Assumptions: ​
 +// (1) if current_player_is_x == true, the last thing played was an '​X'​.
 +// (2) if current_player_is_x == false, the last thing played was an '​O'​.
 +// Hint: If you know the game was not over when an '​X'​ was played,
 +// you don't need to look for '​O'​s,​ and vice-versa.
 +minimax_score_t minimax_computeBoardScore(minimax_board_t* board, bool player_is_x);​
 +
 +// Init the board to all empty squares.
 +void minimax_initBoard(minimax_board_t* board);
 +</​file>​
 +=== Pass-Off ===
 +To pass the algorithm milestone, you need to demonstrate your minimax program providing the correct answer for several provided boards and **for 10 additional boards** that you must write. After adding your test boards to the test-code below, test your minimax program using the program shown below.
 +
 +**Note: if your minimax algorithm passes these tests, you may still have bugs in your code. These tests are not exhaustive. I strongly advise you to test your minimax code much more thoroughly. Otherwise, you will find that you game may not be unbeatable in the final milestone.**
 +<​code>​
 +#include "​minimax.h"​
 +#include <​stdio.h>​
 +
 +int main() {
 +  minimax_board_t board1; ​ // Board 1 is the main example in the web-tutorial that I use on the web-site.
 +  board1.squares[0][0] = MINIMAX_O_SQUARE;​
 +  board1.squares[0][1] = MINIMAX_EMPTY_SQUARE;​
 +  board1.squares[0][2] = MINIMAX_X_SQUARE;​
 +  board1.squares[1][0] = MINIMAX_X_SQUARE;​
 +  board1.squares[1][1] = MINIMAX_EMPTY_SQUARE;​
 +  board1.squares[1][2] = MINIMAX_EMPTY_SQUARE;​
 +  board1.squares[2][0] = MINIMAX_X_SQUARE;​
 +  board1.squares[2][1] = MINIMAX_O_SQUARE;​
 +  board1.squares[2][2] = MINIMAX_O_SQUARE;​
 +
 +  minimax_board_t board2;
 +  board2.squares[0][0] = MINIMAX_O_SQUARE;​
 +  board2.squares[0][1] = MINIMAX_EMPTY_SQUARE;​
 +  board2.squares[0][2] = MINIMAX_X_SQUARE;​
 +  board2.squares[1][0] = MINIMAX_EMPTY_SQUARE;​
 +  board2.squares[1][1] = MINIMAX_EMPTY_SQUARE;​
 +  board2.squares[1][2] = MINIMAX_EMPTY_SQUARE;​
 +  board2.squares[2][0] = MINIMAX_X_SQUARE;​
 +  board2.squares[2][1] = MINIMAX_EMPTY_SQUARE;​
 +  board2.squares[2][2] = MINIMAX_O_SQUARE;​
 +
 +  minimax_board_t board3;
 +  board3.squares[0][0] = MINIMAX_O_SQUARE;​
 +  board3.squares[0][1] = MINIMAX_EMPTY_SQUARE;​
 +  board3.squares[0][2] = MINIMAX_EMPTY_SQUARE;​
 +  board3.squares[1][0] = MINIMAX_O_SQUARE;​
 +  board3.squares[1][1] = MINIMAX_EMPTY_SQUARE;​
 +  board3.squares[1][2] = MINIMAX_EMPTY_SQUARE;​
 +  board3.squares[2][0] = MINIMAX_X_SQUARE;​
 +  board3.squares[2][1] = MINIMAX_EMPTY_SQUARE;​
 +  board3.squares[2][2] = MINIMAX_X_SQUARE;​
 +
 +  minimax_board_t board4;
 +  board4.squares[0][0] = MINIMAX_O_SQUARE;​
 +  board4.squares[0][1] = MINIMAX_EMPTY_SQUARE;​
 +  board4.squares[0][2] = MINIMAX_EMPTY_SQUARE;​
 +  board4.squares[1][0] = MINIMAX_EMPTY_SQUARE;​
 +  board4.squares[1][1] = MINIMAX_EMPTY_SQUARE;​
 +  board4.squares[1][2] = MINIMAX_EMPTY_SQUARE;​
 +  board4.squares[2][0] = MINIMAX_X_SQUARE;​
 +  board4.squares[2][1] = MINIMAX_EMPTY_SQUARE;​
 +  board4.squares[2][2] = MINIMAX_X_SQUARE;​
 +
 +  minimax_board_t board5;
 +  board5.squares[0][0] = MINIMAX_X_SQUARE;​
 +  board5.squares[0][1] = MINIMAX_X_SQUARE;​
 +  board5.squares[0][2] = MINIMAX_EMPTY_SQUARE;​
 +  board5.squares[1][0] = MINIMAX_EMPTY_SQUARE;​
 +  board5.squares[1][1] = MINIMAX_O_SQUARE;​
 +  board5.squares[1][2] = MINIMAX_EMPTY_SQUARE;​
 +  board5.squares[2][0] = MINIMAX_EMPTY_SQUARE;​
 +  board5.squares[2][1] = MINIMAX_EMPTY_SQUARE;​
 +  board5.squares[2][2] = MINIMAX_EMPTY_SQUARE;​
 +
 + ​uint8_t row, column;
 +
 + ​minimax_computeNextMove(&​board1,​ true, &row, &​column); ​     // true means X is current player.
 + ​printf("​next move for board1: (%d, %d)\n\r",​ row, column);
 + ​minimax_computeNextMove(&​board2,​ true, &row, &​column); ​     // true means X is current player.
 + ​printf("​next move for board2: (%d, %d)\n\r",​ row, column);
 + ​minimax_computeNextMove(&​board3,​ true, &row, &​column); ​     // true means X is current player.
 + ​printf("​next move for board3: (%d, %d)\n\r",​ row, column);
 + ​minimax_computeNextMove(&​board4,​ false, &row, &​column); ​    // false means O is current player.
 + ​printf("​next move for board4: (%d, %d)\n\r",​ row, column);
 + ​minimax_computeNextMove(&​board5,​ false, &row, &​column); ​    // false means O is current player.
 + ​printf("​next move for board5: (%d, %d)\n\r",​ row, column);
 +}
 +</​code>​
  
lab_5_milestone_1.txt ยท Last modified: 2019/05/07 12:16 by hutch