Jump to content

  • Log In with Google      Sign In   
  • Create Account


Member Since 31 Dec 2010
Offline Last Active Aug 30 2015 12:03 PM

#5173680 Best way to traverse a 2d array to dertermine the winner in Tic-Tac-Toe

Posted by Aphton on 14 August 2014 - 01:53 PM

A simple brute-force optimization that came to mind when reading the title was:





For each cell, you can perform 3 checks: Horizontal (H), Vertical (V) and Diagonal (D(D1, D2))

But not all checks are needed for each cell, so lets see:

Cell 1: H, V, D1
Cell 2: V
Cell 3: V, D2
Cell 4: H
Cell 5: -
Cell 6: -
Cell 7: H
Cell 8: -
Cell 9: -

In case its not clear:
Cell 2: H is not needed because its covered by Cell1-H and D is simply not possible

Cell 5: H is covered by Cell4-H, Diagonals are covered by Cell1-D1 and Cell3-D2 and V is covered by Cell2-V


So this leaves you with 3x H, 3x V and 2x D checks ~ 8x Checks in total, which is much less then 36x Checks

Ofc the other solutions are much more elegant (referring to the one suggested at #5)


Edit: Oh and ofc, the traversal itself could look like this:

// Horizontal
for (int i = 0; i < 3; i++)
  ... field[(pos.x + i) % 3, pos.y] ...

// Vertical
for (int i = 0; i < 3; i++)
  ... field[pos.x, (pos.y + i) % 3] ...

// Diag 1
for (int i = 0; i < 3; i++)
  ... field[(pos.x + i) % 3, (pos.y + i) % 3] ...

// Diag 2
for (int i = 0; i < 3; i++)
  ... field[(pos.x - i) % 3, (pos.y + i) % 3] ...

Im not sure about whether C++ % (mod) handles negative numbers mathematically correctly..

#5171892 Other uses for matrices in games?

Posted by Aphton on 06 August 2014 - 09:24 AM

Sobel-Operator (Image Processing - Edge Detection)
Gaussian Elemination

#5134479 How to get good fast?

Posted by Aphton on 25 February 2014 - 12:08 PM

There is one thing I havent read here yet:
Its not only practice and study but most of it
is the will to become better! You have to actually want to become better.
There is one parallel I can think of to make it more clear:
Your whole (school-) life you have been learning and practising
"writing" - such as grammar/spelling/different types of text/...
Yet not everyone (including you), who does this, is a (good) writer..
The same applies to programming & programmers. There are many types
of em: Some like the beauty in it, some just do it because they have to
and want to get the job done, even though sloppily...
I think the best way to learn anything is to do it autodidacticly.
If you let anyone else (teacher?!) shove knowledge down your throat without
really being interested, the results will be just the same as how you learnt to write!
Try to not lose your interest.
Also, stop distracting yourself with such petty worries. Just start learning and practising ^^
To me it almost seems like procrastination xD


Oh btw, to your original question at how to actually get better in a fast and effective way:
Well, it just boils down to practising and learning, steadily! And trying out new stuff.

You can buy a book or two and get the basics down.


You should tackle some projects / ideas you think you "might" be able to do. There should

still be stuff thats new to you that you have to learn about as you go along. If you repeat this,

you will gain knowledge, little by little, over time. It will become invaluable experience!