Category Archives: EPGY Projects

Project “Ultimate Tic Tac Toe”

  1. Abstract

The popularity of the intellectual, addicting game, Ultimate Tic Tac Toe, is rising exponentially, yet the game lacks a sophisticated artificially intelligent computer player to challenge human players. At the Artificial Intelligence course in EPGY, I worked on a novel approach to the AI for Ultimate Tic Tac Toe. Instead of making computers act like humans, I was inspired to make computers THINK like humans by allowing them to learn from past experiences, which is the concept of case based reasoning. Human intelligence is not defined by what humans know; it is defined by “how” we know. My goal is to replicate true human intelligence through implementing case based reasoning on this game. By completing this project, I hope to expand the case based reasoning’s range of application and contribute new ways to implement case based reasoning.

2. Background on Case Based Reasoning

In order to create the most intelligent artificial system for a game, one must consider what makes the computer’s opponent, the human, a worthy adversary. Above all other human capabilities, the ability to learn from experiences makes humans the most intelligent life forms. My purpose is to replicate this behavior and thought process in a computer bot so that it will grow in intelligence after every game.

The primary process in case based reasoning is the 4 R’s: retrieve, reuse, revise, and retain. In a current situation, the computer player will first retrieve, or examine actions in similar past experiences. After accumulation of past experiences, the computer will mutate the past experience (reuse and revise) in order to make it fit in the current situation. If the action in the current situation was successful, then the action will be retained, and recorded as a successful past experiece. As this cycle iterates, a computer player will become more and more intelligent after every consecutive game it has played.

4rs

3. Application- What is Ultimate Tic Tac Toe?

Ultimate Tic Tac Toe is defined as a 3×3 Tic Tac Toe game in which each square has its own tic tac toe game.

tictac

The picture above best describes the gameboard for this game. A comprehensive guide to the rules of this game can be found in here (http://mathwithbaddrawings.com/2013/06/16/ultimate-tic-tac-toe/). The rules of the game make it very intellectual and thus, very addicting. Therefore, creating a bot with learning capabilities for such a complicated game is a novel proposition.

4. Previous Work in Case Based Reasoning

To create computer bots for the artificial intelligence Starcraft conferences, many teams implement case based reasoning so that their computer player can use tactics from its previous opponents and battles in order to succeed in its current situations. Also, corporations such as Verdande technology use case based reasoning in their products. Their data mining product, Edge Platform, uses previous problems and solutions to tackle current situations. Even though this product is used broadly across various fields, the computer can find similarities between situations of different clients and perform optimally.

Edge_Platform

5. Current AI in Ultimate Tic Tac Toe

Ultimate Tic Tac Toe applications on the web most commonly have random, unintelligent computer players. There is one on the khan academy website that uses a monte carlo search tree (MCST) to make moves. MCST evaluates every next move by simulating games that would occur after each move. Then the computer player chooses the next move that guarantees the most amount of future optimal results. This implementation allows the computer to think in advance and makes moves accordingly.

mcst

However intelligent this gameplay might seem, this does not prevent the computer player from making mistakes over and over again. If a computer player isn’t able to use case based reasoning to learn from experiences, a human player may exploit this discrepancy and be able to beat the computer player every time by  making the computer make the same mistake every time. The current AI for Ultimate Tic Tac Toe doesn’t significantly challenge human players and becomes very easy to beat after exploitation.

6. Proposed Solution

I set up a localhost MySQL server in order to record each game in a table within a single database. With the JDBC driver, I am able to connect my JAVA application to the MySQL server during a game. After I access all the data from my previous games, I sort through the moves and only analyze the winner’s moves from each game. After playing the game several times, I realized that the game strategy and technique changes at different points of the game. Furthermore, human players prioritize which square to play in depending on their depth into the game. Therefore, I divide each game into three equal sections and classify each move into the section of the game that it was played in. Then, I took these three individual clusters of moves and created a probability model for each cluster. The computer player would then apply one of these models depending on the computer player’s depth into the current game. I decided to use a probability model to create a dynamic computer player because dynamic gameplay is hard to exploit since it is unpredictable. Plus, this gives the human player the feeling that it is playing against a sophisticated, human-like bot.

mysql

Shows the localhost MySQL server I used to save past game experiences.

7. Conclusion

The bot for my game is just like the camel in this old proverb. I, the camel owner, had given the camel all the resources and wisdom to guide it to the water, but only the camel could decide if it wanted to drink water or not. I had given the AI bot a myriad of experience and the ability to cleverly analyze, yet would my bot use the resources to play better or fail? The artificially intelligent bot was extremely bad player after playing one or two games, but after it got more and more experience under its belt, it played with more sophistication and demonstrated a greater understanding for the game.  It even inherited tactics and strategies from previous players and implemented them in its future gameplay. The probability model made it impossible to exploit and an even more worthy adversary for the human player. Players for this game comment that it was much more challenging than the MCST computer player for this game.

exampleWin

The computer player (O) defeats one of my friends (X)

8. Future Work

I hope to implement alpha-beta pruning or MCST to the computer player so that I can create a Perfect Bot that will use both foresight and hindsight to become an extremely difficult player to beat. I am also looking forward to specify the classification of the previous games’ data, and implement markov chains in order to create smarter and more specific probability models. Above all, I hope to release a free version of this game on the Android market.

9. References

http://en.wikipedia.org/wiki/Case-based_reasoning

http://artint.info/html/ArtInt_190.html

http://www.youtube.com/watch?v=87FhSfvOiwU

http://www.verdandetechnology.com/home/products-and-services/edge-platform/

https://www.khanacademy.org/cs/in-tic-tac-toe-ception-perfect/1681243068

Tagged , , , , , ,

Get even faster with ASP

 

Answer Set Programming is logic-based syntax such as Prolog, except it runs much faster. It does not have user input components or abilities to read or write to files. ASP’s and Prolog’s syntax is relatively the same even though they use relatively different technology.

In this project, I was given a program and had to terminate the fluent(heat).  Fluent is an event that has a fickle status that can happen, or terminate. You can check out my code under my Pastebin portfolio (link is in the Links page above) in the paste “Turn off the heat.” I used the following link to run the program  http://chapaai.adamsmith.as:8118/

After so much time with imperative and OO programming, ASP gives us a taste of no control flow and declarative programming. It expedites the process of creating projects too because I don’t have to create objects, classes, etc. This language makes it very easy to initiate environment and states if one is able to simplify any project to a collection of boolean arguments.

As you can see below, the heat is showing negative values after time T =5 when I initiated the event, air conditioning.

Tagged , ,

Dipping into Prolog

How could I have continued to SQL without looking at the prolog? (hahaha)

Prolog is a logic-inspired programming language that is used for game artificial intelligence, such as story generation and level generation. In my project with Prolog, I used abduction reasoning to create the following situation: The dining hall has chocolate ice cream, but not vanilla. I also made it understand family hierarchy. You can see my work in Prolog in my Pastebin link on the Links page above!

The statements after the “:-” has to be initiated in order for the statements before the “:-” to be initiated. After I initiated the dining hall as a place, it inherited characteristics from the statements preceding it. I ran prolog using this application here: http://waitaki.otago.ac.nz/~michael/wp/

I’m hoping to learn more prolog with this neat tutorial: https://www.csupomona.edu/~jrfisher/www/prolog_tutorial/contents.html

Image

Tagged ,

Image Recognition – KM Clustering

On famous apps such as Hot or Not, the program judges the hotness of a person based on the aesthetic value from a picture of that person. Programs like this use KM clustering at the base level to categorize similar pixels.

I implemented KM clustering to give fancy, instagram-like effects to any picture. This program allows the user to enter in several “seed pixels,” and every pixel in the image will be grouped with the seed pixel that has the closest color. I used an algorithm similar to the kNN classification project to group the pixels into clusters. Then I took the average color value of all the pixels in each cluster and applied it to all the pixels in that cluster. Repeating the above steps around 20 times will drastically change the coloring of the picture, yet the picture features will still be preserved.

original picture of obama

original picture of obama

after 3 iterations

after 3 iterations

red, white, and blue obama after 20 iterations

red, white, and blue obama after 20 iterations

From this project, I really enjoyed how I could reuse skills and techniques from past projects in order to save time!

Tagged , ,

kNN Classifier tackles Big Data

Today I created a kNN (k-Nearest Neighbor) classifier, which classifies instances based on their similarity to instances in the training data. For instance, we were given data points with three dimensional coordinates and each data could have a label of a one or a zero. Given more data points, my job was to label them with a one or zero. Since the one labels clustered with each other and the zeros clustered with each other, I made a method which checked the “k” closest data points (k being a constant) to the unlabeled data point. I used the 3-D distance algorithm and a bubble sorting algorithm to find the closest points. The unlabeled data point then inherited the majority label value of the “k” closest points.

The kNN classifier is a type of data mining tool that tackles the conundrum of Big Data!

Tagged , ,

EPGYTraveler

I created an algorithm to find the shortest path to go through all the points on a map. The points on the map were the hometowns of the students in our class. I used a recursive method to create a brute force algorithm, where I found all the possible paths that one could take through all the points and collected the distances of the paths. I then parsed through these distances to find the shortest one! The algorithm is still under revision, but in theory, it works! It was intriguing to see how students at EPGY are from everywhere around the world.

Imaget

Tagged , , ,

Lisp Computer Programming

The code below shows common functions executed through lisp, a declarative programming language. One reason that Lisp is used for Artificial Intelligence is that it is an excellent prototyping tool. Also, Lisp supports symbolic programming well. Old AI was also symbolic. In addition, the code/data distinction in lisp is weaker so it feels more extensible than other languages because your functions and macros look like the built-in stuff (Stack Overflow).

(write-line “Hello World”)
(defun add (X Y)
“Compute three times X.”
(+ Y X))

(print (add 3 3)) ; Display that function with 4 as a param

(defun subtract (X Y)
“Compute three times X.”
(- X Y))

(print (subtract 4 3)) ; Display that function with 4 as a param

(defun multiplication (X Y)
“Compute three times X.”
(* X Y))

(print (multiplication 3 3)) ; Display that function with 4 as a param

(defun factorial (n)
(if (<= n 1)
1 ; returns 1 once you go through all the numbers
;hidden else statement here
(* n (factorial (- n 1)))))

(print (factorial 5))

Tagged ,

Project Proposal

What is the specific area you are working within?

I am working with many implementations of decision trees, such as markov chains and random forests. I will also work with reactive planning and case-based artificial intelligence.

What is it that you would like to learn about it?

I would like to learn how to use MySQL databases achieve case-based AI, so that the computer player can actually learn from his experience. I also want to create a player that follows multiple playing styles and not follow a strict decision tree.

Why is this interesting to you?

It is very interesting because I really want machines to act like humans and gain experience as they play!

Why should other people care?

Because the game to which I’m applying these artificial intelligence algorithms is highly intellectual.

What are the practical applications of this topic?

We can be one step closer to making machines “think” like humans.

What is the closest example (researched from the web) of what you want to build or investigate?

It is called Ultimate Tic Tac Toe, where there is a 3×3 Tic Tac Toe game and each square has its own 3×3 Tic Tac Toe game in it.

What do I want to accomplish?

I want to create a Java application of Ultimate Tic Tac Toe that will allow one player to play with an artificially intelligent computer player.

Obstacles

I’m going to need a little guidance in how to utilize data from my databases to allow the computer to learn from its past opponents and its previous mistakes.

What tools am I using

MySQL databases, Eclipse and maybe VSphere Client and an ESXi license

Tagged , , , , ,

VisualSort

This program is able to sort rectangles from shortest to longest. It will generate rectangles with random lengths in a random order and use bubble sort to organize the rectangles.Image

EPGY Draw

In this project, we created an drawing canvas program that can draw multiple shapes on a drawing board using Graphics. I was very interested in figuring out how to create an ellipse once the mouse goes to the left or above the initial starting position of the shape, so I created an algorithm for that.Image