Go Back  Xtreme Visual Basic Talk > Legacy Visual Basic (VB 4/5/6) > Game Programming > Unbeatable Tic Tac Toe Opponent


Reply
 
Thread Tools Display Modes
  #1  
Old 10-15-2001, 10:31 AM
semmons99
Guest
 
Posts: n/a
Question Unbeatable Tic Tac Toe Opponent


I am making a Tic Tac Toe program in VB. So far I have it so that two players can play against one another and one player can play against a relatively promative AI. I am now tying to work on creating an AI that is unbeatable. Does anyone have any ideas on where I should go with this code next? So far I have the computer check to see if it can complete a three in a row anywhere on the board. Here is the code. If you can help it would be appreciated.
Reply With Quote
  #2  
Old 10-15-2001, 10:41 AM
Banjo's Avatar
Banjo Banjo is offline
Hell's Angel

Retired Moderator
* Guru *
 
Join Date: Jul 2001
Location: Yorkshire, UK
Posts: 10,394
Default Re: Unbeatable Tic Tac Toe Opponent

You need to prevent the player from getting to the postion of having two possible lines of three. E.g:
<pre>
0 | | 0
----------
| x |
----------
0 | | x</pre>
If it gets to this situation (there are other ones) then x can not win. you must prevent the player from doing this.

Note that you will not be able to produce an AI that can win everytime. In Tic Tac Toe it is impossible for either side to win if they both make logical moves. The best you can hope for regularly is a draw.
__________________
A wise one man once said "what you talking about dog breath"
Reply With Quote
  #3  
Old 10-15-2001, 03:38 PM
Garrett Sever's Avatar
Garrett Sever Garrett Sever is offline
Strange Brewer

Retired Moderator
* Guru *
 
Join Date: Jun 2001
Location: AddressOf Insomnia
Posts: 2,815
Default Re: Unbeatable Tic Tac Toe Opponent

Anybody ever see War Games w/ Matthew Broderick?

Yeah, ancient, but it makes this very point.

"Shall we play a game?"
__________________
"The lights below
You know they'll bleed forever
Get back as the cores blow
Let me fall..." - Dismantled, "Cornered"
Reply With Quote
  #4  
Old 10-15-2001, 05:15 PM
orufet's Avatar
orufet orufet is offline
Paranoid Coder

Retired Leader
 
Join Date: Mar 2001
Location: Canada
Posts: 2,716
Default Re: Unbeatable Tic Tac Toe Opponent

Yeah, I saw that movie years ago....Pretty good, but, as you said, quite old...
Reply With Quote
  #5  
Old 10-15-2001, 06:53 PM
Banjo's Avatar
Banjo Banjo is offline
Hell's Angel

Retired Moderator
* Guru *
 
Join Date: Jul 2001
Location: Yorkshire, UK
Posts: 10,394
Default Re: Unbeatable Tic Tac Toe Opponent

Yeah, it had a wonderful menu along these lines:

1) Pong
2) Tic Tac Toe
3) Global Thermonuclear War
:

So what do you press; 3 of course! [img]images/icons/smile.gif[/img]
__________________
A wise one man once said "what you talking about dog breath"
Reply With Quote
  #6  
Old 10-22-2001, 05:32 PM
Cryostasis Cryostasis is offline
Junior Contributor
 
Join Date: Oct 2001
Location: North Wales
Posts: 218
Default Re: Unbeatable Tic Tac Toe Opponent

I'm writing an AI at the moment for tic tac toe, and I first started with loads of if statements prioritising in winning, avoiding 2 way traps, defending, etc respectively. I've now nearly finished one that actually 'evolves' it's own perfect ai in a couple of munutes, saves it then you can play against it.
__________________
Chaos is merely logic beyond human comprehension
Reply With Quote
  #7  
Old 10-23-2001, 03:59 AM
Yoda's Avatar
Yoda Yoda is offline
Contributor

Retired Leader
* Expert *
 
Join Date: Apr 2001
Location: Gent, Belgium
Posts: 479
Default Re: Unbeatable Tic Tac Toe Opponent

Writing an AI for the 'better kind' of games, you must realize that it will never be unbeatable.

I remember I used to play Magic : The Gathering. I don't know if some of you have heard of it. It's a card game that uses thousands of cards of which you make a selection and then combine the cards' abilities to defeat your opponent who plays his own set of cards. I remember I was very exited when they released the computer version of the game, which was two years later than planned, and had already moved from software house to software house, because of problems with the AI. They finally released it (I think it was Electronic Arts), but being a rather strong player, I didn't have the least bit of difficulty with even the toughest computer opponent. (more info here).

Same goes with chess : a computer version of chess might have beaten the best player in the world already, but it is impossible to make a computer win all the time.

The explanation is simple : in Magic as well as chess, most of the moves are logical moves : I do this and gain one card/piece. I do that and the computer can't take one of my cards/pieces. Till there, no problem, the computer will walculate so many moves that it will get the upper hand for sure. But the thing is, in both these games, and other, sometimes you have to make an illogical move, ie. sacrifice one or more of your cards/pieces to get the upper hand later on. This is where the computer fails. Being no more than 0's and 1's, the only way for an AI is yes or no, true or false, and not somewhere in between. It will never make a 'wrong' move, even when in the long run it falls into place.

This way my opinion is, that human intelligence, and not only in games, will never be overtaken by AI.

For those who stuck with me until the end : I'm impressed [img]images/icons/wink.gif[/img]
__________________
Do or do not,
There is no try
Reply With Quote
  #8  
Old 10-23-2001, 05:48 AM
Banjo's Avatar
Banjo Banjo is offline
Hell's Angel

Retired Moderator
* Guru *
 
Join Date: Jul 2001
Location: Yorkshire, UK
Posts: 10,394
Default Re: Unbeatable Tic Tac Toe Opponent

That assumes that the computer only looks at the current move. Most modern chess programs will analyse a huge number of move sequences and pick the one that puts it in the best position at the end of the sequence.
__________________
A wise one man once said "what you talking about dog breath"
Reply With Quote
  #9  
Old 10-23-2001, 06:12 AM
Yoda's Avatar
Yoda Yoda is offline
Contributor

Retired Leader
* Expert *
 
Join Date: Apr 2001
Location: Gent, Belgium
Posts: 479
Default Re: Unbeatable Tic Tac Toe Opponent

True, but the AI will consider loss of a piece as too big a sacrifice to make in the first place.
__________________
Do or do not,
There is no try
Reply With Quote
  #10  
Old 10-23-2001, 07:17 AM
Banjo's Avatar
Banjo Banjo is offline
Hell's Angel

Retired Moderator
* Guru *
 
Join Date: Jul 2001
Location: Yorkshire, UK
Posts: 10,394
Default Re: Unbeatable Tic Tac Toe Opponent

Not if that loss will result in a higher gain in 6 moves time. In the end it all comes down to who thinks the furthest ahead and computers are overtaking us on that one.

The only thing that a human can do that a computer can not is anticipate the psychological results from a move. A human player can decide which of the possible moves is more likely based on knowledge of his opponents style and mental state. The computer can not evaluate these factors.

However, I do think the Deep Blue victory (i.e.: a stalemate) was less impressive when you consider that it took a machine the size of a medium office to draw with a human brain.

My opinion is that chess in its purest form is just a hugely complicated version of TicTacToe. If you have two players capable of analysing all moves to the end of the game and they play a logical move every time then a stalemate is enevitable. The thing that makes chess interesting is the human element. The psychological pressure and the exploitation of human falibilities.
__________________
A wise one man once said "what you talking about dog breath"
Reply With Quote
  #11  
Old 10-23-2001, 07:50 AM
Yoda's Avatar
Yoda Yoda is offline
Contributor

Retired Leader
* Expert *
 
Join Date: Apr 2001
Location: Gent, Belgium
Posts: 479
Default Re: Unbeatable Tic Tac Toe Opponent

I completely agree and am starting to think that comparing chess to magic maybe wasn't such a good idea. There's quite a difference in the fact that, with a card game, and especially such a vast one in number of different cards, you have the difficulty of dealing with non-identified cards, ie. the cards in another player's hand, because of which sometimes to you a move seems highly illogical, but taking in account the cards you do not know your opponent has, the move seems to gain in logicality and wit. With chess you have all possibilities right in front of you, the only thing left to do is calculate the remaining moves, thus making it exactly possible to predict each different outcome of the game, as long as your resources are high enough (as you made clear). Therefore, indeed, but two times Deep Blue against each other and you will have a stalemate for sure.
And thinking that I can't even win a chess game from my palmtop !
__________________
Do or do not,
There is no try
Reply With Quote
  #12  
Old 10-23-2001, 08:17 AM
Banjo's Avatar
Banjo Banjo is offline
Hell's Angel

Retired Moderator
* Guru *
 
Join Date: Jul 2001
Location: Yorkshire, UK
Posts: 10,394
Default Re: Unbeatable Tic Tac Toe Opponent

Thats the thing, even a cheap little computer can beat most of us at chess. It can just calculate more outcomes than we can. That's why Gary Kasparov's draw was so impressive. He held off a computer who's memory was far more reliable than his.
Keep at the palmtop, you'll beat it [img]images/icons/wink.gif[/img].
__________________
A wise one man once said "what you talking about dog breath"
Reply With Quote
  #13  
Old 10-23-2001, 09:39 AM
Mill Mill is offline
Just another Excel nerd

Retired Moderator
* Guru *
 
Join Date: Feb 2000
Location: Michigan, USA
Posts: 2,631
Default Re: Unbeatable Tic Tac Toe Opponent

I've wondered how the computer version of Magic would work. With the card game, the more money you spend and the more cards you buy, the better your odds of winning. How does this work in the computer version?
__________________
"The face of a child can say it all, especially the mouth part of the face." - Jack Handey
Reply With Quote
  #14  
Old 10-23-2001, 10:02 AM
Yoda's Avatar
Yoda Yoda is offline
Contributor

Retired Leader
* Expert *
 
Join Date: Apr 2001
Location: Gent, Belgium
Posts: 479
Default Re: Unbeatable Tic Tac Toe Opponent

You have different kinds of play modes :

1°) Duel mode

You can create a deck of cards out of every possible card in the game. Only Unlimited, Arabians, Dark, Antiquities and Revised were ever brought for the game. Then you can either play a human opponent or play the computer on different difficulty levels. There is also a mode in which you try to beat as much opponents in a row as possible.

2°) Sealed Deck

Probabely the coolest feature of the game. You choose between 1 or 2 starter packs and 1 to 4 booster packs, and then, just like in real life, you must tear them open and discover what cards you've got. Afterwards, a tournament is played with these cards against computer opponents who, same as you, drew different cards.

3°) Quest mode

You walk around in a sort of RPG style landscape with a minimum of cards and have to defeat all five lords (one for each color). Then you face te suppreme evil. While walking through the land you can visit villages where you can buy cards or food, or complete quests to get more cards. You can also fight different creatures throughout the game, each one with their own set of cards, to win cards or objects.
__________________
Do or do not,
There is no try
Reply With Quote
  #15  
Old 10-24-2001, 01:56 PM
BillSoo's Avatar
BillSoo BillSoo is offline
Code Meister

Retired Moderator
* Guru *
 
Join Date: Aug 2000
Location: Vancouver, BC, Canada
Posts: 10,441
Default Re: Unbeatable Tic Tac Toe Opponent

While CHESS has a huge number of possible moves compared to TicTacToe, it pales in comparison to other board games like GO.
__________________
"I have a plan so cunning you could put a tail on it and call it a weasel!" - Edmund Blackadder
Reply With Quote
  #16  
Old 10-24-2001, 02:09 PM
Banjo's Avatar
Banjo Banjo is offline
Hell's Angel

Retired Moderator
* Guru *
 
Join Date: Jul 2001
Location: Yorkshire, UK
Posts: 10,394
Default Re: Unbeatable Tic Tac Toe Opponent

GO? I'm not familiar with that one. How does it work?
__________________
A wise one man once said "what you talking about dog breath"
Reply With Quote
  #17  
Old 10-25-2001, 12:32 AM
BillSoo's Avatar
BillSoo BillSoo is offline
Code Meister

Retired Moderator
* Guru *
 
Join Date: Aug 2000
Location: Vancouver, BC, Canada
Posts: 10,441
Default Re: Unbeatable Tic Tac Toe Opponent

GO is a japanese game played on a 19x19 (or larger) board. Players alternate placing stones on the board trying to make certain formations to capture territory. It's pretty popular in western culture as well....

I suggest you do a web search for more info....

__________________
"I have a plan so cunning you could put a tail on it and call it a weasel!" - Edmund Blackadder
Reply With Quote
  #18  
Old 10-25-2001, 08:24 AM
Banjo's Avatar
Banjo Banjo is offline
Hell's Angel

Retired Moderator
* Guru *
 
Join Date: Jul 2001
Location: Yorkshire, UK
Posts: 10,394
Default Re: Unbeatable Tic Tac Toe Opponent

Now that you describe it, I think I have played this, although it may have been under a different name. And your right, the number of combinations in that would be enourmous!
__________________
A wise one man once said "what you talking about dog breath"
Reply With Quote
  #19  
Old 10-25-2001, 10:29 AM
Yoda's Avatar
Yoda Yoda is offline
Contributor

Retired Leader
* Expert *
 
Join Date: Apr 2001
Location: Gent, Belgium
Posts: 479
Default Re: Unbeatable Tic Tac Toe Opponent

Isn't Othello a western variety to Go ?
__________________
Do or do not,
There is no try
Reply With Quote
  #20  
Old 10-25-2001, 01:41 PM
Mill Mill is offline
Just another Excel nerd

Retired Moderator
* Guru *
 
Join Date: Feb 2000
Location: Michigan, USA
Posts: 2,631
Default Re: Unbeatable Tic Tac Toe Opponent

They're similar, but not quite the same. With Othello (or Reversi) you capture your opponents pieces by controlling two end points. In Go, I believe that you have to totally surround the pieces that you want to capture.
__________________
"The face of a child can say it all, especially the mouth part of the face." - Jack Handey
Reply With Quote
Reply


Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)
 
Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off

Forum Jump

Advertisement:





Free Publications
The ASP.NET 2.0 Anthology
101 Essential Tips, Tricks & Hacks - Free 156 Page Preview. Learn the most practical features and best approaches for ASP.NET.
subscribe
Programmers Heaven C# School Book -Free 338 Page eBook
The Programmers Heaven C# School book covers the .NET framework and the C# language.
subscribe
Build Your Own ASP.NET 3.5 Web Site Using C# & VB, 3rd Edition - Free 219 Page Preview!
This comprehensive step-by-step guide will help get your database-driven ASP.NET web site up and running in no time..
subscribe
 
 
-->