(Due to a bug, Accuracy 0 does not work) Tic-tac-toe, otherwise known as Naughts And Crosses, is a game you've almost certainly played before. https://en.wikipedia.org/wiki/Tic-tac-toe If you want to recompute the game tree for whatever reason (just to see how long it takes? Spoiler: It's quite a long time), just see inside, go to the "AI" sprite, and set the "computed?"variable to 0, and click the green flag.
I was inspired by this video: https://www.youtube.com/watch?v=5oXyibEgJr0 I then remembered reading the article about Game Trees on the Scratch Wiki (https://wiki.scratch.mit.edu/wiki/Game_Tree), and remembered it mentioned there was no actual Scratch code because it's too complex.So I got inspired to make this! I've pre-computed the whole game tree before I uploaded this, but there is a script to compute it inside, in case it might have been too big to upload. How it works is basically computing all the possible sequences of moves, and assigning a score to them (win, loss, or draw), by first checking the positions that have already finished, then checking 1 move before that to see if a player can force a win or draw, and stepping back further, and so on. The result is a tree of all possible move sequences, along with their future outcomes. When it's making a move, the computer then just checks through each possible option to see which ones give it the optimal outcome, and chooses randomly from those. If it's accuracy is lower than 100%, sometimes it will play a random move instead of the best move ("making mistakes") There are several reasons why it's harder to implement game trees in Scratch than any other language: 1. Scratch is slower than other languages. Even in turbo mode, it takes a while to compute the whole game tree. 2. Scratch does not have first-class data structures, like Snap! does, which means I had to implement a workaround for tree data structures in terms of a list with pointers representing tree nodes. 3. Scratch does not have temporary variables, so I had to emulate them via a stack (another list) If it was a more complex game than tic-tac-toe, such as Checkers (aka Drafts) or Chess, I would not be able to store the entire game tree in memory, so I would have to garbage collect parts of it too, and write a more complex board evaluation function that detects more than just win, lose, and draw, as I can't search all the way to then end of the game, just a few moves ahead. Still, it's a cool proof-of-concept I think :)
