I wish to create a tic-tac-toe game with a game tree. I want it to have a computer that can always make the best move, hopefully never losing. Please post scripts needed for this here.
Offline
skippito wrote:
I wish to create a tic-tac-toe game with a game tree. I want it to have a computer that can always make the best move, hopefully never losing. Please post scripts needed for this here.
There's no way to always win at Tic-tac-toe but you can make it so the cpu never loses...I can't think of an algorithm right off the top of my head but I'll keep thinking.
Offline
This is a very challenging project, and I've only been able to complete it in Java. It should be pretty similar on Scratch!
Here's how I approached the problem:
There are only 8 ways that a player can get three-in-a-row: (1's are where the player went)
[1][1][1]
[0][0][0]
[0][0][0]
[1][0][0]
[1][0][0]
[1][0][0]
[1][0][0]
[0][1][0]
[0][0][1]
etc.
Whenever the human player goes somewhere, my program would delete all of player 2's (player 2 is the AI) winning combinations that involved that spot. So if the human player went in the upper left square, then every combination that player 2 had where it would have go in that spot would be deleted. When it was the AI's turn, it would only make decisions based on what was left in its list, and the human players list. Does that make sense?
Hope that helped!
Offline
take a look at this project. I haven't made it so the computer never loses because the player will get bored. However, you can remix it so it will never lose (probably on another difficulty level, 'Impossible')
However, a perfect tic-tac-toe engine is a very ambitious project!
Last edited by joefarebrother (2012-04-14 13:30:03)
Offline
This Scratch-Wiki article should help you. The actual script would be fairly lengthy, but it would be something like this:
Look at all possible moves
Make move 1
see if someone wins
if(someone wins)
return (who won?)
else
go a level deeper
Repeat for move 2, 3, 4, etc.
I don't know your experience with programming, but if this is your first account and Scratch is your first experience programming, I'd try something less ambitious and less complex.
Offline