I've been working on a project for my Java class. In this project, we create a simple Tic-Tac-Toe game with a pretty GUI, all of that is swell, I made it work just fine. I ran into my problem when I got to checking if one of the two players has won.
The game is 2 player, no AI, as of right now but that wouldn't really impact the algorithm needed to check if the player is a winner or not. The variable that makes it difficult for me is that the board size can be changed from 3x3 to 4x4 to 5x5 --> 1,000x1,000 and beyond. I need a way to check if the player won regardless of the board size.
The 2 algorithms I could think of are:
Algorithm 1:
1. Go through every row HORIZONTALLY, add 1 to an integer if its an x, 1 to a different integer if its an o, and then check the next slot, if it is the same as the previous, add another point, if it is null or the opposite, reset the points to 0, and restart, continuing in place down the row.
2. Go through every row VERTICALLY, do the same method of points ^.
3. Go through every DIAGONAL going down to the LEFT, same method of points ^.
4. Go through every DIAGONAL going down to the RIGHT, same method of points ^.
*** The Diagonal Methods here would have to exclude the corner pieces so we don't get an OOB error.
Pros: Less coding Easier to code Cons: Does more computer than Algorithm 2 Not as "smart" What happens if board size is 1,000,000 --> So many more computations to complete...
Algorithm 2:
This algorithm would take the spot you just played and...
1. Check up 2, if they are both the same as played you win.
2. Check up 1, check down 1, if they are both the same as played you win.
3. Check down 2, if they are both the same as played you win.
4. Check right 2, if they...
5. Check right 1, left 1 if they...
6. Check left 2, if they ...
7. Check upwards right diag 2, if they..
8. Check upward right diag 1, check downward left diag 1, if they...
9. Check downwards 2, if they...
10. Check upwards left diag 2, if they...
11. Check upwards left diag 1, check downwards right diag 1, if they...
12. Check downwards right 2, if they...
Pros: Less Computing at larger map sizes Looks like I'm smarter, code is "smarter" Would work with small maps just as fast and big maps Cons: More coding Harder Code
I doubt my teacher expects anyone else in the class to do this properly, but I want to because it shouldn't be left unfinished.
What are you opinions? Should I go with Algorithm 1 or 2 -- and is there a better 3rd one I'm missing?
I'm leaning towards Algorithm 2, but I only have like 2.5-3 days to finish everything.
Algorithm 2 would be the way to go, and frankly probably a lot easier than 1 to code anyway. The naive version would check exactly the 12 conditions you state.
An even faster version could check one adjacent first and not even bother checking the 2-away spots if it doesn't have to. For example, with the relevant spots on the board as follows:
00 02 04
11 12 13
20 21 XX 23 24
31 32 33
40 42 44
If spot 12 were a blank or an O, neither the 02-12-XX nor the 12-XX-32 win conditions will be possible. But the question is if this is really worth the hassle (hint: the answer is going to be No, this is a microoptimization.) The resulting nested-if statements will also be harder to read than 12 simple checks. So I would go with your second algorithm, with bounds checking of course.