Forums: » Register « |  Free Tools |  User CP |  Games |  Calendar |  Members |  FAQs |  Sitemap |  Support |

New Free Tools on Dev Shed!

#1
August 23rd, 2013, 11:29 PM
 Mike Ferashire
Registered User

Join Date: Aug 2013
Posts: 4
Time spent in forums: 49 m
Reputation Power: 0
Invinvible AI issue in Tic Tac Toe

Hello everybody! I was trying to code the game of Tic-Tac-Toe when I encountered a problem. I want to make the AI invincible, however, it is not invincible and places the symbol in the next available position. How can I fix this?

Here is my function codes:

Code:
```void determinMove(char positions[])
{
int num, i, currentBestScore, score;

currentBestScore = -100;

for(i = 0; i < 9; i++)
{
if(positions[i] == ' ')
{
positions[i] = 'X';
score = getFutureScoreOfMove(positions, 'C');
if(score > currentBestScore)
{
num = i;
currentBestScore = score;
}
positions[i] = ' ';
}
}
}
positions[num] = comp;
}```

Code:
```int getFutureScoreOfMove(char positions[], char turn)
{
int i, currentBestScore, score;

if(turn == 'C')                       currentBestScore = -100;
else                                     currentBestScore = 100;

for(i=0; i<9; i++)
{
if(positions[i] == ' ')
{
if(turn == 'C')
{
positions[i] = 'X';
score = getFutureScoreOfMove(positions, 'U');
positions[i] = ' ';
}
else
{
positions[i] = 'O';
score = getFutureScoreOfMove(positions, 'C');
positions[i] = ' ';
}
if(turn == 'C' && score > currentBestScore)
currentBestScore = score;
if(turn == 'U' && score < currentBestScore)
currentBestScore = score;
}
}
return(currentBestScore);
}```

Thank you very much

#2
August 24th, 2013, 02:38 AM
 salem
Contributed User

Join Date: Jun 2005
Posts: 4,266
Time spent in forums: 2 Months 4 Weeks 1 Day 18 h 35 m 56 sec
Reputation Power: 1827
__________________
If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
If at first you don't succeed, try writing your phone number on the exam paper

#3
August 24th, 2013, 02:39 AM
 Triple_Nothing
Contributing User

Join Date: Jun 2009
Posts: 518
Time spent in forums: 5 Days 20 h 41 m 20 sec
Reputation Power: 7
Sorry, I am more into the web programming, but I was just kinda curious about how u saw the AI places its choice randomly. Is it truely randomly, or in order from lowest defined cell to highest, grabbing the next available opening? Just seemed starting your loop at 0 and just adding 1 each time will have it just continue from the beginning and grab first open space.

But I'm not strong in this area, so just a thought...

Last edited by Triple_Nothing : August 24th, 2013 at 12:32 PM.

#4
August 24th, 2013, 04:02 AM
 Mike Ferashire
Registered User

Join Date: Aug 2013
Posts: 4
Time spent in forums: 49 m
Reputation Power: 0
You are right, it is just grabbing the next available move, now that i look at it careful;y. Do you know how i can fix this?

#5
August 24th, 2013, 11:59 AM
 Triple_Nothing
Contributing User

Join Date: Jun 2009
Posts: 518
Time spent in forums: 5 Days 20 h 41 m 20 sec
Reputation Power: 7
Well, at basic, I could just offer next available in sequence w/ your 0-8 and just add 1, or random number n check if empty. As far as invincible, if I'm right, that is ONLY possible if AI goes first, which I hope is not the case. There is a trick where the first player can ALWAYS win, UNLESS the first play of the 2nd player is center(for trick 1). I can't tell you code to help, but in order for AI to make it harder, it will have to find cells currently filled, check which are whose, and generate possibilities and odds to decide its next play.

Just to cover the tricks in Tic-Tac-Toe:
Trick 1...
Human player picks a corner.
As long as AI doesn't play center, next 2 choices of human are usually the 2 corners left open by AI.
This creates an option of 2 possibilities for human to win, and only offering AI 1 move.

Trick 2...
Human player picks center.
AI can play anything.
Next 2 choices of human must just be corners.
Only thing with this is it is not a guarenteed win. There is chance for tie if AI's first 2 choices are corners.

EDIT: And many ask me about trick 1, what if AI's 1st 2 choices are corners as well, not leaving u the option to pick the third? Well, if AI picked 2 corners, as did human, that leaves a valid move for win between the 2 corners that did get selected.

Last edited by Triple_Nothing : August 24th, 2013 at 12:31 PM.

#6
August 24th, 2013, 12:44 PM
 Triple_Nothing
Contributing User

Join Date: Jun 2009
Posts: 518
Time spent in forums: 5 Days 20 h 41 m 20 sec
Reputation Power: 7
And just a thought to help AI decide play, or at least to stop some wins by human, woud be a simple addition. An X or O can hold a numerical value. Then have your script add horizontally, vertically, and diagonal. Make the AI value X/O hold a value to state there's no chance for Human win via that line.

This example may be a bit off from your scripts language, since I'm a web developer, but just some input.
Lets say AI = X and Human = O.
X = 10 and O = 1
A checkLine function can select the 3 cells and add them together.
If total is greater than or equal to 10, then line has an AI mark, so is safe from Human win.
If total is equal to 0 OR 1, then line has no marks or just 1 Human mark, so is safe for now.
If total is equal to 2, then line contains 2 Human marks, and must be AI's next move to avoid its loss to Human via that line.

This won't be invincible, since human can play a trick, and AI will only grab first available item, so Human will just play 2nd for win.

Last edited by Triple_Nothing : August 24th, 2013 at 12:46 PM.

#7
August 24th, 2013, 09:51 PM
 Mike Ferashire
Registered User

Join Date: Aug 2013
Posts: 4
Time spent in forums: 49 m
Reputation Power: 0
THanks for your input. By 'invincible' i mean never lose, and I believe that is possible for the 2nd player

#8
August 25th, 2013, 05:01 PM
 Andy Patterson
Registered User

Join Date: Aug 2013
Posts: 6
Time spent in forums: 2 h 54 m 10 sec
Reputation Power: 0
Long ago I wrote a 3D tic tac toe program.

What I did first was figure the win vectors. In the two dimensional case you have 3 vertical, 3 horizontal and 2 two diagonal for 8 possible wins. You have 9 possible moves each one belong to 2, 3, or 4 win vectors. I made mapping arrays for the win vectors. My 3D tic tac toe version played in a 4 x 4 x 4 cube had 64 possible move locations and 76 win vectors. I made map arrays that mapped a square to a it's win vectors. In your case you have 9 = 3*3 possible moves were I had 64 = 4*4*4. A square in the 3d 4x4x4 could belong to as many as 7 win vectors. In the 2D version the center square belongs to 4 win vectors. I made a 64x8 map array that contained the win vector index 1 to 76, 0 terminator. Your 2 D problem has 8 win vectors. And the squares belong to 2,3 or 4 of the win vectors. The concept is that the mapping is turning the analysis into a single dimensional problem.

To track the win vectors I used a byte array indexed by the win vector. This each byte tracked the occupancy of it's squares. When a move was placed in a square a value of 1 or 8 was added the win vector tracking array. say 1 for x and 8 for O. As X placed moves in a win vector it would be incremented by 1 going form 0 to 4. As O placed moves the value wouud go 8, 16,24,32. Hope you undersand binary. Anding the win table with 0b111000 gave me the number of O's scaled times 8 in that win vector. Anding with 0b111 gave me the number of x in that vector.

The move strategy was to search the winvector array for best move. The first priority was to look for a possible win. The second was to look for a block. So a loop through the win array looking for me having 3 squares and the opponent 0. In the 2D game that would be 2 squares. I could mask off the opponent moves and if not zero I could win in that vector. But the opponent might if they had 3.

That is 24 required a block and a 3 was win.

To select a move

loop through win tracking array looking an unblocked win vectors containing a 3. Opponent having 0 moves in the vector. If opponent has 3 moves and me 0 remember, value 24, forced block, remember it, but keep looking for me win having 3 and opponent 0. If found no single move wins for me. If found a forced block move to block. block it.

The next strategy having not found a win or forced block was to look for intersecting win vectors I had 2 in and opponent none. Looking for a move that creates two wins.

Look if opponent could get a double win and block that.

etc.

I do not remember all of the strategies.

In the 2D version you have 3 win vectors for each corner and 4 for the center square. 2 for the rest. Hope this will help. The last strategy was to choose a square having the highest number of open win vectors. In your 2D case that would be the center square if open.

Andy

#9
August 25th, 2013, 09:38 PM
 Mike Ferashire
Registered User

Join Date: Aug 2013
Posts: 4
Time spent in forums: 49 m
Reputation Power: 0
Thank you Andy, I am using a method similar to what you did now, although I'd still like to learn about the alpha-beta pruning algorithm in more detail.

#10
August 29th, 2013, 03:57 PM
 clifford
Contributing User

Join Date: Aug 2003
Location: UK
Posts: 4,977
Time spent in forums: 1 Month 4 Days 5 h 19 m 41 sec
Reputation Power: 1801
The algorithm (or strategy) to either win or draw at tic-tac-toe is hardly "AI" - its just an algorithm.

#11
August 29th, 2013, 11:44 PM
 Andy Patterson
Registered User

Join Date: Aug 2013
Posts: 6
Time spent in forums: 2 h 54 m 10 sec
Reputation Power: 0
Quote:
 Originally Posted by clifford The algorithm (or strategy) to either win or draw at tic-tac-toe is hardly "AI" - its just an algorithm.

And how is AI not an algorithm?

#12
August 30th, 2013, 02:28 PM
 clifford
Contributing User

Join Date: Aug 2003
Location: UK
Posts: 4,977
Time spent in forums: 1 Month 4 Days 5 h 19 m 41 sec
Reputation Power: 1801
Quote:
 Originally Posted by Andy Patterson And how is AI not an algorithm?
I did not say it wasn't; but existence AI algorithms does not make all algorithms examples of AI.

The optimum strategy for tic-tac-toe is purely mechanistic and deterministic - there is no uncertainty which is what characterises AI - the ability to make decisions from uncertain, noisy, conflicting or fuzzy data or as in the case of tic-tac-toe; unknown future input. AI may involve aspects of planning, learning, knowledge representation, perception, deduction and reasoning - none of which are necessary in this context - the algorithm does not require the computer to anticipate likely future moves for example.

If this were AI, then almost all programming would be AI.

An AI algorthim generalises a problem so that a number of similar but not identical problems can be solved without directly coding the specific solution. The solution to any particular problem is not known a priori by the programmer; the program rather provides the means to determining a solution rather than actually being a direct representation of the the solution.

Last edited by clifford : August 30th, 2013 at 02:31 PM.

#13
August 30th, 2013, 02:33 PM
 salem
Contributed User

Join Date: Jun 2005
Posts: 4,266
Time spent in forums: 2 Months 4 Weeks 1 Day 18 h 35 m 56 sec
Reputation Power: 1827
A true AI should have the capability to learn from past mistakes. Armed only with the rules of the game "place alternate X and 0", and a goal "get 3 symbols in a row", it should 'learn' how to win the game.

For example, you might play "XXX" across the top row, whilst it blindly fires a couple of 'O' around the rest of the board, and it would promptly lose.

At some point, it would spot your "XX" and place a 'O' on the next turn to block the win - this is a learnt step.

If you just code some algorithm, then you get the same response to the same sequence of moves, no matter how many times you play it.

#14
August 30th, 2013, 05:44 PM
 Andy Patterson
Registered User

Join Date: Aug 2013
Posts: 6
Time spent in forums: 2 h 54 m 10 sec
Reputation Power: 0
The term was first coined the in 1955. That's a bit before my time I didn't start programming until 1965. But as defined by John McCarthy, who coined the term in 1955 AI is a system that perceives its environment and takes actions that maximize its chances of success.

A lot of game AI of NPCs are deterministic. It is still called character AI. AI is a blurry term.

Had a bit of fun with DOCTOR an early AI program written in LISP. DOCTOR is a classic AI program. But it does not have a goal to maximize its chances of success. It is simply a program that remembers what you say and asks about them. When you type "MY" something. The "something" is appended to mylist. At random times and points it will output "Lets talk more about (random something from the my list) or respond with "Earlier you said ... (random something from the my list)

We would load up the DOCTOR with info about people we knew. CTRL-C out and save it to a file. That's a feature of TOPS-10 OS. We would then run the program when the person showed up. Most were convinced they were talking to some one on another terminal. This was 40 years ago. AI meant having the appearance of intelligence as the DOCTOR program or the goal oriented problem solving first coined in 1955.

It seams like the TIC TAT TOE game would fall in category one. There is a lot more going on in current AI. But I found nothing that narrowed it definition. It takes actions that maximize its chances of success.

It is simplistic yes. But I have no problem with him calling it AI.

Andy

 Viewing: Dev Shed Forums > Programming Languages > C Programming > Invinvible AI issue in Tic Tac Toe