Hi,
I am stuck with my tictactoe -project and I need help. Here is a link to my project tictactoe.
There is predefined state of the game ->
[E, o, x,
E, x, E,
o, E, E]
And for my understanding minimax should return position 5 ->
[E, o, x,
E, x, x,
o, E, E]
but now I get value of 0 for every move, those can be seen when running the code with console log. Any suggestion what shoud I try next, I am feeling desperated 
-Zumartic-
While this doesnât answer your question, I had similar issues. I abandoned minmax and implemented my own logic. Tic tac toe has a small enough board that it is easy enough to think through different scenarios. assuming that you understand the various patterns of game play.
If you havenât already, you may wish to search the forums for âtic tac toeâ to see the issues and solutions others have encountered â you are certainly not alone in finding this project a challenge.
Happy coding!
I did the same thing. At the moment I am more interested in getting further in coding than in learning algorithms, specially when they seem too dificult for the learning stage in which we are. Algorithms are important and fun, but in my case I need a balance between fun, knowledge and progress.
Also, I am not going to let a nerdy algorithm make me feel bad about myself!!! 
I was not able to create the algorithm I ended up to creating optimal play strategy -> tictactoe
-Z-
There are eight possible winning lines in tic tac toe. Each of these can be represented by an array. You can create an array of arrays that will represent your game board.
Now you can create the AI with three general algorithms(the computer is X). Most or all of the logic can be done with arrays and loops.
If you can implement those three algos, the computer will have quite realistic (but not unbeatable) game play. If you add some hard-coded moves for the first few turns, then you can create an unbeatable AI.
Hope that helps!
Hi Everyone,
I wouldnât call the minimax a real AI 
When playing minimax or similar algos just play computationally all the options ahead. In practice for long games like chess the strategy is run up to a certain point and use other heuristics for decision making.
For the tic-tac-toe, for an unbeatable strategy just start from one point an then play all possible outcomes up to some time in the future.
Select the outcome that pays more or in case of an unclear outcome just play a position. In this case the minimax rules that in case you cannot win, or that winning is not the nearest option, find the position that better destroy the options of winning of the opponent in any following move. Actually, the right interpretation is to select that move that reduce the expected losses. So it was not about winning, but about zero-sum games. Then you can select to win if the options allows you.
That is my interpretation of the rule (I havenât tried the game yetâŚ).
In the case of the tic-tac-toe the more the gamers play, the higher the certainty. I havenât tried but it should be a point of the match at which the programme will get what the best outcome should always be, probably after 4-5 moves. In order to reduce the search, start letâs say the first 2 moves using another approach and then start looking.
For those audacious some recursion could be also applicable⌠but likely not advisableâŚ
OBS: this game is small enough to search the TOTAL SOLUTION SPACE, that is, all the possible outcomes. Donât try a similar approach with other similar games or situations where the number of options increase!
I implemented Minimax in my version of the game. I tried to comment my code, so it was easy to see how the algorithm worked.
Take a look and see if it helps you:
I canât see it displayed. Read the code though⌠Looks enjoyable!!!
And saw your recursion⌠Good! Although I am thinking on another solution that doesnât need to visit the whole Solution Space.
Yes: good that you are using a linear representation of the gameboard, but I think that a Matrix representation could have been more useful?
Hi, I used this tutorial to implement an unbeatable opponent : http://www.wikihow.com/Win-at-Tic-Tac-Toe
Hi Everyone:
By just Googling âfreecodecamp tic-tac-toe algorithmâ I also found other codes you can see :
Also the problem is common in gitter, reddit and the forum:
There is something in some of the minimax implementations that are not considering some scenarios in order to produce a really unbeatable one.
However the point of the exercise IS NOT to create an totally unbeatable project although one that can
perform reasonably well in the majority of the cases.
We can use your thread, @zumartic, to discuss further some different solutions to the algorithm problem⌠I think we should try at least to suggest pseudo-codes of several options?
can you check this one that if you can win or not ?
I canât see it displayed. Read the code though⌠Looks enjoyable!!!
Play the game here:
https://ortonomy.github.io/tic-tac-toe/
And saw your recursion⌠Good! Although I am thinking on another solution that doesnât need to visit the whole Solution Space
You asked for minimax - if youâre not going to visit the whole solution space, then is it still minimax? Considering you need to assign a score to a board state, the only definite score you can assign is win / no-result / loss in tic-tac-toe.
Yes: good that you are using a linear representation of the gameboard, but I think that a Matrix representation could have been more useful?
I know of matrices, but I donât know matrices or matrix algebra that well. I wouldnât be able to compare them and answer your question. Youâd have to give me an explanation of why matrices would have been more useful.
P.S - my algorithm came from here: Tic Tac Toe: Understanding the Minimax Algorithm â Never Stop Building - Crafting Wood with Japanese Techniques
hi @geligelu,
Thanks for asking! I think this discussion could highlight some âhiddenâ takeaways from this particular exercise, IMO.
(Disclaimer: I didnât do any CS at uniâŚ)
You asked for minimax - if youâre not going to visit the whole solution space, then is it still minimax?
First of all:
###What is minimax?
Actually Minimax is NOT at first an algorithm per se but a decision criterion. The criterion is (wikipedia):
minimise the possible loss for the worst case (max) scenario
You then build an algorithm, called also minimax, that comply with that criterion. There are several ways to code the algorithm but all should comply with the same criterion and in theory lead to a similar outcome.
As I understood it the algorithm started from a initial scenario and then had to find the next final worst case scenario by iterating up to some point in the future, assigning a loss (which can be positive) to that outcome, and coming back to start from another initial scenario. Then comparing outcomes and keeping initial scenario(s) that will minimise the losses.
In a recursive form though it could move likely as a canonical depth-first search or similar. In the case of depth-first search, from wikipedia:
Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. One starts at the root (selecting some arbitrary node as the root in the case of a graph) and explores as far as possible along each branch before backtracking.
(OBS: remember you can (almost?) always represent a recursion as a iteration and viceversa!)
As I understand it, to be a complete minimax you assume that both contenders play a minimax rule:
How I understand it, scores could be also added at each step of the game, not just at the end, in order to optimise moves when several scenarios could lead to winning or draws.
(OBS: I was first thinking that the minimiser was a fixed criterion at any initial scenario in which case a simple draw could be also an optimal solution EVEN if a winning outcome was possible)
###Do I have to visit the whole Solution Space?
This was more a thought (again I have not work on this algo yet) but I think NO.
First, there are rules of the game that are the best outcome to follow and that you expect should be the next move (like blocking a win). You assume you are playing with a rational contender which is also minimax. There are also some additional rules that you could incorporated to the algo to make it âknowledgeableâ. Example:
This could be used to help you to discharge some solutions that are not optimal, although feasible.
You can also, for some solutions, break the iteration/recursion as the outcome is already known IN ADVANCE. No need to visit other solutions.
This is more like finding ways to set UPPER or LOWER bounds and prune feasible but not optimal solutions accordingly.
There should be several ways to do that. Some of them probably many of them an overkill for this situation.
###Matrices
Youâd have to give me an explanation of why matrices would have been more useful.
This was also a thought actually. Yes I think that in this case and maybe for much JS it makes no difference. As you might know there are some languages more suitable and efficient when working with matrix types than by using arrays and loops. Donât think it is the case of JS.
I was thinking though that by using matrix notation it could be easier to loop over the solutions and prune some no-optimal ones easily.
But for one possible LA approach, you could write the rules of the game assigned to each cell of the gameboard and apply transformations. Maybe an overkill for this project. In case you are interested though, here a package to work with matrices in JS:
