Detecting a Diagonal Win

[Aange10]

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 . 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

[Insectoid]

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.

[Aange10]

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.'?

[Tony]

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.

[Insectoid]

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.

[Aange10]

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.

[Tony]

that wouldn't work, if the winning move was done in the center instead of a corner. How are you checking for horizontal/vertical?

[Aange10]

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

[Tony]

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.

[RandomLetters]

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 )

[Aange10]

xD I hate reading something, and then just stop comprehending. Makes me feel like a mindless monkey with a banana .

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 .

[Tony]

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.

[Aange10]

Thank you! I'll definitely remember that tip. So many nifty people online. All my shortcuts become miniscule compared to the advise I get .


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.

[Tony]

yeah, in just about every language other than Turing = is for assignment and == is for comparison.