# AI Algorithm for 5-In-Row game.

I started on a project a few days ago and made a 5-In-Row game ... a game like tic-tac-toe but with a game plan at 25*25 squares and to win you need 5 in a row. It was no problem to get this game to work on a single computer and will make it work through network too.

My question here is if anyone here has any clue on how to make a good Algorithm for an AI, I have though a lot about this and it is defiantly not easy.
Lets say the Player is X and the AI is O then a good start should perhaps be to check around where the player puts its X to se if he have any other X close to the one he just put out and then try to stop him. Like this:
'  _ _ _ _ _ _ _ _ _
' |_|_|_|_|_|_|_|_|_|
' |_|X|_|_|X|_|_|X|_|    here the X is where to check if the player put his
' |_|_|X|_|X|_|X|_|_|    mark at the 0
' |_|_|_|X|X|X|_|_|_|
' |_|X|X|X|0|X|X|X|_|
' |_|_|_|X|X|X|_|_|_|
' |_|_|X|_|X|_|X|_|_|
' |_|X|_|_|X|_|_|X|_|
' |_|_|_|_|_|_|_|_|_|

But the AI also has to think on putting its own O as good as possible to get a chance to win.

I have never done any AI stuff before and don't know if I’m thinking in the right line. Would be great if someone of you guys could give me some help and/or some hints on this.

I'm programming this game in vb.net but the language shouldn't be of so much concern, I want to know how to think to get a good algorithm for this AI in the game.

/Jesper
###### Who is Participating?

Commented:
For each row of 5 on the board, keep a count of the number of X's or O's in that row,
(If there are both X's and O's, that row of 5 can't be used for a win and can be ignored))
Then each space gets a value depending on the rows it's in
If it is in a row of 4 O's, then playing at that point is a win, and it has the maximum value
If it is in a row of 4 X's then that point blocks a win, so it has next to maximum value,
If it's in a row of 3 twice then playing there makes two 4's which is a forced win (unless there's already a row of 4)
If it's in a row of 3 and in two overlapping rows of 2, then it forces a 4 in one direction and 3 twice in another direction
Otherwise you can use a heuristic adding the values of each row that contains the space
A row with both X's and O's, cannot win, and counts 0
An empty row might have value 10, a row with 1 X might have value 20, and a row with one O might have a value of 25
(You might adjust these values to change the style of the computers play)
Then play at the space with the highest total value,
These heurisics alone should make a decent player,
for more of a challenge you might add a lookahead with alpha-beta pruning.
0

Commented:
Before I start presenting you uninformed opinions I'd rather direct your attention to this link: http://ai-depot.com/Main.html . After a short glimpse I feel that it is a rather comprehensive resource on all sorts of algorithms. I didn't find any articles dealing with the logic behind your specific game. From personal experience, I would recommend that you get an overview [doesn't have to be in-depth] over various ways to tackle AI-specific algorithms. In gathering information you will most likely be in a far better position to see the problem you are facing with much more clearity. I'm confident, that you will even be able to come up with your own algorithm.

.f
0

Author Commented:
Thanks a lot for the answers... that page seems to be very good I’ll read some there...

ozo, thanks, i think the way of using value/points is a good one i have an good idea on how to make my AI now... I’ll try program it as soon as possible and se if it works. There will be a lot of rows to check though... 8 rows on each empty square...

I think I will need to put extra points on the squares close the X's and O's so the AI places as close as possible, and then I’ll do some random if there are more than one square with the same point-value.

Thanks again. =)
0

Commented:
squares close to the X's and O's will share more rows of 5 in common with the X's or O's, so the above heuristic will naturally give more points to close squares.
0

Author Commented:
hmm... na...
If i do so in every square it checks 4 squares in every direction it want get more point if it is close. The Points around an O Should be something like this then if I have understood this correctly:
'  _ _ _ _ _ _ _ _ _
' |5|_|_|_|5|_|_|_|5|
' |_|5|_|_|5|_|_|5|_|
' |_|_|5|_|5|_|5|_|_|
' |_|_|_|5|5|5|_|_|_|
' |5|5|5|5|O|5|5|5|5|
' |_|_|_|5|5|5|_|_|_|
' |_|_|5|_|5|_|5|_|_|
' |_|5|_|_|5|_|_|5|_|
' |5|_|_|_|_|_|_|_|5|

If I give 5 points if the line includes an O.
0

Author Commented:
oh.. my misstake.. it is true as you say... i don't know what i was thinking... had something wrong with my code
0

Commented:
To clarify, if you have a row with an O
|_|_|_|_|O|_|_|_|_|
It is contained in 5 overlapping sets of 5 in a row spaces
|5|5|5|5|O|_|_|_|_|

|_|5|5|5|O|5|_|_|_|

|_|_|5|5|O|5|5|_|_|

|_|_|_|5|O|5|5|5|_|

|_|_|_|_|O|5|5|5|5|
A B C D E F G H I
The square next to the O (column D or F) belongs to 4 of those sets of 5,
so its score would be 4*5=20 points
The next square over (column C or G) belongs to 3 of those sets of 5, so its score would be 3*5=15 points
The square on the edge (column A or I) belongs to only one of those sets of 5, so its score would be 1*5=5 points

0

Author Commented:
ok... the AI works very good now... it is not perfect but hard enough for what it is builded for. Thanks again for the very great help. If i had more points to give I would but this is all I have.
0

Commented:
I have designed a "5-in-row" game long time ago. I can tell you this: if you want to design a really strong AI you MUST implement both heuristic and recursive (tree-decision) algorithm. But "cutting the tree" is the key point here, otherwise your game will think till dawn. If somebody needs more info about AI in board games please visit my programming Resume where you can find my "Closing" game, or write to my e-mail: office@business-software.org. I am willing to share source (Delphi, C++) without charge, if anyone asks..

All the Best,
Miroslav Olenjin
Perth, W. Australia
http://www.delphipages.com/resume/resume.cfm?ID=641
0