CODEWITHSUNDEEP
algorithmgraphpath-finding
Biad Zine-Eddine
Biad Zine-Eddine

Reputation: 1

Game of pathfinding in a weighted graph

I was wondering about an optimisation problem related to graph's exploration : Suppose we have a connected weighted graph, and each vertex has between 1 and 4 connections with other vertices. Now let's say some vertices contain chocolate ,and we put on that graph at two different vertices two students both of them controlled by two AIs that have access to the position of the chocolates, the position of the other student and the graph, and at each turn, both of them can move to a connected vertex (and need K moves if the weigh of the edge is K). Finally, if a student is on a vertex containing chocolate he eats it. My question : What would the best algorithm for the AI so that the student controlled will eat more chocolate then the other ?

Thank you .

Upvotes: 0

Views: 477

Answers (1)

Jakob Lovern
Jakob Lovern

Reputation: 1341

The best approach to this would likely be using cost analysis and heuristics. Your bot has 1-4 choices it can make, so you should consider each one. What's the benefit of going up? What's the cost? If you take value as benefit - cost, then you should choose the most valuable option.

So... How do you even calculate benefit and cost, anyways? You've outlined a few conditions already. The K value is a cost. Whether there is a chocolate there is a benefit. Maybe analyze the number of chocolates adjacent to a given vertex?

But wait! You know your enemy's position, and your enemy knows yours! If you move in a given direction, it'll influence their move (If they're smart.) So you'll have to look ahead and analyze what your enemy will probably do in response to you. Chess solvers use breadth-first lookahead to plan out the best possible move via this exact system. Unfortunately, your problem is unbounded - There is no true win condition. So your bot will look ahead indefinitely (or, until it runs out of memory, anyways.) This is a problem, because calculations take time. Chess solvers get around this by imposing a time limit. They take the best move they've found by the time they run out of time.

Now, I've given you a general framework to work within. You still need to assemble it. Part of making heuristics is weighing your costs and benefits. Maybe the cost of K is insignificant compared to the benefit of getting a chocolate? Maybe it isnt? Use constant coefficients to weigh the costs and benefits.

As for finding your way through the grid, I'd take a look at Dijkstra's algorithm or A* to move.

Oh, and before I forget, here's the wikipedia article on graph traversal. You may find it useful.

Upvotes: 1

Related Questions