✅ Tic tac toe
im trying to implement tic tac toe with DFS and im struggling to get it to work properly
37 Replies
$paste
If your code is too long, you can post to https://paste.mod.gg/, save, and copy the link into chat for others to see your shared code!
GitHub
TicTacToe/TicTacToe at master · ZoonAttack/TicTacToe
Contribute to ZoonAttack/TicTacToe development by creating an account on GitHub.
My main issue is that, from what I've observed, the algorithm is correctly checking the states, which is typical of depth-first search (DFS). However, the major problem is that it continues to place an "O" on the buttons randomly, even when it should recognize that placing an "O" on a certain button would lead to a winning state. If that is the case, it should only place one "O" on that button and then allow me to take my turn by clicking on any other button. If you look closely, you'll see that it is just placing "O"s all over the board.
"Once that winning path is found. it will recursively backtrack up the call stack. At the top of the call stack it will turn THAT next possible move which allowed the A.I to reach that winning state." i want THAT to happen.. i think my problem is with managing the backtracking
it should backtrack to the very first step without making any change to the actual game.board
once it backtracks to the very first step that led it to the winning state.. it performs the change to the real board instead of the copy board
okay did you not debug this? step by step?
also i would reorganize code a little
extract a clear sequence of methods so that the solving logic is easier to follow and it's clear what the steps are doing
for example:
this is the part that checks if an end condition is met, so i would move that stuff in an isolated method
then you are searching for the first empty cell
i would put that in an isolated method
and so on, until everything is clear and you can debug this
I debugged it
I traced every single little output it works fine and backtracks
But it just assigns to the real board when it shouldn't
It should only assign once it backtracked all the way
i should try this to be sure but how many times do you think this is called
Game.board[i, j] = 'O';
or should be called, maybeSo once the dfs has found a path and the checkstate finally returned true when it was passed an 'O' it should backtrack all the way without making changes again to the path. And at the very first step it took to reach that path it should assign it to game.board
And send the row and col for that position of the board to update button so I can display the O on the ui
I think my problem is I'm not isolating the backtracking and it keeps backtracking and adjusting even if it found a win. And that during backtracking it keeps assigning to the actual board
yeah and there are two issues - again i should try this before being 100% sure - about this
so first would be: which cell should be written on the game board? answer i believe it should be the first found right? (or first in the stack)
and second: what happens after
the
return true?Yes first found right
Umm it should return true so while it backtracks it keeps the state "true"
That's what I thought of
i would think so too, so what happens next
It exits out of the current stack call and returns to the precious turn it took and Same thing should happen
Oh wait wait
This is what's supposed to happen
While it's still returning to the very first step it took
But what happens is.. I have this return true after applying the winning move to the game board so once it returns true in the game.cs I can use that information with smth else
The return true under the game.board should be the last return of the stack call of that method
Since I'm currently not using that in the game.cs I think I just have it to stop the algorithm or smth
we can put it in this way
the last call to DFS recursion is the one that results in a win condition
from there it always goes in that if and returns true
But as a said. It should be already the last move though its not
The last call should be the one determining the win condition indeed. If it found then it should keep returning while doing nothing and applying the very first turn it took to the original board
yes but there is not the "do nothing" part
I think my problem is it enters the if statement where the game.board is
Yeah Is that what I'm missing ?
yes but i would say the complicated part is that in there it's being shuffled a bunch of things together
so it's difficult to keep track of what is happening and error occours
that's to me what mainly is missing, isolating stuff so that you could have an easily followable sequence of events
because it will be more difficult to have errors
also because at this point to solve this you cannot have just two return states (true/false)
you have to have at least one more, which is "ending was met, do nothing until i get to the first move and write that to the game board"
which is a kinda complicated state, not impossible but not the simplest i guess
and also maybe there are even more conditions
but maybe it's taken care of by
isDraw
although you are not using the return value of DFS from game.csI will make a boolean that tells me that and return it if a winning condition is met
So it stays true all over the backtracking
I don't quite understand how that would make a difference
Since the logic is just what's under the checkstate
i think an enum would be more explicit
currentPlays++/-- is a logic
currentBoard[i, j] = '\0'; is a logic too
if (isComputerTurn && result) is a logic obv.
and this for(int i = 0; i < 3; i++) for(int j = 0; j < 3; j++) (currentBoard[i,j] == '\0') is a logicYeah
Okay I'll try it once possible and tell ya
which would should roughly translate in
- exit if ending condition is met (winning/losing, draw, no more cells left)
- find first playable cell
- set turn number
- simulate play (pc/human)
- clear
- update real board with winning move
which would be the "main" loop
Wdym main loop
Yeaah I think what I'm missing is the exit if win state is found
So.. what do you exactly recommend me to do ?
main loop as in algorithm loop, or like solution-finding loop
if you already have some stuff going on and apparently the modification you need to make this work is relatively small, i would try that first
eventually reorder code after
What is "that" :d sorry got a bit confused
Make an enum or boolean that tells me "ending was met" ?
Is the point of that boolean to make dfs backtrack and reach the very first step?
yes
yes, to tell that the move was valid
i guess you could see it in this way
the first move is the move that will eventually be done
the rest of the moves are a simulation to prove that the move is worthy
yeah thats right
can i just make an enum with the states COMPUTERWON, HUMANWON, DRAW, VALIDMOVE or something
hey if youre awake could you check my code now ? i did some changes
i think the logic seems promising now
it doesnt put Os all over the place but it gives up in the middle 💀
it reached a winning state
but the first move it made was supposed to be the one ontop
top middle
it played in the middle.. you can see the "first move" variable being (1,1)
there is a problem
it works well and but it loses track of the actual first move it made.. the firstMove tuple values change when they shouldnt since the algorithm did not backtrack to the very first move yet
and theres something else.. firstMove tuple sometimes is null
after a set of moves are made.. it reaches null for some reason
i managed to fix
this problem
now i have THIS problem
I updated my github u can see the updated code there
i still think you have to learn to debug better, how many cycles will this algorithm make, like few tens?
i fixed the code
u can check the latest modified code now
it works way better than i expected
i still need to handle some end-game cases but thats all in the game logic not the algorithms
$solved
#close
you could
int.Parse also the remaining Convert.ToInt32(button.Tag.ToString());
and instead of Tuple<int,int> you can use like (int Column, int Row)
it would be nice to have at least names for various strings like
better tactic would be to not use ui stuff in the algorithm at allyeah youre right
trying to make it fancy 😂