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:
- the final outcome is lose, draw or win
- the maximisation is to make a step that lead to a final win: the contender that plays first at each step is a maximiser
- the minimisation is to make a step that will prevent the other to win (OJO: not to win him/herself): this contender plays after a maximiser and he/she is a minimiser
- the roles are exchanged along the game until the game stop
- assign a value to that outcome and save it somewhere for future comparison
- you go back and you start another initial scenario until all the possible initial scenarios are played
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:
- every value in a corner wins in its vertical, horizontal and diagonal
- every value in the center of the boarders wins in its vertical and horizontal
- every value in the center wins in its diagonals, center vertical and center horizontal
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.
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: