semmons99

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.

Banjo

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.

Garrett Sever

Anybody ever see War Games w/ Matthew Broderick?

Yeah, ancient, but it makes this very point.

"Shall we play a game?"

orufet

Yeah, I saw that movie years ago....Pretty good, but, as you said, quite old...

Banjo

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]

Cryostasis

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.

Yoda

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]

Banjo

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.

Yoda

True, but the AI will consider loss of a piece as too big a sacrifice to make in the first place.

Banjo

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.

Yoda

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 !

Banjo

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].

Mill

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?

Yoda

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.

BillSoo

While CHESS has a huge number of possible moves compared to TicTacToe, it pales in comparison to other board games like GO.

Banjo

GO? I'm not familiar with that one. How does it work?

BillSoo

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....

Banjo

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!

Yoda

Isn't Othello a western variety to Go ?

Mill

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.