Building a computer into tic tac toe

Programming Questions

sihingsin

Building a computer into tic tac toe

in Programming Questions • 8 months ago

Hello everyone,

I tried to build the game tic tac toe in the last few weeks and am now trying to challenge myself and my skills.

I finished tic tac toe in the sense, that two people can play it when on the same computer, but in my opinion a good game needs a singleplayer modus. So with that in mind I have a few questions.

First of all this is my code so far:

PImage bkgd;
PImage xp;
PImage op;
PFont arial;
int turn;
int[]grid = new int[9];
void setup(){
size(600,600);
bkgd = loadImage("noughts.png");
xp = loadImage("x.png");
op = loadImage("o.png");
image(bkgd,0,0);
for (int i=0;i < grid.length;i++){
grid[i] = 0;
}
turn = round(random(1));
arial = createFont("Arial", 32);
textFont(arial, 50);
}
void draw(){
if ((grid[0] == 1 && grid[1] == 1 && grid[2] == 1) || (grid[3] == 1 && grid[4] == 1 && grid[5] == 1) || (grid[6] == 1 && grid[7] == 1 && grid[8] == 1) || (grid[0] == 1 && grid[3] == 1 && grid[6] == 1) || (grid[1] == 1 && grid[4] == 1 && grid[7] == 1) || (grid[2] == 1 && grid[5] == 1 && grid[8] == 1) || (grid[0] == 1 && grid[4] == 1 && grid[8] == 1) || (grid[6] == 1 && grid[4] == 1 && grid[2] == 1)){
fill(255,0,0);
text("'X' WINS",200,300);
noLoop();
}
if ((grid[0] == -1 && grid[1] == -1 && grid[2] == -1) || (grid[3] == -1 && grid[4] == -1 && grid[5] == -1) || (grid[6] == -1 && grid[7] == -1 && grid[8] == -1) || (grid[0] == -1 && grid[3] == -1 && grid[6] == -1) || (grid[1] == -1 && grid[4] == -1 && grid[7] == -1) || (grid[2] == -1 && grid[5] == -1 && grid[8] == -1) || (grid[0] == -1 && grid[4] == -1 && grid[8] == -1) || (grid[6] == -1 && grid[4] == -1 && grid[2] == -1)){
fill(255,0,0);
text("'O' WINS",200,300);
noLoop();
}
}
void mousePressed(){
x();
o();
}
void keyPressed(){
if (key == 'r'){
image(bkgd,0,0);
for (int i=0;i < grid.length;i++){
grid[i] = 0;
}
turn = round(random(1));
arial = createFont("Arial", 32);
textFont(arial, 50);
loop();
}
}
void x(){
if (mouseButton == LEFT){
if (mouseX > 0 && mouseX < 200 && mouseY > 0 && mouseY < 200 && grid[0] == 0 && turn == 1){
image(xp,50,50);
grid[0] = 1;
turn = 0;
}
if (mouseX > 0 && mouseX < 200 && mouseY > 200 && mouseY < 400 && grid[1] == 0 && turn == 1){
image(xp,50,250);
grid[1] = 1;
turn = 0;
}
if (mouseX > 0 && mouseX < 200 && mouseY > 400 && mouseY < 600 && grid[2] == 0 && turn == 1){
image(xp,50,450);
grid[2] = 1;
turn = 0;
}
if (mouseX > 200 && mouseX < 400 && mouseY > 0 && mouseY < 200 && grid[3] == 0 && turn == 1){
image(xp,250,50);
grid[3] = 1;
turn = 0;
}
if (mouseX > 200 && mouseX < 400 && mouseY > 200 && mouseY < 400 && grid[4] == 0 && turn == 1){
image(xp,250,250);
grid[4] = 1;
turn = 0;
}
if (mouseX > 200 && mouseX < 400 && mouseY > 400 && mouseY < 600 && grid[5] == 0 && turn == 1){
image(xp,250,450);
grid[5] = 1;
turn = 0;
}
if (mouseX > 400 && mouseX < 600 && mouseY > 0 && mouseY < 200 && grid[6] == 0 && turn == 1){
image(xp,450,50);
grid[6] = 1;
turn = 0;
}
if (mouseX > 400 && mouseX < 600 && mouseY > 200 && mouseY < 400 && grid[7] == 0 && turn == 1){
image(xp,450,250);
grid[7] = 1;
turn = 0;
}
if (mouseX > 400 && mouseX < 600 && mouseY > 400 && mouseY < 600 && grid[8] == 0 && turn == 1){
image(xp,450,450);
grid[8] = 1;
turn = 0;
}
}
}
void o(){
if (mouseButton == RIGHT){
if (mouseX > 0 && mouseX < 200 && mouseY > 0 && mouseY < 200 && grid[0] == 0 && turn == 0){
image(op,50,50);
grid[0] = -1;
turn = 1;
}
if (mouseX > 0 && mouseX < 200 && mouseY > 200 && mouseY < 400 && grid[1] == 0 && turn == 0){
image(op,50,250);
grid[1] = -1;
turn = 1;
}
if (mouseX > 0 && mouseX < 200 && mouseY > 400 && mouseY < 600 && grid[2] == 0 && turn == 0){
image(op,50,450);
grid[2] = -1;
turn = 1;
}
if (mouseX > 200 && mouseX < 400 && mouseY > 0 && mouseY < 200 && grid[3] == 0 && turn == 0){
image(op,250,50);
grid[3] = -1;
turn = 1;
}
if (mouseX > 200 && mouseX < 400 && mouseY > 200 && mouseY < 400 && grid[4] == 0 && turn == 0){
image(op,250,250);
grid[4] = -1;
turn = 1;
}
if (mouseX > 200 && mouseX < 400 && mouseY > 400 && mouseY < 600 && grid[5] == 0 && turn == 0){
image(op,250,450);
grid[5] = -1;
turn = 1;
}
if (mouseX > 400 && mouseX < 600 && mouseY > 0 && mouseY < 200 && grid[6] == 0 && turn == 0){
image(op,450,50);
grid[6] = -1;
turn = 1;
}
if (mouseX > 400 && mouseX < 600 && mouseY > 200 && mouseY < 400 && grid[7] == 0 && turn == 0){
image(op,450,250);
grid[7] = -1;
turn = 1;
}
if (mouseX > 400 && mouseX < 600 && mouseY > 400 && mouseY < 600 && grid[8] == 0 && turn == 0){
image(op,450,450);
grid[8] = -1;
turn = 1;
}
}
}

As you can see I haven't started the computer yet. My problem is that I don't want to start and after that notice that I did way too much work.

I thought about making the computer finish a line if it has already two of its own in there.

if ((grid[0] + grid[1]) == -2 && turn == 0){
image(op,50,450);
grid[2] = -1;
turn = 1;
}

As you can see my try is not really efficient as I had to code the same thing for every possible combination of two. My question now is, if there is an easier way to do the whole thing.

Thanks for any help!

Sincerely SihingSin

Replies(14)

Chrisir

Re: Building a computer into tic tac toe

8 months ago

this is your game board:

int[]grid = new int[9];

a win is possible
with fields

0,1,2
also
0,3,5
also 0,4,8
etc.

OK.

So, now you can make a new array "the possible fields to win on" and for loop over them.
Each position contains 3 numbers which are 3 fields of your board.

BTW
You can first check: can the computer win.
Then check, can the player win. If so computer must hinder him or her.
Then check if he can make a fork etc.
see http://en.wikipedia.org/wiki/Tic-tac-toe

Random
It is worthy to have one computer-AI you are working on. Have another AI that plays random (search all empty fields and randomly choose one of them).
Let those two (AI and random) play against each other. When you play 2000 games (20 seconds) and your AI is good, it must never loose.
I found this a very good way of testing the AI.

Greetings, Chrisir

sihingsin

Re: Re: Building a computer into tic tac toe

8 months ago

Thanks a lot for your response. I was planning to do the same steps you mentioned, but my first problem is if I can make my try on top more compact.

a win is possible
with fields

0,1,2

also

0,3,5

also 0,4,8

OK.

So, now you can make a new array "the possible fields to win on" and for loop over them.
each position contains 3 numbers which are 3 fields of your board.

You said that I can make an array for the winning conditions. These are all possible combinations for one to win the game:

if ((grid[0] == 1 && grid[1] == 1 && grid[2] == 1) || (grid[3] == 1 && grid[4] == 1 && grid[5] == 1) || (grid[6] == 1 && grid[7] == 1 && grid[8] == 1) || (grid[0] == 1 && grid[3] == 1 && grid[6] == 1) || (grid[1] == 1 && grid[4] == 1 && grid[7] == 1) || (grid[2] == 1 && grid[5] == 1 && grid[8] == 1) || (grid[0] == 1 && grid[4] == 1 && grid[8] == 1) || (grid[6] == 1 && grid[4] == 1 && grid[2] == 1)){
fill(255,0,0);
text("'X' WINS",200,300);
noLoop();
}
if ((grid[0] == -1 && grid[1] == -1 && grid[2] == -1) || (grid[3] == -1 && grid[4] == -1 && grid[5] == -1) || (grid[6] == -1 && grid[7] == -1 && grid[8] == -1) || (grid[0] == -1 && grid[3] == -1 && grid[6] == -1) || (grid[1] == -1 && grid[4] == -1 && grid[7] == -1) || (grid[2] == -1 && grid[5] == -1 && grid[8] == -1) || (grid[0] == -1 && grid[4] == -1 && grid[8] == -1) || (grid[6] == -1 && grid[4] == -1 && grid[2] == -1)){
fill(255,0,0);
text("'O' WINS",200,300);
noLoop();
}

How would you put this into an array?

My main thing to ask though if you can make the possibilites for one to win in the next move more compact. I only know the way through making an if condition for every possible win with the next move, which are a lot. If there was a way to make that more compact using an array or any trick you have up your sleeve. It would make my work way easier and efficient.

Thanks for any help!

Sincerely SihingSin

Chrisir

Re: Building a computer into tic tac toe

8 months ago

well you can make an object

oneWinningLine

which has

int field1
int field2
int field3

now you have an array of those: arrayWinningLines.

Now you can fill it

"012", "345", "678", "036", "147", "258", "048", "246"

Then your checks are easier:
for-loop arrayWinningLines to check whether somebody won:
xWon = false;
if (arrayWinningLines[i].field1 = "x" && arrayWinningLines[i].field2 = "x" && arrayWinningLines[i].field3 = "x")
{
xWon = true;
}

sihingsin

Re: Re: Building a computer into tic tac toe

8 months ago

I never created an object, so I have no clue what you mean by that. Could you explain to me how you do that?

Sincerely SihingSin

Chrisir

Re: Building a computer into tic tac toe

8 months ago

yes, see

http://www.processing.org/learning/objects/

sihingsin

Re: Re: Building a computer into tic tac toe

8 months ago

Can you make an example of an object? The explanation is on the website is very hard to understand for, but also I don't really know how to use the knowledge they are trying to give to me.

Sincerely SihingSin

asimes

Re: Building a computer into tic tac toe

8 months ago

Tic Tac Toe has a small game tree, but there still are over 200,000 possible games to consider on the first turn. Getting an AI to play correctly by making a response to any state of the board is not really the best way to go about designing one. Even if the logic is more along the lines of "Play the winning move if there are already two in a row" or "Stop the opponent's win by blocking if there are two in a row" the AI will still lose to forks where the opponent has two ways to win in one turn.

Generally when people write an AI for a game like this they use the Minimax Algorithm to create a game tree of all the possible games that could happen based on the current state of the board. For Tic Tac Toe, the game tree looks like this:

Note, the image above is a simplification, the first node should really have nine lines for everywhere a X could go, each child node should have eight lines for everywhere an O could go, etc. Basically what is going on is every possible game that could be played is being generated. For each node you expand all the possible things that could happen until a player wins or it is a draw. Then your AI looks at all the possible things that could happen and picks the best one. The explanation on how to do this is too long for a post here, but Google or YouTube searches on Minimax should provide the help needed to get started.

sihingsin

Re: Re: Building a computer into tic tac toe

8 months ago

My goal is not to create a perfect computer, but one that is working and nice to play against. Forks are of course a way to trick a not perfect computer, but my goal is to make the computer run after the following algorithms:

1. Is there a possibility for me to win with this move?

2. Is there a possibility for the opponent to win with his next move?

3. Can I play to the middle square?

4. Can I place next to another one of mine?

5. Can I take a corner?

6. Take any leftover square.

I want to leave forks out for the first place, since this is just a training for me. It doesn't have to be perfect, but I want to gain knowledge on that topic.

Thank you very much for your reply though.

Sincerely SihingSin

Chrisir

Re: Building a computer into tic tac toe

8 months ago

The game is in both concepts much more complicate than one would expect.

I personally find both concepts complicate:

logic more along the lines of "Play the winning move if there are already two in a row" or "Stop the opponent's win by blocking if there are two in a row" the AI will still lose to forks where the opponent has two ways to win in one turn.
Minimax Algorithm

asimes

Re: Building a computer into tic tac toe

8 months ago

sihingsin, then best of luck, making a clever computer that is not perfect is almost just as involved. Tic Tac Toe is a game with 4 fold symmetry, I would strongly recommend using that to your advantage when making your logic.

Chrisir, there are tricks in Tic Tac Toe that are almost impossible to code against without having the AI look to the future before it makes a move. For example, in this state:

X has already lost! If O plays at the bottom-left, X is forced to block at the top-right, and then O can play at the center-left creating a fork. The complication is just part of playing Tic Tac Toe well, these kinds of traps have to be avoided by searching.

Chrisir

Re: Building a computer into tic tac toe

8 months ago

Can you make an example of an object?

here...

WinningLine[] arrayWinningLines = new WinningLine[9];
void setup() {
arrayWinningLines[0] = new WinningLine (0, 1, 2); // ---
arrayWinningLines[1] = new WinningLine (3, 4, 5); // ---
arrayWinningLines[2] = new WinningLine (6, 7, 8); // ---
arrayWinningLines[3] = new WinningLine (0, 3, 6); // | from top down
// etc.
for (int i=0; i < 4; i++) { // arrayWinningLines.length
println( arrayWinningLines[i].field1 + " - " +
arrayWinningLines[i].field2 + " - " +
arrayWinningLines[i].field3 );
}
}
void draw () {
//
}
// ==================================================
class WinningLine {
int field1;
int field2;
int field3;
WinningLine (
int field1_,
int field2_,
int field3_ )
{
field1=field1_;
field2=field2_;
field3=field3_;
}
} // class
//

Chrisir

Re: Building a computer into tic tac toe

8 months ago

@asimes: Thank you! I still think a not perfect program following some rules is easier to program than a Minimax Algorithm for a quite beginner.....

I once tried Minimax Algorithm with chess and couldn't quite get it to work...

asimes

Re: Building a computer into tic tac toe

8 months ago

It is tricky, but I learned it myself by asking for help on this forum :)

Chrisir

Re: Building a computer into tic tac toe

8 months ago

@ sihingsin:

you might want to look at

http://www.wikihow.com/Win-at-Tic-Tac-Toe

also in the wikipedia article is a rule set to win afaik

http://en.wikipedia.org/wiki/Tic-tac-toe#Strategy