- Forum
- General C++ Programming
- Tic Tac Toe algorithm timing out on long
Tic Tac Toe algorithm timing out on long cases
I've encountered a programming problem where there are multiple games of tic tac toe being played and you have to deduce, when making a specific move, who will win if you continue making the best move possible. I've been tearing my hair out at what exactly is causing this problem; the program seems to work fine for one single case but with 15+ games it becomes near impossible. Any help would be appreciated.
|
|
Last edited on
|
|
Last edited on
Put your code in code tags so it's readable.
Post some input and corresponding output.
If it's from a website, post a link to the problem.
Post some input and corresponding output.
If it's from a website, post a link to the problem.
problem: https://www.codeabbey.com/index/task_view/tic-tac-toe-minimax-algorithm
input data:
3
1 8 7
7 1 5 3 4 8
7 2 1 3
answer:
000020000 101000100 000021202
my output: [nothing]
times out
input data:
3
1 8 7
7 1 5 3 4 8
7 2 1 3
answer:
000020000 101000100 000021202
my output: [nothing]
times out
| my output: [nothing] |
Also:
To consume the newline after
cin >> ws;
Right after line 1. This will consume any whitespace that follows
|
|
Inputs is on a line by itself. Line 1 reads the number, but NOT the newline. So the first time you hit line 4, it reads from after inputs, to the end of the line. To consume the newline after
inputs, add:cin >> ws;
Right after line 1. This will consume any whitespace that follows
inputs.
You aren't really gaining anything by using int8_t and uint8_t instead of int. Just make them ints and get rid of all the casts.
I don't see why you need to store the moves. Once they're on the board, they're done. You don't really need to refer to previous moves (do you?), except perhaps the last move, if that simplifies things.
You don't need an array for turn. Storing the one who went first is good enough, although in regular tic-tac-toe X always goes first, so maybe you don't need to store that at all (the turn number would tell you whose turn it is).
gameOver repeats the code of winner. It could just call winner instead.
If they're expecting a function like the recursive one they show to work for their input then your TLE might be due to your code getting into an infinite loop with some inputs.
I don't see why you need to store the moves. Once they're on the board, they're done. You don't really need to refer to previous moves (do you?), except perhaps the last move, if that simplifies things.
You don't need an array for turn. Storing the one who went first is good enough, although in regular tic-tac-toe X always goes first, so maybe you don't need to store that at all (the turn number would tell you whose turn it is).
gameOver repeats the code of winner. It could just call winner instead.
|
|
If they're expecting a function like the recursive one they show to work for their input then your TLE might be due to your code getting into an infinite loop with some inputs.
Last edited on
> for (int m = 0; m < 10; m++){ //make each possible move to output the winner.
¿there are 10 possible moves?
I would have guess that that should have to do something
¿there are 10 possible moves?
|
|
I would have guess that that should have to do something
Last edited on
ah, thanks for pointing out the error and simplification. Much appreciated.
I'm storing moves to see which play provides the optimal winner. There's still inexplicable logic error in the MakeOptimalMove that I probably have to fix (if it helps, I keep on getting the same output for whatever reason), but at least I got past the infinite loop problem
I'm storing moves to see which play provides the optimal winner. There's still inexplicable logic error in the MakeOptimalMove that I probably have to fix (if it helps, I keep on getting the same output for whatever reason), but at least I got past the infinite loop problem
Last edited on
Does this pass?
|
|
One problem is that you're copying boards all the time. Each board is at least 27 bytes by my count. That isn't much but it would still be faster if you followed the algorithm given so you can use a single board. See the underlined parts below:
function assess(side):
if some side have won:
return this side
endif
bestMove = null
bestValue = -1000000
for each (move from allPossibleMoves):
makeMove(move)
value = assess(-side)
takeBack(move)
if value * side > bestValue:
bestValue = value * side
bestMove = move
endif
endfor
return bestValue * side |
oh, I'm stupid, you could calculate value by how many 1's you have on the board, haha. Thanks for the help man. I thought you needed a bazillion boards like my school tic tac toe project suggested (though if the problem statement was to output the board with X and O then maybe the class would work)
TTT is sometimes used to explain a concept of 'transposition tables' where you have every possible state of the game (rotated and mirrored boards are redundant so you only need a fraction of the # of states of possible board positions). And some positions are illegal and omitted (eg any board with 3 xs and 1 o is not legal).
this results in a bloated obnoxious program to illustrate the point (since TTT can be written in just a few lines of code). Kind of like using factorials to show recursion, when a lookup table of a few values is the better answer.
this results in a bloated obnoxious program to illustrate the point (since TTT can be written in just a few lines of code). Kind of like using factorials to show recursion, when a lookup table of a few values is the better answer.
Last edited on
Topic archived. No new replies allowed.