Yet Another Tic Tac Toe. Yet Another Tic Tac Toe program. With- in about 3. I had a game up and running in which I could play against my step- daughter. My implementation separated the game logic into three areas: model, UI, and an AI class. The associated source files for these areas are Tic. Tac. Toe. Game. vb, frm. Tic. Tac. Toe. vb, and Tic. Tac. Toe. AI. vb. General programming areas used in this project include Enums, Events, and Overloading a property. After implementing my version of tic- tac- toe, I researched how others have implemented the game. Grant Richard has written a good article in the C# area here. The Tic- Tac- Toe Model. A tic- tac- toe board can have three entries in a square: Nothing, X, and O. These are represented by an Enum called Grid. Entry. The Enums are appropriately called No. Entry, Player. X, and Player. O. A multi- dimensional grid of 3x. Grid. Entry represents the playing board. Also note that the enum is inside the class. This allows the programmer to code CLASSNAME. ENUM from other classes. Public. Class Tic. Tac. Toe. Public. Enum Grid. Entry. No. Entry = 0. Player. X = 1. Player. O = 2. End. Enum. Private m. This property gets/sets a type of Grid. Entry. A user can only set a Square to either X or O. If they try to overwrite a square once it has been written to, the set property ignores the set operation. The set property also checks to see if there is a winner condition or draw condition and raises the appropriate event. Public. Event Tic. Tac. Toe. Win. Occured(By. Val a. Winner as Grid. Entry) Public. Event Cat() . This class was called Square. Coordinate which would allow me to pass one parameter to a function instead of i. Row and i. Col. So the property Square was overloaded to take a Square. Coordinate variable. Public. Property Square(a. SC as Square. Coordinate) as Grid. Entry. Get. Return m. This is setup using an Add. Handler command and using the Address. Of operator to point to lbl. Grid. Each control is named lbl. Grid. XX where XX is the grid coordinates for the square as noted above. For example 0. 0 is the first square. The subroutine Draw. Grid updates the labels with the data in the tic- tac- toe model. Add. Handler lbl. Grid. 00. Click, Address. Of lbl. Grid. If the same player is in all three squares in one direction, that player is returned from the win logic code; otherwise No. Entry is returned. Before Going to start, a short description. Private. Function Check. For. Horizontal. Win() as Grid. Entry. Dim i. Row as. Integer. Dim i. First. Square. Player as Grid. Entry. For i. Row = 0to. First. Square. Player = m. This Visual Basic source code shows a full tic tac toe game in VB6. It uses forms, graphics, a simple AI algorithm, and other fun game stuff. Get started learning how to program games by programming Tic Tac Toe in Visual Basic. How to build the GUI, determine play, and find a winner. Yet Another Tic Tac Toe program. This example breaks the tic tac toe game into three parts. Model data, UI, and AI.; Author: Ralph Main; Updated:; Section: VB.NET; Chapter: Languages; Updated. Now, input 8 in TextBox1 and 10 in TexBox2 then click the Button. It will have a multiplication table like the image below. Download the source code below and try it! Programming resources for C and C++, Visual C++ and C#.Net Languages, C and C++ Programming tutorials and articles, Source Code, free open source programs and. I wrote this code to demonstrate how to program artificial intelligence (AI) into a two-player board game after seeing several requests for help on doing so in an online coding forum. I chose tic-tac-toe (also. We loop through all squares, and if we find a No. Entry, return false; otherwise if they are all full, return true for a draw. Private. Function Check. For. Draw() as. Boolean. Dim i. Row as. Integer, i. Col as. Integer. For i. Row = 0to. 2For i. Col = 0to. 2If m. There are four general rules that the AI class follows: Win if possible. Block opponent from winning. Determine a Best Bet move to setup a future win. Make any valid move. A Move. Entry class has been created to contain possible moves. This is a private class only accessiable to the Tic. Tac. Toe. AI class. This class contains two variables: a Square. Coordinate, and a Move. Type of Winning, Blocking, or Normal. Private. Enum Move. Type. Blocking = 1. Winning = 2. End. Enum. The Tic. Tac. Toe. AI class has only one public method Get. AIMove(By. Val a. TTT as Tic. Tac. Toe) and returns a Square. Coordinate. The workhorse of the AI is the private function Determine. Move. Entry(a. SC as Square. Coordinate) which classifies a Square. Coordinate to either a winning move, a blocking move, or a normal move. It first checks horizontal, vertical, and finally diagonal. To check diagonal, another enum is used along with a function to determine which tic tac toe square is being examined. Private. Enum Square. Type. Upper. Left = 1. Upper. Right = 2. Bottom. Left = 4. Bottom. Right = 5. Other = 6. End. Enum. Private. Function Determine. Move. Entry(By. Val a. SC as Square. Coordinate) . If there are no winning moves or blocking moves, it tries to determine if there are any best moves by calling Determine. Best. Normal. Move(a. Normal. Move. List as Array. List). Otherwise it picks a normal move at random. I had fun writting this tic- tac- toe program. I may in the future examine other implementations of the base model and the logic for determining win, draw, and AI moves. For example, Grant Richard uses a single array of 9 squares numbering each square 1 to 9 with his win conditions contained in an array. His article is here. Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages. Simple Artificial Intelligence in C# . I chose tic- tac- toe (also known as noughts and crosses) since virtually everyone knows the game and the rules are simple enough that we don’t need an elaborate analysis of game configurations. Basically, we would like a computer player to . There are of course many ways to do this. In this post we will explore a common method of searching for moves by building game trees that represent the space of possible moves (game configurations) and selecting a move which yields the best outcome. Game trees can be quite large, particularly so for complex games, and as such can take quite a bit of time to construct and evaluate. Even tic- tac- toe, as simple as it is, has. That may sound like quite a lot but it pales in comparison to chess which has an estimated. Thankfully, computers are especially suited for dealing with these types of problems though it is interesting to note that for a long time it was believed that a computer would never be able to defeat humans at games like chess. Sadly (or perhaps not) for humans this is no longer the case. Getting Started. I am going to assume that everyone knows how to play the game so I won. If you wish to run the game you will need the . NET 4. 0 Framework installed on your machine. If you wish to edit the solution you will need Visual Studio 2. Visual Studio Express (I. The source code for this project can be found here. In order to follow along, you are going to need some object- oriented programming experience as I assume that the reader understands concepts like using abstract classes and inheritance. The code is written in C# but anyone with java, C++ or VB. NET experience should be okay. The primary focus here will be on the AI portions of the code but I will walk through much of the code. Internally, the board is modeled as a two- dimensional array of integers. A value of 0 represents an empty space, a value of 1 an . The array indices represent the row and column respectively. The convention used for position number is shown in figure 1 below. Note that while the internal representation of the board pieces is an int, this is not exposed to clients. Instead an enumeration representing the game pieces is used (enum Pieces) This keeps things clean and prevents coding accidents. This is important as our computer player will need to test out moves on Board objects and we don’t want to muck around with the actual game board so we will use clones. It is responsible for keeping track of each player’s turn and making moves on the board and ends the game when a player wins or a draw has been reached. The move class is shown below. As you can see it an encapsulation class used to store the move position and piece being moved. The human player is responsible for getting a move from a live person while the. The code for the Player class is shown below. This is used to notify listeners when a move has been made. This is useful because the move selection for the players run in their own thread so that it does not block the main thread (and UI) while waiting for a player to select a move. The code for Human. Player is shown below. All it does is wait for a click on the game board UI and then invokes the Player. Moved event which is handled by the game Tic. Tac. Toe. Form. In order to accomplish this we are going to. We will follow usual convention and choose. With the evaluation function in place we can use the. We will take a closer look at the minimax algorithm in a bit but for now let’s define the evaluation function. Defining an Evaluation Function. There are many ways to construct an evaluation function that meets our criteria. The way I chose is fairly simple: . Kind of a mouthful, I know. Have a look at figure 2 below which shows a sample calculation of e(m) with . We are free to choose any sufficiently large number as long as we can guarantee that it is impossible . Conceptually, I like to use. In this program I used double. Max. Value and double. Min. Value respectively. This is not so difficult for tic- tac- toe because there is not much strategy to consider and we won’t need to look too far ahead to see whether we have chosen a good move or not. A game like chess however, is a completely different matter. A poor evaluation function will lead to a very bad computer player even in end- game scenarios where there are only a few moves to make. In more complex games, you may need to experiment a bit with fine- tuning the evaluation function to ensure that it reasonably characterizes how favorable a given configuration is. Now that we have an evaluation function we are ready to describe the minimax algorithm (informally), which will enable our computer player to decide on an . What we will do is make a tree of possible moves down to a given depth. The depth represents how many levels of moves the computer will look ahead. A tree of depth of 2 contains all the possible moves the computer can make and all of the subsequent moves that the computer’s opponent can counter with. The tree’s root node will represent the initial board configuration. We will have two kinds of nodes, MAX nodes and MIN nodes. MAX node are used to represent configurations for which the computer must move and MIN nodes represent board configurations for which the computer’s opponent must move. Thus, the tree’s root node is always a MAX node. MAX nodes select the move that results in the MAXimum e(m). We continue construction of the tree by generating children for these MIN nodes, which are of course MAX nodes since it will be the computer’s turn again in the board configurations represented. The tree construction continues in this manner until we reach the specified depth. Let’s walk through an example using the configuration in figure 3 shown below. This configuration will be represented by the root node of our game tree. This will be our root node, and since it represents a configuration for which the computer needs to move it is a MAX node. The computer can move in positions 3, 5, and 6. Each of the moves yield a new configuration and are represented as children of the root node. Because the child nodes represent configurations for which the opponent must move they are MIN nodes (see figure 4 below). Figure 4: Game tree showing three children spawned from the root node representing an . Since these children are the children of MIN nodes they will be MAX nodes. This is always the case. MAX nodes have MIN children and vice- versa. The graphic below shows the complete tree for depth 2. Figure 5: A Tic- Tac- Toe game tree of depth 2. We can now begin to apply the minimax algorithm. Figure 5 below shows the tree with the e(m) values calculated by the evaluation function for the bottom child nodes. Figure 6: Tree showing e(m) calculation for the bottom- most children. With the e(m) values calculated for the bottom. The best move for a MIN node is the child node that has the minimum value. The values the MIN nodes have selected are shown circled to the right of the min nodes. These are displayed this way to distinguish selected values from values that are calculated directly from the evaluation function. Only nodes on the bottom level use the evaluation function to compute their values. Figure 7: The MIN nodes are assigned the values representing their best move, which is the child node that has the minimum e(m) value. Now the root node selects the maximum value from among it’s children. The node with e(m)= 0 is the maximum so that is selected by the root node as the best move for the computer to make (moving to position 6). The algorithm predicts a loss if a move to position 3 or 5 is made where e(m) = - . We will build our search tree using Node objects that will represent a particular move made. As discussed earlier, there are two types of Nodes, MAX and MIN nodes. In code, we define the. We will make use of an abstract Node class to capture the common properties and functionality of MIN and MAX nodes. The code for the Node class is shown below. Each Node has a value associated with it, either computed directly from the evaluation function or by selecting the maximum (for MAX Nodes) or minimum (for MIN Nodes) value of the children. The Node class also keeps track the move made to its parents board to generate its own board. There is also the Best. Move property which enables a node to keep track of its best move. Don’t worry about the details now as we will see later how this all works when we do an example. Let’s take a look at the Max. Node and Min. Node classes. This class represents a MAX node in the game tree. The code for Computer. Player is shown below. To get the ball rolling, the. The evaluation function is set and the root node’s Find. Best. Move (recall that this is implemented in the abstract Node class) method is invoked with the default search depth of 3. The first thing done in Find. Best. Move is to check that depth > 0. Since this is the first pass and depth = 3, it enters the if block and the Generate. Children method is invoked and a child node is created for each empty position in the root node’s Board representing all the possible initial moves that the computer can make . Each of these children will be Min. Nodes since their parent is a Max. Node. After the Generate. Children method is called the Evaluate. Children method is invoked, which causes the child nodes to computer their Value. Strictly speaking, the algorithm we described does not call for evaluating the nodes at this point. According to the algorithm, we are only required to evaluate nodes at depth 3 or any terminal nodes (nodes for which there is a completely full board or a board in which one player has won). I’ll go into a little more detail later as to why I chose to evaluate the children now, but for the sake of this example, let us assume that we do not find any winning nodes until we at least complete our tree. Now we use a bit of recursion and for each child that the root node has that node’s Find. Best. Move method is invoked passing along a depth of 2.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. Archives
December 2016
Categories |