Tic-tac-toe with MyCobot — Part 2

Hello Aliens

Continuing from the previous blog post, the upcoming content will provide an overview of the Minimax Algorithm, delve into the task setup, and illustrate the seamless integration of these components. The blog will explore how each element contributes to the successful execution of the task at hand, offering a comprehensive understanding of the Minimax Algorithm and its practical application within the specified context.

Minimax Algorithm

The minimax algorithm is a decision-making algorithm commonly used in two-player turn-based games such as chess, checkers, or tic-tac-toe. The primary goal of the minimax algorithm is to determine the optimal move for a player, considering all possible moves and their potential outcomes.

Here’s a simplified explanation of how the Minimax algorithm works:

1. Evaluation Function: Assign a value to each possible game state. This value represents how favorable the state is for the current player. For example, in a chess game, a positive value might indicate an advantageous position, while a negative value might suggest a disadvantage.
2. Recursive Tree Search: Generate a tree of possible moves, where each level alternates between the maximizing player (trying to maximize the evaluation function) and the minimizing player (trying to minimize the evaluation function). Recursively evaluate each node in the tree until reaching a specified depth or a terminal game state.
3. Backtracking: Propagate the values from the terminal nodes back up the tree, adjusting the values based on whether it’s the turn of the maximizing or minimizing player. At each level, the maximizing player chooses the move that leads to the maximum value, while the minimizing player chooses the move that leads to the minimum value.
4. Optimal Move: The root of the tree represents the initial game state, and the algorithm selects the move that leads to the child node with the highest value, assuming both players play optimally.

This algorithm ensures that the AI player makes decisions with the assumption that the opponent will also make optimal moves. However, it has limitations in terms of the computational resources required, especially as the game tree grows exponentially. To mitigate this, optimizations like alpha-beta pruning are often applied to reduce the number of branches that need to be explored.

A back and forth between both players, along with the player deciding whose “turn it is,” is crucial to the Minimax algorithm to be able to determine which player has the best result. The other player then selects which of its possible actions has the lowest possible score, calculating the scores for each of the possible actions. The player taking turns subsequently attempts to maximize its score, and so on along the move tree into an end state, deciding the scores for the moves of the opposing players.

Walking through the algorithm execution.

1. In state 1, it is now the X’s turn. X runs minimax on states 2, 3, and 4 upon generating them.
2. Since the match is at its final state, the second state gives the score of +10 to state 1’s score list.
3. Without being in the end states, states 3 and 4 generate states 5 and 6 and use minimax on them, whereas states 4 create states 7 and 8 and use minimax on them.
4. State 5 places a score of -10 on the rating list of state 3, while state 7 performs the same, giving a score of -10 on the score list of state 4.
5. States 6 and 8 add a rating of +10 to the move lists of states 3 and 4 as they generate the only feasible moves, which are end states.
6. As it is O’s turn in states 3 and 4, O is going to attempt to find the smallest score; given the option, the two states 3 and 4 will result in a score of -10.
7. State 1 will choose the winner’s move with a score of +10 in a bid to best utilise the score, while state 2 will fill up the score list for states 2, 3, and 4 with +10, -10, and -10, respectively.

To summarize, the minimax algorithm works on game tree representations, backward recursion (minimax), and decision-making. While playing a game like tic-tac-toe, the algorithm evaluates all of the potential moves, gives a numerical value for every game state, and chooses the move that gives the participant the best outcome at the time after taking the opponent’s best response into consideration.

Setup

Installing Pymycobot and the necessary Python software is the first step. You must install myCobot for Linux after installing Python. Next, you must download and burn the transponder while the base is linked to the display. Next, open myStudio, download Atom, and flash it. To stop the robot from hitting the camera module, simply install the required software and then set all motor settings to 0 degrees. After that, use the calibration code to calibrate. In addition to it, install the necessary OpenCV packages as well. Make sure the environment is properly set for error-free execution. Remember, this task is nothing but establishing a nice integration of Robotics, Artificial intelligence, and Computer Vision.

The logic encoded in the script consists of some methods related to the Minimax algorithm that are integrated.

a. Creation of tic-tac-toe board

1. board_initialization(): as I set the columns and rows to 3 each. I want to create a board in a 3x3 matrix shape that represents each cell in the game.
2. draw_board(): takes an image as input and draws a tic-tac-toe board on it. The board is divided into a grid with horizontal and vertical lines. The black colour lines are used with a line thickness of 3 pixels.
3. print_board(): displays the tic-tac-toe board in the console.

b. Centers for the blocks in the game

1. block_centers(): got these coordinates by collecting all the 9 block coordinates and their centers.

c. Getting the pickup places and the other relevant coordinates

1. pickup_place_cords(): Giving the coordinates to the myCobot to pickup the block for its (computer) move. And placing the blocks at the mentioned centers, which I declared in the block_centers().

d. Minimax algorithm

1. minimax(): This function is a recursive implementation of the minimax algorithm for a tic-tac-toe game. The function evaluates the game state and returns a score based on whether the ‘O’ player or the ‘X’ player is maximizing their score.

Base Cases:

If the ‘O’ player has won, the function returns 1.

If the ‘X’ player has won, the function returns -1.

If the board is full and there’s no winner, the function returns 0.

Recursive Cases:

If it’s the turn for the maximizing player (currently ‘O’), the function iterates through available pickup_place_cords, simulates each pickup_place_cords, and calls itself recursively with the updated board and the next player’s turn (‘X’). It then updates max_eval with the maximum value obtained from these recursive calls.

If it’s the turn for the minimizing player (currently ‘X’), the function does the same but minimizes the values by updating min_eval with the minimum value obtained from recursive calls.

Undoing pickup_place_cords: After each pickup_place_cords simulation, the board is reverted to its original state by resetting the cell to an empty space.

2. find_best_pickup_place_cords() : AI algorithm for playing Tic-Tac-Toe. It uses the minimax algorithm to evaluate and choose the best pickup_place_cords for the ‘O’ player.

3. cross_check_winner() : Checks which player has won the game. In order to do that, need to check the rows and columns and also the diagonals.

Credits to Elephant Robotics for the color recognition code.

The Aruco’s (markers) were detected upon which the grids (tic tac toe game board) get activated and displayed on the screen. Place the green blocks in the bin from which the cobot picks up. Apart from it, I need to have the yellow cubes. So, as a part of the first move, I need to put the yellow block in one of the 9 grids, and the camera module identifies the block and based on the minimax algorithm’s next decision of making a move, the cobot pickups the green block from the bin and puts it in the grid as guided by the minimax algorithm. Now, it is my turn to pace yellow block in the grid which ever I want. And then the cobot takes it move and this process continues on until an end result is achieved. You can see the video below

In my video, the game was won by the computer as it followed the decisions from the Minimax algorithm. The robot advances to the green block and picks up the green block and put it in the respective coordinates as directed by the logic by the Minimax algorithm. In my turn I need to keep the yellow block in the grid which ever I want to place. The process continues on. This demonstrates the cobot’s capabilities by using the color recognition. The cobot’s capabilities, decision making algorithm (AI Move), and the computer vision all combinedly comes together to get this task done.

References

[1] https://www.hackster.io/Elephant-Robotics-Official/newly-upgraded-and-user-friendly-ai-kit-2023- a23669

[2] https://docs.elephantrobotics.com/docs/gitbook-en/2-serialproduct/2.10-AIkit2023en_320/3- color_recognition.html

[3] https://www.geeksforgeeks.org/minimax-algorithm-in-game-theory-set-1-introduction/

Thanks for reading the article! If you like my article, do 👏 this article. If you want to connect with me on LinkedIn, please click here.

I plan to share additional blog posts covering topics such as robotics, drive-by-wire vehicles, machine learning, deep learning, etc..

Stay tuned.

This is Karteek Menda.

Signing Off