0
\$\begingroup\$

I have a 2d array with ground represented by 0s and the walls represented by 1s.

Player can use a LOOK command or a MOVE command. Look command returns a 5x5 array centered around the player and the player can move in any of the 4 directions. Each actions takes up a round.

I want to implement a bot that is trying to find and catch the player that can also use these commands once per round.

What is the best way to balance the use of LOOK and MOVE commands for the bot and what is an algorithm to find the best route to patrol the map in.

\$\endgroup\$
9
  • 1
    \$\begingroup\$ This reminds of the explore-exploit trade-off in AI, you might be interested in that. See also Markov decision process and Reinforcement learning. \$\endgroup\$
    – Theraot
    Nov 28, 2022 at 15:23
  • \$\begingroup\$ This looks a lot like a challenge that might be used in an AI competition, homework assignment for a computer science class, or an interview problem. If you're looking for help with one of those use cases, can you please disclose that in your question? This can guide the kinds of help users share in answers. \$\endgroup\$
    – DMGregory
    Nov 28, 2022 at 16:42
  • \$\begingroup\$ Do you know how big the area is? Does the ai retain memory of the area? Can it look through the walls? If you use move and want to go behind a wall - in case you know the way to that place, does the can the move extend further than the 5x5? Or rather, can you move to any known position in one move? \$\endgroup\$
    – Zibelas
    Nov 28, 2022 at 17:37
  • \$\begingroup\$ @DMGregory It is for a cs-coursework. \$\endgroup\$ Nov 28, 2022 at 17:38
  • \$\begingroup\$ @Zibelas AI will retain memory of the area. It can look through the walls. It can only move to any adjacent tiles. If there is a long wall, it does not know how to go behind it if it hasn't explored the edges of the wall. \$\endgroup\$ Nov 28, 2022 at 17:40

1 Answer 1

0
\$\begingroup\$

Don't let perfect be the enemy of good

"Best" is very likely unattainable. You don't know what strategy the player might use to escape. Some chasing algorithms will be good at catching some avoidance algorithms, and worse at catching others.

Tips for producing adversarial game-playing AIs in general

I'll start with my procedure (from my own college days) writing AIs to play various combinatorial games. I'm going to stop short of suggesting any specific algorithms, but that's not because I don't want to help. I don't know what your technical level is, or how long you have to write the bot. This game seems fairly complex and any useful AI for it is likely fairly involved, so the sky's the limit with how complex you want to go.

The advice I'm giving assumes that you're at least an upper-level college student with at least two weeks to work on this.

Get the simplest possible AI working

In this case, the simplest AI I can think of would be one that randomly decides to MOVE or LOOK each round, and if it MOVEs, randomly chooses the direction.

Get the simplest possible adversary working

In the question as you posed it, the adversary is the player - but it doesn't have to be! Humans are inconsistent and slow when it comes to playing games. If you want to be able to figure out what algorithms are good, you'll need a way to score them that is fast and consistent - this means writing an AI to replace the human opponent.

In this case, the simplest possible escaper is the same as the simplest possible chaser: randomly move/look every round.

Get the simplest possible gym environment working

If your professor didn't already give you one, create a program that simulates the game itself, which your two bots can play Move/Look against.

If the assignment doesn't give any description as to how the boards might be laid out, then you'll want to go with the simplest possible boards for now (in this case, I'd go with a finite rectangle of open space surrounded by walls).

Then create a gym, which scores each chaser and escaper.

  • For each chaser, (of which you only have 1 right now)
  • For each escaper/adversary, (of which you only have 1 right now)
  • For each board, (of which you only have 1 right now)
  • Play a bunch of games with random start positions for each player and score them.
    • You'll need to enforce a turn limit, as most of the time two random-walks will not intersect in any reasonable time.
  • Output the total scores in a readable format. In order, you'll likely want:
    • A total score for each chaser
    • A total score for each escaper
    • Chaser score broken down by escaper (which cats are good at catching which mice)
    • Chaser and escaper score broken down by board.
    • The full breakdown of the results of each chaser/escaper/board.

Iterate on all three

If you have an idea for a chaser that might be good, implement it, throw it in the gym, and score it against the rest. Similarly for a new escaper. Add new boards when you think of them, too (unless you know what boards your prof. will be evaluating you against). An algorithm will perform differently on an empty field, as it would for a sparsely occluded field, single-tile wide maze, multiple-tile wide maze, etc.

Try to have as many simple ideas as possible at first to seed the competition.

Whenever you make a new (working) version, leave the old version in the gym. If you make a new escaper optimization that evades your latest chaser, you might find that a version three attempts ago isn't vulnerable to the new tricks.

Specific advice for this game

For this particular game, I can think of a few things I'd probably put in, for both chasers and escapers.

Build a map of the walls

Every non-simple AI (both chaser and escaper) for this game will want to build a map as they go, and most of the time, they'll want to LOOK whenever they're about to move into unexplored space in order to avoid moving into walls.

Build a "position cloud" of where the opponent might be

If the opponent was at a certain position the last time you LOOK'd, then in the next move, they cannot be more than one space away from that position. If you'd make the same move regardless of where they are in that cloud, there's no need to LOOK again. Every time you MOVE without LOOKing, the cloud grows by one space in all directions.

In a tight maze, for example, the chaser might only need to LOOK when you're standing in an intersection - unless the rules allow the escaper to jump over the chaser if they're adjacent and both move toward each other, in which case they might need to LOOK any time when they're at the edge of the cloud, too.

An escaper is likely trying to maximize the distance between itself and the nearest edge of the chaser's cloud, while the chaser is probably trying to minimize the size of the escaper's cloud first, and then minimize the distance between itself and the farthest edge of the cloud second.

Break the game down into phases

I see this game breaking down into three phases, and a good AI for this game will want to change its behavior depending on what phase the game is in.

First, if the two players do not start close together, then the game has two phases. In the first phase, neither player has any information about where the other player is. During this phase, the Chaser wants to find the Escaper, but without any knowledge, all they can do is explore as much ground as possible. The Escaper wants to not be found, but they can also use this time to explore and plan their escape.

Second, both sides make contact. Escapers will probably try to flee toward areas they know, because they have the advantage if they know the terrain and the chaser doesn't (a simple escaper might try just backtracking their last 10 steps whenever they see the chaser). This advantage goes away as the game goes on and the chaser maps more territory.

During this phase, the chaser should prioritize mapping the territory. They have very little chance of actually catching the escaper on their home ground, but there might still be some advantage in minimizing the size of the escaper's cloud during this time (or in other words "have some rough idea of where they are"). The escaper at this point should try to cautiously map more territory, but avoid being cornered.

Finally, once the chaser has enough of a map to confidently attack, they push the game to its third phase, by aggressively trying to minimize the size of the escaper's position cloud ("cut them off and drive them into corners"). This would mean thinking multiple moves ahead. If the escaper flees into unexplored territory, they can move back to phase 2.

Sometimes it's better to guess than to LOOK

I can think of a few different escaper algorithms which will beat chasers 100% of the time if they stop to LOOK whenever they need to make a decision. Consider having an "aggression" variable that will determine how likely a chaser is to simply guess instead of LOOKing. My intuition tells me that aggression should increase with the length of the game: the longer the escaper has managed to succeed, the more likely it is that you're up against a "perfect" escaper and can't win without making guesses.

\$\endgroup\$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .