Tic Tac Toe & Minimax AKA Grrrr

Tic Tac Toe & Minimax AKA Grrrr
0

#1

Hello guys!

I have become frustrated with trying to learn minimax. I’ve read many, many, many links and worked on this for days. My problem is with understanding other’s different implementations, understanding how they connect logically (they all seem to do it different ways), and the commands and structures they use for it. I understand theoretically how it works, implementation is the problem. I want to code a basic implementation and tweak it/review it and learn from that. I.E. player 1 (x) will be human, and player 2 (o) will be the computer. If i can get it functional I can understand it and then move on to making which player is which irrelevant, add “clues” button, etc.
My implementation comes from https://www.geeksforgeeks.org/minimax-algorithm-in-game-theory-set-3-tic-tac-toe-ai-finding-optimal-move/ which is the simplest explanation I’ve found.
My codepen is https://codepen.io/tylerOtj/pen/qpyKJr?editors=1112
Everything is thus far done in console. The source code (geeks for geeks) says minimax will play for x, however on board 0 it won’t block OR win, and on other tested boards it makes moves not optimal.

Things I’ve tried:
-swapping computer and player (o->x, x->o)
-setting isMax in minimax call (in findBestMove) to true\false for both combinations of computer\player x\o
-Alert statements on every change in bestVal, board, setMove to check correct cell assignment, board updating, value assignment
-Noted that “new best val” statement in findBestMove function is only called once, sometimes twice (on an empty or 1-celled board shouldn’t it be called more?)

Like I said, my goal is to really understand this. Even if you don’t give me the answer a hint in the right direction, a behavior to look at, anything would be greatly appreciated.
Thanks


#2

i don’t understand what you mean exactly but i have thought about that project a bit recently since i am going to do tic tac toe after i complete my pomodoro, i hope in a day or two. from what i remember from my childhood :3 it’s a very simple game with a couple of possible entrapments if you go first of which we can use one (for simplicity always the same) and avoid two. so, how i am seeing it, i will need a function that would check if you (i.e. ai) can get a vertical or a horizontal line of three on your turn and another one to check if the enemy can get it on theirs and what’s the position which completes the line/prevents it’s completion, it should be rather straightforward

except for that i would need only few simple rules, that should be applied to all the flipped vertically and horizontally states though, that flipping might be the hard part. here are these rules:

if you go first (for simplicity let x always go first, btw i wish it was the case in the sample app, random is annoying) then as your first move you set a cross in the middle of the field

then the enemy has two possible ways to answer (each having a few flipped states):

     . . .
     . x .
     0 . .

and

    . . .
    . x .
    . 0 .

if the enemy answers the second way it’s a draw, pretty much doesn’t matter where you put your x, if you follow the both aforementioned checks, if you can draw a line and if the enemy can draw a line, those are enough to get a draw or a win

if the enemy answers the first way you can try to entrap them:

    . . x
    . x .
    0 . .

if the enemy answers like

    . . x
    . x .
    0 0 .

you won and you only need the aforementioned checks for it, it will prevent the enemy from completion their line and then finish the enemy off completing of the two lines that the enemy can’t break:

    . . x
    . x .
    0 0 x

otherwise it’s another draw and to complete it you only need the aforementioned checks again and random placement if no threat exists (or to even more min max it can be not random but another function which places your x where you theoretically can complete the line, anyway it’s a draw if the enemy pays a tiny bit of attention)

if you go second and the enemy puts their x in the middle you simply put the zero like on the second scheme to avoid the possible entrapment and then use the aforementioned checks. if the enemy puts their x like this, it’s the second way of entrapment and it’s pretty simple to avoid and to use autochecks till the end after that, you put the zero into the middle and proceed as following and then use the autochecks:

    . . .
    . 0 .
    x . .

    . . x
    . 0 .
    x 0 .

if the enemy didn’t try to entrap you and their move was anything but the aforementioned position then autochecks will be enough to get a draw again

p.s. forget it,

    . . .
    . x .
    . 0 .

is a death sentence and unavoidable defeat, i forgot about that trick

    . . .
    x x .
    . 0 .
    x . .
    x x 0
    . 0 .

#3

Don’t forget about diagonal lines.


#4

yeah :3

my that post wasn’t very accurate anyway, i dunno how i even forgot about that trick to 100% win unless your opponent puts 0 to one of the corners