Minimax Tic Tac Toe

Adventurer
1

So I just started this level and it has some glaring information missing from the guide.

  1. Am I playing as X or O? (I’m assuming X)
  2. I’ve never heard of the Minimax or Negamax methods. Would be nice if the guide included a
    link to a page about them (I know I could google, but this would make it easier.)
  3. Needs updated default code for other languages
  4. Would be nice if the guide included a description of how the board is stored and passed between functions. It is there if I mouse over “board” in the spell palette, but would be nice to have a more structured Guide that included that.
2

@Darredevil heads up

3

Hi dwhittaker,

The current guide for Minimax Tic Tac Toe is temporary , a new guide should be available in a couple days.Regarding your questions :

1.Yes you are playing as X.
2.The new guide will include proper explanations and examples as well as links
3.Should be available in a few days
4.The new guide will try to take this into consideration, but could you be more specific ? Because from my point of view , you really don’t need this information as long as you respect the return conditions for the other methods and i assumed the description of the “board” object in the spell palette is enough. Not sure what you mean by stored and passed.

4

Glad to hear you are already working on an improved guide. I don’t think I worded #4 well. Mostly just saying that I think the mouse over description is pretty good, but that it might be good to also have it in the guide.

Another nice thing would be to add the UsesArrays component to get those snippets included.

5

@Darredevil So I’m trying to get my code to actually finish and just realized that the code is expecting moves of the form {i: <value>,j: <value>}, but in the getPossibleMoves function, the default code includes this comment:

This function must return all possible future moves given a board state
the moves must be an object like this : {x: <value>,y: <value>}
the values should be between 0 and 2

Beyond that I still can’t get everything to come together for this level. I understand the basic concept, but the things I’m passing back and forth don’t seem to work properly. Or the python transpiler isn’t working properly, I can’t figure out which is which. I’ll try again in another month or so!

6

@dwhittaker I agree with you, a simple tutorial on how to write minimax algrothim would be really helpful.I tried googling tutorials for minimax algorithms but most of them just discussed the concept of minimax.I didnt find any form of source code.

I understood the minimax algorithm, but one question I still have is how do I evaluate a board.Like how do I evaluate the score of a board at a particular state.

Leaving that aside I found this helpful video on youtube : https://www.youtube.com/watch?v=STjW3eH0Cik

Its really helpful as it talks about how to reduce the number of states that you would have to calculate.(Alpha-Beta)
The equations might intimidate you,but if you dont understand them just ignore them and continue.Its really worth it, give it a shot :smile:

7

This heavily depends on the problem and is therefore mostly left out of the algorithm itself. A few notes:

An evaluation can happen at any time during the MinMax-Algorithm and usually acts as recursion-anchor. If the tree is too deep to traverse completly, you evaluate early and use this result. Chess for example is way to complex to traverse the MinMax-Tree completly, but certain situations are better than others, thus receiving a higher rating.

An evaluation can be anything from

  • Game Won -> Evaluate to 1 Point
  • Game Lost -> Evaluate to 0 Points

to

  • Count Enemies on Field -> Evaluate to 100 - #Enemies

The first lets you find a strategy that will win the game, no matter how many enemies you kill, the second one will find you a strategy that will kill the most enemies.

Sorry, Tic-Tac-Toe-Thread…
For this case the first variant is enough. You usually don’t care how many turns you need to win TTT, you’re only interested in winning.