none
Tic Tac Toe Ai, Using Alpha Beta Pruning

    Question

  • Hello, I am attempting to create a Tic Tac Toe game but am having trouble programming the Ai. I searched online and found that alpha beta pruning is used to find the best result. I looked over the code on codeproject but don't know how to adapt it to the way my game is set up currently. Right now I have an array of all the possible combinations for winning. There is a grid with buttons named 1 through 9. Each time a player touches one of the buttons the contents change to that letter and the number/name of that button is added to either the x or o list depending on which letter is playing. How would I adapt the alpha beta pruning to find the best result if right now I only have the x list, o list and possible wins array. Below is the click event that checks to see if there is a winner and adds the corresponding number to the correct list. Any help or explanation would be greatly appreciated. Thanks.

     static private int [,] moves = new int[,]
            {
                 {1,2,3},
                 {4,5,6},
                 {7,8,9},
                 {1,4,7},
                 {2,5,8},
                 {3,6,9},
                 {1,5,9},
                 {3,5,7}
            };
    
     private void emptyButton_Click(object sender, RoutedEventArgs e)
            {
                Button button = sender as Button;
                button.FontSize = 100;
                string x = "X";
                string O = "O";
                bool success;
    
                //checks to see if x won
                if (xTurn && button.Content == null && playing && oList.Count + xList.Count != 9)
                {
                    button.Content = x;
                    int xNum;
                    success = int.TryParse(button.Name.ToString(), out xNum);
                    xList.Add(xNum);
                    if (checkForWin(xList))
                    {
                        resetOpacity();
                        showWinner("X");
                        textBlock.Text = "X Won!";
                        (App.Current as App).lastWinner = "X";
                        (App.Current as App).xWins++;
                        CheckForAchievements();
                        Storyboard1.Begin();
                        Storyboard2.Begin();
                    }
                    else
                    {
                        xTurn = false;
                        showTurn(xTurn);
                    }
                   
                   
                }
                //checks for 0 to win
                else if (xTurn == false && button.Content == null && playing && oList.Count + xList.Count != 9)
                {
                    button.Content = O;
                    int oNum;
                    success = int.TryParse(button.Name.ToString(), out oNum);
                    oList.Add(oNum);
                    if (checkForWin(oList))
                    {
                        resetOpacity();
                        showWinner("O");
                        textBlock.Text = "O Won!";
                        (App.Current as App).oWins++;
                        (App.Current as App).lastWinner = "O";
                        CheckForAchievements();
                        Storyboard1.Begin();
                        Storyboard2.Begin();
                    }
                    else
                    {
                        xTurn = true;
                        showTurn(xTurn);
                    }
                  
                   
                }
    
                //checks for a tie game
                if ((oList.Count + xList.Count) ==9 && playing == true && set == null)
                {
                    resetOpacity();
                    textBlock.Text = "Tie!";
                    (App.Current as App).ties++;
                    (App.Current as App).timesPlayed++;
                    (App.Current as App).lastWinner = "Tie";
                    (App.Current as App).lastPlayed = DateTime.Now;
                    (App.Current as App).playing = false;
                    playing = false;
                    CheckForAchievements();
                    Storyboard1.Begin();
                    Storyboard2.Begin();
                }
            }

    Saturday, December 21, 2013 7:12 PM

Answers

  • In simple terms you have a number of choices of valid moves that player A can make. For each of those moves you create another virtual board that represents the state after each of those moves. For each of those boards you create yet another set of virtual boards for every valid response that player B could make. You repeat this until either 1) you get a winning conclusion 2) you reach a 'thinking depth' and stop. In theory, if your algorithms for evaluating the best move are correct then you'll know which of the moves from the first set of virtual boards is your best move. The pruning aspect is a way to speed the process up. For tic-tac-toe pruning isn't necessary since the number of permutations of virtual boards is small and they all can be quickly evaluated. You typically need pruning when the game moves are more complex and the processing time for all the possibilities would be too long. Then you remove specific virtual boards because you think the resulting score is too low that any subsequent move could never recover the score. This is essentially how chess masters used to fool computers by luring the AI into mistakes because they knew they'd prune moves that would, eventually, become the best move.

    http://pauliom.wordpress.com

    Sunday, December 22, 2013 1:24 PM

All replies

  • Forget about the phone. Open a console project and get the AI working. Don't be distracted by the UI. Ensure you understand the concept of having many 'boards' running and choosing the one that produces the best overall score. How much do you understand of the concepts of alpha/pruning?

    http://pauliom.wordpress.com

    Saturday, December 21, 2013 7:19 PM
  • Forget about the phone. Open a console project and get the AI working. Don't be distracted by the UI. Ensure you understand the concept of having many 'boards' running and choosing the one that produces the best overall score. How much do you understand of the concepts of alpha/pruning?

    http://pauliom.wordpress.com


    I would say I know close to nothing other than that there seem to be slight variations to doing it. I also looked at some videos that explained the process but I wasn't quite sure why it worked exactly and how it could be applied to something like Tic Tac Toe.  
    Saturday, December 21, 2013 9:41 PM
  • In simple terms you have a number of choices of valid moves that player A can make. For each of those moves you create another virtual board that represents the state after each of those moves. For each of those boards you create yet another set of virtual boards for every valid response that player B could make. You repeat this until either 1) you get a winning conclusion 2) you reach a 'thinking depth' and stop. In theory, if your algorithms for evaluating the best move are correct then you'll know which of the moves from the first set of virtual boards is your best move. The pruning aspect is a way to speed the process up. For tic-tac-toe pruning isn't necessary since the number of permutations of virtual boards is small and they all can be quickly evaluated. You typically need pruning when the game moves are more complex and the processing time for all the possibilities would be too long. Then you remove specific virtual boards because you think the resulting score is too low that any subsequent move could never recover the score. This is essentially how chess masters used to fool computers by luring the AI into mistakes because they knew they'd prune moves that would, eventually, become the best move.

    http://pauliom.wordpress.com

    Sunday, December 22, 2013 1:24 PM
  • Thank you for your reply. I still have a few questions that I would like clarified.

    When you say "create another virtual board", do you mean create a scenario where you look at the different moves possible with where the player's piece is currently placed? For example, if the player makes a move in the first, upper-left corner, or as I called it 1, you would look at the outcomes if you placed a piece in every spot except the one where the player made their first moves? If this is the case, how would you know which spot is best to place the letter considering most of the choices would have about the same result? The same can be said for if the player makes their first move in the very center. Or do you mean to say that you create multiple scenarios for each move that could be made and then multiple scenarios under each of those original possible moves? If that is the case it seems like you would get a lot of different combinations to choose from. 

    Again,thank you for your in-depth explanation.   

    Sunday, December 22, 2013 5:07 PM
  • The latter of the two. Hence you create a tree of possible boards, hence the term pruning. For Tic Tac Toe that tree would be very small for a computer to process.

    http://pauliom.wordpress.com

    Sunday, December 22, 2013 10:29 PM
  • Ok, then if that is the case would I only evaluate 1 move ahead. For example, if the user places a letter I would only take into account what the next best move would be, not guessing what move they would make after the ai makes a choice of where to place the letter. So as the game goes on it should be easier to determine which is the best move.

    Also, if that is the case how does the computer determine the best place to play if there has only been one move? If the player plays their first piece in the very center all the empty spaces around it are fair game. In this case should the ai choose a spot randomly and wait to see where the player puts their next piece?

    Thursday, December 26, 2013 5:11 PM
  • The depth, or ply, it a strong indicator on how clever your AI is. At 1 ply it's going to play a pretty dumb game...having said that TTT is a pretty dumb game so you'll probably get away with it. In the case with the same score is achieved for each ply, then you can choose a rnd move

    http://pauliom.wordpress.com

    Friday, December 27, 2013 6:33 PM
  • Thank you, this clarified a lot of the questions I had.

    Monday, December 30, 2013 4:58 PM