This is the first project for my AI class. The project was to create an unbeatable Tic Tac Toe game. Took about 4 hours to code, with a few later tweaks to polish the AI.

The State of the Board

The board is represented by a 2-dimensional array, 3x3. The array is initialized for each game with 0's. When the human player or the computer makes a move the related array position is assigned a value. Human moves ( X ) are assigned a 3, computer moves ( O ) are assigned a 4. So if the human moves to the center position on the board the board array assigns 3 to position 1, 1.

Condition for the Possibility of Victory and Defeat

The AI is aware of the conditions of the board through the int findType( int Type ) function. This function initializes an array that represents the lines of the board, one for each row, one for each column, and one for each diagonal, making a total of 8 lines. The values placed in the array are calculated by adding the integer identifiers of the board array positions that fall along that line. The function then returns the first line it finds that is of the desired type, or a not found flag. For example, in the game to the right the top horizontal would have a value of 0 + 3 + 4 = 7, if findType( 7 ) was called the value for the top horizontal line would be returned. All possible line arrangements have a unique value. These flags allow the AI to know the conditions of the board and what action is appropriate. The bool CheckWin( int X, int Y ) function checks to see if a human or computer move has satisfied the conditions to win with their turn and also increments the turn counter. This is done by calling the findType function for line types 9 and 12. CheckWin also identifies if all moves have been made and the game is a tie.

Why Resistance is Futile

When the computer looks for a move it starts by initializing variables X and Y to any random combination that is currently empty. The AI then looks for a position that would allow it to win on this turn and end the game with a victory. The only line that satisfies that condition is OO with a value of 8. If no lines will allow a win this turn the AI looks for a line that would allow to human player to win on their next turn, the only line that satisfies that condition is XX with a value of 6. If a move is found the AI identifies which position is empty in the line and sets X and Y to those values.

If there is no chance of victory or defeat this round the AI checks for a line type it knows allows the human player to get two potential win lines in a turn and thereby defeat the computer. This line type is XXO on the diagonal, with O in the center position. If this is the case the computer sets X and Y to a side position so that the human must prevent the computer from winning and can't grab the third corner. If that line condition does not exist the computer sets X and Y to one of the corners since they allow for the most possible win combinations. Finally the AI checks to see if this is the second turn and if the center is open - if so it preempts another strategy by setting X and Y to the center position. The computer then uses the final values for X and Y and moves to those coordinates on the board.

Tempting Fate

When the game is first loaded all buttons are disabled. To start a game go to File>New . The game will randomly select if you or the computer goes first. The bottom of the game window will tell you when it is your turn. To make a move click the appropriate button. When a game has ended the buttons are disabled and � You Win! �, � You Lose! � or � Tie Game! � is displayed. Exit or start a new game at any time from the File menu.

Another project for my AI class. This program generates random mazes and then solves them using either a depth first or breadth first search.

The Maze Silo

The storage of a maze begins with the click of the 'Generation' button. A maze is generated by first parsing the user input. The input is then used to initialize the Maze object, this involves creation of an array of Cell objects, initializing each cell in the maze, and selecting a random cell as the first cell. Each cell knows its location in the maze, the state of its walls, and how to draw itself. For the solution, a cell knows if it was a part of the solution path, and which cell was previous to it in making the solution path.

To Make a Maze

The generation is done with a depth first based algorithm. The generation loops until each cell in the maze has been visited, the current cell is asked to find any neighbors it has that still have all their walls. If the cell has no such neighbors then that route has dead ended and a stack of cells that were visited to get to that particular cell is popped and the cell from the stack is checked to see if it has a neighbor that satisfies those conditions. When a cell has been found that has neighbors who have all their walls then a random neighboring cell from that list of neighbors is selected. The wall between the two cells is knocked down, the current cell is pushed to the stack, and the selected cell is made the current cell. If the new cell has not been visited it is set as visited and the visited cell count is incremented.

To Make the Perfect Imperfect

The mazes generated with the above algorithm have no loops and are always solvable. Placing a positive integer value in the Loop Percent or Block Permille field alters the way a maze is generated slightly. The Loop Percent is used to randomly select walls that are being knocked down as the generation moves through the maze and set the wall as down, but perceived to be up by neighboring cells. So when a cell asks a neighbor if it has all its walls it will report that it does even when one or more walls are already down. The Block Permille works in a similar fashion. It sets the chance that as walls are being knocked down a wall will be left up instead, but the generation algorithm will continue moving forward from that point as if the wall had been knocked down.

To Solve or Not to Solve

The DFS works a lot like the generation algorithm. It looks until it has either found the solution, or the solve stack is empty and the current cell has no unvisited cells to move to. The solver is started with the 'Start' position cell, the cell is set as visited. The cell finds which of its neighbors it can be moved to and has not yet been visited. One of these cells is randomly selected. The current cell is pushed onto the stack, the selected cell is made the current cell and it is marked as visited. The process continues until a cell with no unvisited neighbors is found, then the stack is popped until a cell with unvisited neighbors is found. If the maze cannot be solved all cells that were visited during the solve attempt are displayed. If the maze is solved the cell stack is popped and each cell in the stack is marked as part of the solution.

The BFS operates using a queue. The start cell is placed in the queue. While there are still cells in the queue and the solution has not been found the search continues. The cell finds all its unvisited neighbors and places each of them in the queue, each of these cells gets there PreviousCell reference set to the cell that added them to the queue, and they are marked as visited. The solver then dequeues the next cell and repeats the process. If no solution is found then all cells that were visited are displayed. If a solution is found the solution cell is taken and each cell in the list formed by the PreviousCell references is marked as part of the solution.

The BFS will always find the shortest solution, and generally does so faster than the DFS. Since the DFS randomly chooses among unvisited neighbors it will find different paths with each solve, if they exist.

When Drawing a Maze

A new bitmap is constructed using the dimensions of the maze multiplied by the size of each cell. The size of the picturebox that will hold the bitmap is then adjusted, if it is larger than the viewing area scroll bars automatically are added. A graphics object is created from this bitmap, which is then passed to the Maze object. The Maze loops through each cell and tells it to draw its walls, etc. using the graphics object. A cell first draws a filled rectangle if it is part of the solution, it then draws a line for each of its walls that are still up. When the process is complete the fully drawn bitmap is set as the image for the picturebox.

This is a project I did for a Topics class. Project was to design a an elevator simulator as a practice in OOD. Here is a bit of the documentation on how to use the program:

Time is kept track of in the upper left textbox, to the right is the time the next person will arrive at the given floor. The interval may be set before simulation starts or during simulation, as can the min and max person intervals. Stopping the simulator resets everything except to output textbox. The simulation can be paused and resumed during simulation.

When a person pushes one of the floor or the elevator buttons the button lights up to show that it has been pressed. The light (to the right of the floor buttons) lights up when the elevator is at a floor.

SMPVM Documentation �

When the VM is run it will ask for manual input of a program, manual input is finished by entering a line with an op code of 99, the VM will then load the program and attempt to run it. If the user puts a VM machine code filename as an argument the VM will attempt to load that file and run it.

The VM loader checks to make sure that each machine code line is within expected range, 10000-99999. Machine code files have the following structure:

While the program is running the VM will report if an invalid op code is found and provide the line that the error occurred on. If the stack decrements into the registers or overruns code the program will terminate and an error will be generated. If any errors are generated memory is dumped to the file error.txt . A * will be placed next to the line that the program halted on. During the execution of a program input lines are preceded by a question mark.

This is an enhanced version of the Line Counter program I wrote to keep track of the Yserbius project's progress. This version has the option to show the line counts in a window when run, and adjust many aspects of what information to display and how.

To get to the menu to adjust the settings click on the text area of the counter. If the display of the line counter has been disable either run the application with an argument (ie LineCounter -a) or delete the settings file. All settings are stored in an XML document, so you can manually adjust the settings as well.

Opacity, Font, and Colors only effect the display of the LineCounter application, not its output file.

Output is placed inside of preformatted tags (<pre>). If ColdFusion is selected then the output is placed inside of a CFSET. The output can be included in your web page with any kind of server side include.