Author Topic: Tic tac tao algorithm on large area  (Read 1954 times)

0 Members and 1 Guest are viewing this topic.

Offline kolarz3

  • LV0 Newcomer (Next: 5)
  • Posts: 1
  • Rating: +0/-0
    • View Profile
Tic tac tao algorithm on large area
« on: July 29, 2013, 11:05:07 am »
I must to create algorithm for little change tic tac tao vesion. Board have 20x20 fields, you must to write 5 X or O side by side(also diagonally ). Do you know good algorith to solve this problem ?

Offline Xeda112358

  • they/them
  • Moderator
  • LV12 Extreme Poster (Next: 5000)
  • ************
  • Posts: 4687
  • Rating: +718/-6
  • Calc-u-lator, do doo doo do do do.
    • View Profile
Re: Tic tac tao algorithm on large area
« Reply #1 on: September 27, 2013, 08:41:31 am »
For this, the best algorithm is probably testing for a win.

For example, say the player places an 'O' at position (4,5). You would check:

(0,5)+(1,5)+(2,5)+(3,5)+'O'+(5,5)+(6,5)+(7,5)+(8,5) to check up/down for a string of 5 'O's
(4,1)+(4,2)+(4,3)+(4,4)+'O'+(4,6)+(4,7)+(4,8)+(4,9) to check left/right for a string of 5 'O's

And likewise you would check diagonals. This way, you do not need to scan the whole 20x20 grid, just the area around the last move.

For AI, scanning the whole grid is probably the best way. The smartest algorithm, I think, would try moves in the following order:

-searching for 4-in-a-row for the current player. If one is available, make it 5 in a row
-Else then check 4 in a row for the opponent in order to block a winning move
-check 3-in-a-row
-check 2-in-a-row
-place anywhere

I also made a matrix-based algorithm for AI that may be useful, but the size is based on the number of positions (in this case 400) and the number of possible wins (1080, I think) so it would be a pretty large matrix, compared to 9x8 for a traditional tic-tac-toe board.