Hey, I've been programming for a quite long time but all AI in my games were limited to simple checks and I don't know any specific algorithms.
But now I have to write an AI for my board game. I don't know how much I should explain for you to be able to give me a proper algorithm name or point out some proper solution. But it is tile based, I have a man, he can only walk for X tiles.And there are points on the map which he should collect, how can I make the computer calculate the maximum "points" a player could collect?
Thanks.. by the way I'll write this algorithm in Java but that shouldnt effect the solution I guess.
What kind of algorithm
If X is small, the a brute force algorithm would work simply enough. This sounds like the "travelling salesman" problem - Google it for more information. Are the points the same on each target tile, or can different tiles have different points values?
Author
Thanks for the fast response:)
There are two types of points, one's score is higher, I forgot to say but that should be an important thing.The other tiles are just empty.
The X is very small actually.I guess I can do that by bruteforcing but I want to start implementing those kinds of algorithms.
I checked wikipedia for that travelling sales-man problem but I can't see clearly where my problem and that intersect.Because mine is more like a traveling sales-man in a car with limited fuel. And because 2 different points have different scores it gets a little bit more complicated
There are two types of points, one's score is higher, I forgot to say but that should be an important thing.The other tiles are just empty.
The X is very small actually.I guess I can do that by bruteforcing but I want to start implementing those kinds of algorithms.
I checked wikipedia for that travelling sales-man problem but I can't see clearly where my problem and that intersect.Because mine is more like a traveling sales-man in a car with limited fuel. And because 2 different points have different scores it gets a little bit more complicated
You could use a varation of A* to solve this problem, or bredth first search.
As it sounds like what you are trying to calculate is given X number of moves what path generates the highest score.
As it sounds like what you are trying to calculate is given X number of moves what path generates the highest score.
The problem:
- You have a player who can take X steps.
- He walks on a map with many more than X tiles.
- The tiles have different amounts of money on them.
- Determine: How much money can the player pick up?
Additional comments:
- Once the player picks money up from a tile, the money is gone from that tile.
- The player is allowed to walk on tiles where he has previously been.
Solution:
If you have 'S' tiles, then it seems that you need to use dynamic programming on a state space of size S+2^S -- 'S' for the tile you're on, 2^S for 'visited' flags that tell you that the tile is no longer worth anything.
(That's not totally true as (1) you always know that the tile you're on is empty; this reduces the space to have size S+2^(S-1) (a negligible change), and (2) many states are unreachable (i.e., those where disconnected regions have 'visited' flags. Nevertheless, that's the smallest state space I can think to easily embed your problem in.)
Now, BFS has complexity O(|V| + |E|) where V and E are the vertex and edge sets. How big are these sets?
An NxN, 4-connected square grid has S=N^2 vertices. For your state space, this translates to |V|=N^2+2^(N^2). At each state, there are 4 actions you can make, so there are a total of |E|=4|V| edges.
Hence the total complexity in this case is O(5|V|) = O(2^(N^2)).
Exponential complexity. Ugh.
There are some upper bounds scattered throughout above, though, so it's possible that I've been sloppy and O(2^(N^2)) is too conservative. In particular, the reachable subset of states may be much smaller than I've recognized here.
Actually, that's a good question: Given a graph G and a vertex v, how many connected subgraphs of G are there that contain v? That's really the answer to your question. If this is substantially smaller than 2^|V| then you're back in business.
- You have a player who can take X steps.
- He walks on a map with many more than X tiles.
- The tiles have different amounts of money on them.
- Determine: How much money can the player pick up?
Additional comments:
- Once the player picks money up from a tile, the money is gone from that tile.
- The player is allowed to walk on tiles where he has previously been.
Solution:
If you have 'S' tiles, then it seems that you need to use dynamic programming on a state space of size S+2^S -- 'S' for the tile you're on, 2^S for 'visited' flags that tell you that the tile is no longer worth anything.
(That's not totally true as (1) you always know that the tile you're on is empty; this reduces the space to have size S+2^(S-1) (a negligible change), and (2) many states are unreachable (i.e., those where disconnected regions have 'visited' flags. Nevertheless, that's the smallest state space I can think to easily embed your problem in.)
Now, BFS has complexity O(|V| + |E|) where V and E are the vertex and edge sets. How big are these sets?
An NxN, 4-connected square grid has S=N^2 vertices. For your state space, this translates to |V|=N^2+2^(N^2). At each state, there are 4 actions you can make, so there are a total of |E|=4|V| edges.
Hence the total complexity in this case is O(5|V|) = O(2^(N^2)).
Exponential complexity. Ugh.
There are some upper bounds scattered throughout above, though, so it's possible that I've been sloppy and O(2^(N^2)) is too conservative. In particular, the reachable subset of states may be much smaller than I've recognized here.
Actually, that's a good question: Given a graph G and a vertex v, how many connected subgraphs of G are there that contain v? That's really the answer to your question. If this is substantially smaller than 2^|V| then you're back in business.
A lot of the approach that you choose would be based on whether you are going for an optimal mathematic solution (hard) or something that simply looks reasonable to the casual observer (less hard).
If you want mathematical optimization, then a variant of Traveling Salesman is the way to go. However, even with your truncated version, the branching factor gets out of control quickly as Emergent pointed out.
The simple "faking it" solution is to plot a path to the nearest score tile, plot a path to the nearest one from there, etc. However, that doesn't account for a situation where the nearest tile might be the only one in that direction -- therefore leading you away from the rest.
Another solution would be to lay down an influence map on the board based on the scoring tiles radiating out their presence. With this in place, you know a bit about the "center of gravity" of the scoring tiles. By combining the underlying influence information with the distance information included in the "fake it" solution above, you are now able to bias things in favor of "clusters" of scoring tiles.
For example, if a lone tile was distance 5 to the left, but the nearest of a group of scoring tiles was 7 to your right, you would select the one to the right. It is farther away, but the analysis of that squares influence map provides you with information that says, "I am not alone over here."
Once you arrive at each waypoint, you can continue to use the influence map to pick the next point with the highest "gravity" combined with the lowest distance. As you can assume, this algo will still collect "clusters" when it is near them, but when a cluster is complete, it will pick the next "cluster" rather than the next loner.
Does it guarantee optimality? No. Does it do a pretty good job of getting close? Probably. Does it look reasonably similar to how we, as humans, would approach the problem? Absolutely. And that part right there is the kicker.
If you want mathematical optimization, then a variant of Traveling Salesman is the way to go. However, even with your truncated version, the branching factor gets out of control quickly as Emergent pointed out.
The simple "faking it" solution is to plot a path to the nearest score tile, plot a path to the nearest one from there, etc. However, that doesn't account for a situation where the nearest tile might be the only one in that direction -- therefore leading you away from the rest.
Another solution would be to lay down an influence map on the board based on the scoring tiles radiating out their presence. With this in place, you know a bit about the "center of gravity" of the scoring tiles. By combining the underlying influence information with the distance information included in the "fake it" solution above, you are now able to bias things in favor of "clusters" of scoring tiles.
For example, if a lone tile was distance 5 to the left, but the nearest of a group of scoring tiles was 7 to your right, you would select the one to the right. It is farther away, but the analysis of that squares influence map provides you with information that says, "I am not alone over here."
Once you arrive at each waypoint, you can continue to use the influence map to pick the next point with the highest "gravity" combined with the lowest distance. As you can assume, this algo will still collect "clusters" when it is near them, but when a cluster is complete, it will pick the next "cluster" rather than the next loner.
Does it guarantee optimality? No. Does it do a pretty good job of getting close? Probably. Does it look reasonably similar to how we, as humans, would approach the problem? Absolutely. And that part right there is the kicker.
I should add one more thing. If the number of tiles that have prizes is small, then it'd make a lot of sense to, rather than solving the problem on your original grid, instead solve it on a graph whose nodes are the prize tiles and whose edge lengths are the lengths of the shortest paths (found by A*) between the tiles.
That said, the resulting graph is the complete graph, so although your state space might be small, your branching factor is still a little scary.
That said, the resulting graph is the complete graph, so although your state space might be small, your branching factor is still a little scary.
Quote:Original post by Emergent
I should add one more thing. If the number of tiles that have prizes is small, then it'd make a lot of sense to, rather than solving the problem on your original grid, instead solve it on a graph whose nodes are the prize tiles and whose edge lengths are the lengths of the shortest paths (found by A*) between the tiles.
That said, the resulting graph is the complete graph, so although your state space might be small, your branching factor is still a little scary.
Not necessarily. At that point, you are doing hierarchical A*. The only problem is that because you don't have a true destination, the initial heuristic is impossible to generate. It's still simplifying the problem somewhat.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
