Computer Science Canada

Detecting a Diagonal Win
Author:  Aange10 [ Mon Dec 19, 2011 9:29 pm ]
Post subject:  Detecting a Diagonal Win
What is it you are trying to achieve?
I'd like to figure out a way to detect a diagonal win in Tic-Tac-Toe without hardcoding anything.


What is the problem you are having?
I've not been able to find a correct algorithm/concept to do this.


Describe what you have tried to solve this problem
Originally, I figured I'd try something like

code:

if grid(x + e, y + e).state = "on" then
    dCounter += 1
end if
% Win if the counter gets to 3 (All the diagonals were "on")


where e was a for going through the number of (x columns - 1), (ex: for : 1 .. 2 )


Post any relevant code (You may choose to attach the file instead of posting the code if it is too long)
I solved my problem, but it's awfully hard coded Sad. I'd like something that would work if I were using a 3x3 grid (tic tac toe) or a 900x900 grid. Meaning me not hardcoding how to find the answer.

Turing:

% Where the vCounter is the number of 'Hits' for the diagonal detection
% Where pSymbol is the state I'm checking for.

% Detect Diagnol BL > TR
    if win = false then
        for e : 0 .. 2
            if grid (1 + e, 1 + e).state = pSymbol then
                vCounter += 1
            end if
            if vCounter = 3 then
                win := true
                exit
            end if
        end for
        vCounter := 0
    end if

    % Detect Diagnol BR > TL
    if win = false then
        for e : 0 .. 2
            if grid (3 - e, 3 - e).state = pSymbol  then
                vCounter += 1
            end if
            if vCounter = 3 then
                win := true
                exit
            end if
        end for
    end if



Please specify what version of Turing you are using
4.1
Author:  Insectoid [ Mon Dec 19, 2011 9:30 pm ]
Post subject:  RE:Detecting a Diagonal Win
As far as I know, there isn't a nice way to do it. But, hard-coding it is only 2 lines, so no big deal.
Author:  Aange10 [ Mon Dec 19, 2011 9:39 pm ]
Post subject:  RE:Detecting a Diagonal Win
BTW

Turing:

if grid (3 - e, 3 - e).state = pSymbol  then


should be

Turing:

if grid (3 - e, 1 + e).state = pSymbol  then



But, weren't you the one who said 'In Computer Science, ff it's not the best way to do it, it's wrong.'?
Author:  Tony [ Mon Dec 19, 2011 9:48 pm ]
Post subject:  RE:Detecting a Diagonal Win
The "nice way to do it" is to ask a different question. Instead of "is there victory anywhere on the board" (this does a lot of useless work), a better question is "was the last move a winning move?"

Then the problem becomes much easier, and you can use the same block of code to check for horizontal, vertical, and diagonal line completions by using trig and spinning around the last move's location.
Author:  Insectoid [ Mon Dec 19, 2011 9:54 pm ]
Post subject:  RE:Detecting a Diagonal Win
Quote:
But, weren't you the one who said 'In Computer Science, ff it's not the best way to do it, it's wrong.'?


Sometimes hard-coding IS the best way.
Author:  Aange10 [ Mon Dec 19, 2011 10:23 pm ]
Post subject:  Re: RE:Detecting a Diagonal Win
Insectoid @ 19/12/2011, 8:54 pm wrote:
Quote:
But, weren't you the one who said 'In Computer Science, ff it's not the best way to do it, it's wrong.'?


Sometimes hard-coding IS the best way.


I see, I see.


Quote:


Then the problem becomes much easier, and you can use the same block of code to check for horizontal, vertical, and diagonal line completions by using trig and spinning around the last move's location.


That sounds Amazing. If I knew how to do it; do you by chance have a wiki link or an old PDF? I don't know trig very well, but meh, math is math.

Also, to check if the next move is a winning move sounds much cleaner. I could see how I could take a move and detect if there is a win horizontally/Vertically of it [like you said], but I'm not sure what'd I'd do to check diagonally.

The only thing that comes to mind is to do something like

code:

* Clicks a square
if clicked square = TopLeft then
    grid (x + e, x - e)
elsif
.
.
.


which would pretty much say 'If it's on the bottom left, check up-right, if bottom right check up left' ... etc, which, seems counter productive; I'm pretty much doing that now.
Author:  Tony [ Mon Dec 19, 2011 11:17 pm ]
Post subject:  RE:Detecting a Diagonal Win
that wouldn't work, if the winning move was done in the center instead of a corner. How are you checking for horizontal/vertical?
Author:  Aange10 [ Mon Dec 19, 2011 11:28 pm ]
Post subject:  RE:Detecting a Diagonal Win
I suppose the same way I wrapped text when I was using ASCII values in my encryptor... If while going up, it goes past 3, then subtract 2 from it. (it would check 2 > 3 > 1)

But that's not my problem Sad
Author:  Tony [ Mon Dec 19, 2011 11:52 pm ]
Post subject:  RE:Detecting a Diagonal Win
Presumably you are doing this in a loop, where each iteration does +1 in <direction>. If you can figure out how to programatically control that direction (that is, switch between +1x, +0y for horizontal to +0x, +1y for vertical; and +1x,+1y for diagonal), then you are almost done.
Author:  RandomLetters [ Mon Dec 19, 2011 11:58 pm ]
Post subject:  Re: Detecting a Diagonal Win
Just one way to do it, and you may or may not want to try it (I dont really understand what your data structure looks like)

code:


Length(current location, direction)
   If next location has the same token,
        Return Length(next location, direction) + 1
   Return 0
End



We start at a point on the grid, and go in a direction. For each token (say, O), that matches what we need, we add 1 point, and stop when we dont see the token that we want.

Thus, we can find a total length by adding together the two lengths in opposite directions, and repeating this for every pi/4 angle

Length(current location, direction) + Length(current location, direction+pi) - 1

subtracting one result for the repeated starting location (assuming that you always start on a token that's valid i.e. your move). Of course, you will need to find the coordinates of new locations using trig and the direction as well as check for array bounds

For tic tac toe, it's faster to hard code it (not that speed matters for tic tac toe), but this should work for any game where you connect straight lines (I dont know, I've never used it Razz)
Author:  Aange10 [ Tue Dec 20, 2011 12:40 am ]
Post subject:  RE:Detecting a Diagonal Win
xD I hate reading something, and then just stop comprehending. Makes me feel like a mindless monkey with a banana Very Happy.

Back on topic:

Quote:

(I dont really understand what your data structure looks like)


Pretty much I have a grid (x, y) multi-dimensional array. (1,1) would be the Top Left slot, (2,1) would be the Top Middle, etc. (So (3,3) would be the bottom right)

I check the box by seeing the state (0 = blank , 1 = x, 2 = o). So my statements go
code:

if grid (x,y).state = playerSymbol

and playerSymbol is either 1 or 2. (X or O).

All pretty simple.


As for everything else, I don't really understand it. I understand the adding the two directions, but why pi/4? I also don't see how the [ code ] you listed would implement that pi/4.


And uggh for trig. I always said I was going calc instead, but I've seen so much trig I might just have to take it next year Sad.
Author:  Tony [ Tue Dec 20, 2011 12:55 am ]
Post subject:  Re: RE:Detecting a Diagonal Win
pi/4 radians == 45 degrees; that is, the diagonal line.

Aange10 @ Tue Dec 20, 2011 12:40 am wrote:
(0 = blank , 1 = x, 2 = o)

You might find that:
code:

0 = blank
1 = X
-1 = O

is a lot easier to work with. You can alternate between the two players by multiplying playerID by -1, and check for complete lines by simply adding up the values and looking at the total, instead of using an if-check-then-counter at every step.
Author:  Aange10 [ Tue Dec 20, 2011 2:53 am ]
Post subject:  RE:Detecting a Diagonal Win
Thank you! I'll definitely remember that tip. So many nifty people online. All my shortcuts become miniscule compared to the advise I get Wink.


Anyways the Tic Tac Toe is done (: I need to clean up the code a bit w/ comments and what not, so I'll wait to post it tomorrow. However I'm very pleased.

Also does == just mean =? Assume == does mean =, then great. It makes a lot more since now.
Author:  Tony [ Tue Dec 20, 2011 11:05 am ]
Post subject:  RE:Detecting a Diagonal Win
yeah, in just about every language other than Turing = is for assignment and == is for comparison.

:


You can syndicate this boards posts using the file backend.php or view the topic map using sitemap.php.

Terms of Use | Privacy Policy