This is a read-only archive of the old Scratch 1.x Forums.
Try searching the current Scratch discussion forums.

#1 2012-04-14 12:07:57

skippito
Scratcher
Registered: 2012-03-17
Posts: 100+

Game Tree

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

 

#2 2012-04-14 12:12:29

AtomicBawm3
Scratcher
Registered: 2009-06-27
Posts: 1000+

Re: Game Tree

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.


http://i50.tinypic.com/j0yw0p.jpg

Offline

 

#3 2012-04-14 12:34:54

silvershine
Scratcher
Registered: 2010-11-21
Posts: 500+

Re: Game Tree

This is a very challenging project, and I've only been able to complete it in Java. It should be pretty similar on Scratch!  tongue

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?  smile

Hope that helped!

Offline

 

#4 2012-04-14 13:28:25

joefarebrother
Scratcher
Registered: 2011-04-08
Posts: 1000+

Re: Game Tree

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)


My latest project is called http://tinyurl.com/d2m8hne! It has http://tinyurl.com/d395ygk views, http://tinyurl.com/cnasmt7 love-its, and http://tinyurl.com/bwjy8xs comments.
http://tinyurl.com/756anbk   http://tinyurl.com/iplaychess

Offline

 

#5 2012-04-14 13:48:53

MoreGamesNow
Scratcher
Registered: 2009-10-12
Posts: 1000+

Re: Game Tree

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.


http://images2.layoutsparks.com/1/218929/rubiks-cube-animated-rotating.gif
"Cogito ergo sum" --  I think, therefore I am

Offline

 

Board footer