Tek-Tips is the largest IT community on the Internet today!
Members share and learn making Tek-Tips Forums the best source of peer-reviewed technical information on the Internet!
-
Congratulations Chriss Miller on being selected by the Tek-Tips community for having the most helpful posts in the forums last week. Way to Go!
Tic-Tac-Toe. Artificial Intelligence?
- Thread starter pauiel
- Start date
ive been starting to plan some AI for tik-tak-toe too, if u interested in having a chat about it u can mail me at me[at]mark-ingram[dot]com
Skute
"There are 10 types of people in this World, those that understand binary, and those that don't!"
Skute
"There are 10 types of people in this World, those that understand binary, and those that don't!"
lionelhill
Technical User
... agree! Chess has a lot more interest to it, and fortunately a huge number of very generous people have put comprehensive information on chess algorithms in websites. You can pursue this one as far as you want. A simple alpha-beta search on a modern fast computer, if implemented half-way well, will flatten even quite serious chess players.
Which raises point 2. Actually the really difficult thing about a chess game is how to make a computer play badly in a realistic fashion. i.e. how to implement artificial human intelligence.
Which raises point 2. Actually the really difficult thing about a chess game is how to make a computer play badly in a realistic fashion. i.e. how to implement artificial human intelligence.
Zyrenthian
Programmer
I prefer to play "Global Thermal Nuclear War"
I guess the easiest way to write an AI engine for your program would be to actually play it with someone and write your own strategy down in pseudocode.
this would have to be dependent on whether or not the computer was in defense or offense mode. It would automatically start out in one mode or the other depending on whether it won the random toss for first or second play. In between plays it would have to determine if the mode should change dependendt upon the number of possibilities of the real player being able to score.
You could further enhance this AI if you were to record the computer's number of wins vs losses if you save something to the registry or in a .dat file that your program would read upon startup. That way the computer's play would never be totally random but instead based on past experience with that user (if there was a login or something like that)
bdiamond
this would have to be dependent on whether or not the computer was in defense or offense mode. It would automatically start out in one mode or the other depending on whether it won the random toss for first or second play. In between plays it would have to determine if the mode should change dependendt upon the number of possibilities of the real player being able to score.
You could further enhance this AI if you were to record the computer's number of wins vs losses if you save something to the registry or in a .dat file that your program would read upon startup. That way the computer's play would never be totally random but instead based on past experience with that user (if there was a login or something like that)
bdiamond
I once wrote a tic-tac-toe game that had a simplistic way of learning, but it's not as interesting as a neural net would be.
It kept an array of integer values, which provide a score for each possible move for each possible game situation. There's few enough possible game situations that the resulting array isn't too big. The program remembers each move that was made in the current game. If the computer player loses, then each move it made is considered a bad move and the score is adjusted by -1. If the computer player wins, the score is adjusted by +1. If its a draw, the score is not changed.
I ended up tweaking this a few times. One change I made was I gave the later moves more of the blame for the outcome, and earlier moves didn't get scored as harshly. I also changed the deltas so instead of -1 and +1, it ended up being some other range of values (depending on the blame given to each move). It worked out okay, but the computer player never got really good, but it entertained my niece and nephew (young kids). As you can imagine, it learns very slowly and in a very mechanical way, so I put some randomness in it to make it less predictable. It saved the learning information to a file. It might be amusing to have a program like this play against itself. It would also need some mechanism to keep the scoring values from saturating the limits of the data type.
It kept an array of integer values, which provide a score for each possible move for each possible game situation. There's few enough possible game situations that the resulting array isn't too big. The program remembers each move that was made in the current game. If the computer player loses, then each move it made is considered a bad move and the score is adjusted by -1. If the computer player wins, the score is adjusted by +1. If its a draw, the score is not changed.
I ended up tweaking this a few times. One change I made was I gave the later moves more of the blame for the outcome, and earlier moves didn't get scored as harshly. I also changed the deltas so instead of -1 and +1, it ended up being some other range of values (depending on the blame given to each move). It worked out okay, but the computer player never got really good, but it entertained my niece and nephew (young kids). As you can imagine, it learns very slowly and in a very mechanical way, so I put some randomness in it to make it less predictable. It saved the learning information to a file. It might be amusing to have a program like this play against itself. It would also need some mechanism to keep the scoring values from saturating the limits of the data type.
lionelhill
Technical User
You've got to decide here what you want. From your first posting I think you just want the computer to play better than random. A lot of the responses have assumed you want learning-behaviour as part of full-scale artificial inteligence. I rather liked dementg's version.
But you can have something that plays well without having learning and AI features. Neural nets are a bit of a sledge-hammer to crack the problem. I'm pretty sure my little Mephisto with its 8K ram doesn't have a neural net, and it wins too easily at chess with me (and it also plays like a beginner more convincingly than much larger computer-based packages).
But you can have something that plays well without having learning and AI features. Neural nets are a bit of a sledge-hammer to crack the problem. I'm pretty sure my little Mephisto with its 8K ram doesn't have a neural net, and it wins too easily at chess with me (and it also plays like a beginner more convincingly than much larger computer-based packages).
- Status