[WIP][Help] noughties and crosses (Tic Tac Toe) webtease

[matschbirne]

Hey, I wanted to make a tic tac toe based webtease.

The base function is done and a very dumb bot, who just selects a place randomly... But I want to have a good and an unbeatable bot as well.
I've found these resources:

Spoiler: show

https://github.com/helloRupa/jquery-tic ... master/src, https://github.com/joydicurtis/tictactoe and most importantly https://mostafa-samir.github.io/Tic-Tac-Toe-AI/

I've tried my best to replicate them. But since the EOS javascript is not 100% similar I have some problems.

At the state I'm now the "unbeatable" bot doesn't do the recursive search for the best move and instead just fills in the first empty field, with some additional bugs...

Maybe you could either take a look at my code (it's for sure not pretty) or you may want to program a perfect bot and share it here? I'm gonna take a break, maybe I'll have some new ideas tomorrow.

much love :*

P.S: Tease file attached and this is the EOS Edit link: https://milovana.com/eos/editor/65062/edit

[kerkersklave]

I don't have the time right now to write any code, but tic-tac-toe is a solved game with a known perfect strategy. So I would not go for the usual min-max-search. That would be quite slow without any optimizations (especially as javascript in EOS is slow as it is interpreted by a interpreter written in javascript for safety reasons) and with optimizations it is complicated.

Wikipedia lists the perfect strategy: https://en.wikipedia.org/wiki/Tic-tac-toe
Just take the list mentioned there and if it allows for multiple moves, pick one at random for more variability. If you want to weaken the AI a bit, you can just occasionally make a wrong move or avoid making a directly winning move.

[matschbirne]

yes, it is solved, but if I want to let the ai have the be O, then there would be so many possibilities to programm... Yes there are "only" ~140 ending postions (with symmetries and rotation already accounted for) but there are so many ways to that way. I don't think it is realistic to write them all in code...

There could be a way with something akin to image recognition, like if you have already 2 O's in a row and the remaining field is empty choose this one, and if your oponent has 2 X's in row and the remaining one is empty put yours there. But this would only help near the end. But maybe it could help enough... I need to check that tomorrow.

[kerkersklave]

Did you read the strategy bit in the English Wikipedia article?
The 8-rule-strategy there is perfect for each player. Yes, you could pre-compute every position, but you don't need to, as there is a simpler representation of the perfect strategy. You just have to check all these rules and go by the first one that applies. That works for both players.
Yes, in general that is not true for all solved games, but tic-tac-toe is very simple, so a set of rules is enough to play perfectly.

Also, even if you want to pre-compute all possible combinations, you do not actually need all of them, you just need those that you allow the opponent to actually reach. If you are fine with always picking the same move in the same situation you only need an lookup-table with less than 729 states for each player.
Here is one: https://xkcd.com/832/

But I would not go there, I would just implement the 8 rule strategy.