Answers.Body: <p>If I've understood the logic correctly, the player tries to build a wall such that the enemy cannot reach the player in any way. This can normally be determined by some path-finding algorithms, Dijkstra Shortest Path algorithm being a reasonable choice for the setting and grid-size. 
  This algorithm explores the possible paths from a starting point to one or multiple end points, and usually returns the shortest path to the point(s). If there is no path to the mentioned point, it will not return anything, and you will know the two points are blocked from reaching each other.</p>
  
  <p>Of course, if I've truly understood the rules correctly, the bigger question is how to avoid having the player just build a wall around themselves to block of the enemy instead, which is likely going to be trivially easy. And additionally rule of requiring the player to be in the "room" with the bigger area after a room has been blocked off (Something which coincidentally also could be done by extending the Dijkstra's algorithm a bit with custom logic)</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-07-29T19:40:00.160Z
Answers.Text: Dijkstra's would give you the shortest path between the starting point and the end point, but the problem is that you don't know what the end point is. You are actually searching for the end point.  
  Also, OP mentions that the algorithm should block off the enemy by allowing him as little space as possible. If you just build a wall around yourself the you allow the enemy the largest space possible.
Answers.UserDisplayName: pi-tau
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-11-22T14:49:20.260Z
Answers.LastActivityDate: 2019-11-22T14:49:20.260Z
Answers.UserDisplayName: Kazesui
Body: <p>Imagine a game played on a 10x10 grid system where a player can move up down left or right and imagine there are two players on this grid: An enemy and you. In this game, there are walls on the grid which you can't go through. The objective of this game is to block the enemy in so he can't move around the rest of the board and is effectively "trapped". </p>
  
  <p>I want to write an algorithm that detects which nodes on the board I as a player need to put blocks in, in order to trap the enemy. There are also some other considerations to think about. You have to be able to place the blocks before the enemy place can get out of the box. Also note more thing: You can move AND place a block in the position that you're moving to at the same time. </p>
  
  <p>Here's a picture as an example of the game.</p>
  
  <p><a href="https://i.sstatic.net/LQXVc.jpg" rel="noreferrer"><img src="https://i.sstatic.net/LQXVc.jpg" alt="enter image description here"></a></p>
  
  <p>EDIT: note that the board in the picture is 5x5, but that's okay for the purposes of the example</p>
  
  <p>In this example, I could go up, then right and place a block, then right and place a block, then up and place a block. If there's more than one way of blocking off the enemy, then I should use the way that's going to give my enemy the least amount of space. </p>
  
  <p>Researching on google couldn't find me anything relevant, although it may have been because I wasn't using relevant search terms. I also thought about using a monte Carlo search tree algorithm for simultaneous games, but I would need to research into that more. </p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-11-16T17:24:45.370Z
Comments.Text: @SakthiSomaskandan Nope, I ended up giving up on it. It seemed like any solution I would end up with was either a heuristic or its runtime was unacceptable for my time constraints. Good luck with your own work. Please let me know if you find something promising in your research. I'm still curious about this.
Comments.UserDisplayName: Ahmed 
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-11-06T15:40:28.967Z
Comments.Text: Any progress on this problem statement as I'm looking for an algorithm to do the same? I've already implemented A* algorithm to find the shortest path to the enemy but not sure how to go about trapping the enemy in its own space.
Comments.UserDisplayName: Sakthi Somaskandan
Tags: <game-ai><monte-carlo-tree-search>
Title: How could an AI detect whether an enemy in a game can be blocked off/trapped?
UserDisplayName: Ahmed 
ThreadText: # How could an AI detect whether an enemy in a game can be blocked off/trapped?
  
  (Asked by: username_0 on 2019-11-21)
  
  Imagine a game played on a 10x10 grid system where a player can move up down left or right and imagine there are two players on this grid: An enemy and you. In this game, there are walls on the grid which you can't go through. The objective of this game is to block the enemy in so he can't move around the rest of the board and is effectively "trapped".
  
  I want to write an algorithm that detects which nodes on the board I as a player need to put blocks in, in order to trap the enemy. There are also some other considerations to think about. You have to be able to place the blocks before the enemy place can get out of the box. Also note more thing: You can move AND place a block in the position that you're moving to at the same time.
  
  Here's a picture as an example of the game.
  
  [![enter image description here](https://i.sstatic.net/LQXVc.jpg)](https://i.sstatic.net/LQXVc.jpg)
  
  EDIT: note that the board in the picture is 5x5, but that's okay for the purposes of the example
  
  In this example, I could go up, then right and place a block, then right and place a block, then up and place a block. If there's more than one way of blocking off the enemy, then I should use the way that's going to give my enemy the least amount of space.
  
  Researching on google couldn't find me anything relevant, although it may have been because I wasn't using relevant search terms. I also thought about using a monte Carlo search tree algorithm for simultaneous games, but I would need to research into that more.
  
  **Tags:** game-ai, monte-carlo-tree-search
  
  > **Comments:**
  > **username_1**: Any progress on this problem statement as I'm looking for an algorithm to do the same? I've already implemented A* algorithm to find the shortest path to the enemy but not sure how to go about trapping the enemy in its own space.  
  > **username_0**: @username_1 Nope, I ended up giving up on it. It seemed like any solution I would end up with was either a heuristic or its runtime was unacceptable for my time constraints. Good luck with your own work. Please let me know if you find something promising in your research. I'm still curious about this.  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_2 on 2019-11-22. Score: -1
  
  If I've understood the logic correctly, the player tries to build a wall such that the enemy cannot reach the player in any way. This can normally be determined by some path-finding algorithms, Dijkstra Shortest Path algorithm being a reasonable choice for the setting and grid-size.
  This algorithm explores the possible paths from a starting point to one or multiple end points, and usually returns the shortest path to the point(s). If there is no path to the mentioned point, it will not return anything, and you will know the two points are blocked from reaching each other.
  
  Of course, if I've truly understood the rules correctly, the bigger question is how to avoid having the player just build a wall around themselves to block of the enemy instead, which is likely going to be trivially easy. And additionally rule of requiring the player to be in the "room" with the bigger area after a room has been blocked off (Something which coincidentally also could be done by extending the Dijkstra's algorithm a bit with custom logic)
  
  > **Comments:**
  > **username_3**: Dijkstra's would give you the shortest path between the starting point and the end point, but the problem is that you don't know what the end point is. You are actually searching for the end point.   Also, OP mentions that the algorithm should block off the enemy by allowing him as little space as possible. If you just build a wall around yourself the you allow the enemy the largest space possible.  
  
  ---
  
  