?
Solved

AI Algorithm for 5-In-Row game.

Posted on 2003-03-22
9
Medium Priority
?
3,380 Views
Last Modified: 2013-12-26
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
0
Comment
Question by:DoRsal
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
9 Comments
 
LVL 8

Expert Comment

by:fl0yd
ID: 8188089
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
 
LVL 84

Accepted Solution

by:
ozo earned 300 total points
ID: 8188924
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,
(perhaps adding a little randomness)
These heurisics alone should make a decent player,
for more of a challenge you might add a lookahead with alpha-beta pruning.
0
 

Author Comment

by:DoRsal
ID: 8195818
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
Learn how to optimize MySQL for your business need

With the increasing importance of apps & networks in both business & personal interconnections, perfor. has become one of the key metrics of successful communication. This ebook is a hands-on business-case-driven guide to understanding MySQL query parameter tuning & database perf

 
LVL 84

Expert Comment

by:ozo
ID: 8195921
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 Comment

by:DoRsal
ID: 8196724
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 Comment

by:DoRsal
ID: 8196804
oh.. my misstake.. it is true as you say... i don't know what i was thinking... had something wrong with my code
0
 
LVL 84

Expert Comment

by:ozo
ID: 8199024
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 Comment

by:DoRsal
ID: 8212895
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
 

Expert Comment

by:molenjin
ID: 9414065
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

Featured Post

VIDEO: THE CONCERTO CLOUD FOR HEALTHCARE

Modern healthcare requires a modern cloud. View this brief video to understand how the Concerto Cloud for Healthcare can help your organization.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

What is RenderMan: RenderMan is a not any particular piece of software. RenderMan is an industry standard, defining set of rules that any rendering software should use, to be RenderMan-compliant. Pixar's RenderMan is a flagship implementation of …
As game developers, we quickly learn that Artificial Intelligence (AI) doesn’t need to be so tough.  To reference Space Ghost: “Moltar, I have a giant brain that is able to reduce any complex machine into a simple yes or no answer. (http://www.youtu…
This is my first video review of Microsoft Bookings, I will be doing a part two with a bit more information, but wanted to get this out to you folks.
How to fix incompatible JVM issue while installing Eclipse While installing Eclipse in windows, got one error like above and unable to proceed with the installation. This video describes how to successfully install Eclipse. How to solve incompa…
Suggested Courses

800 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question