Answers.Body: <blockquote>
  <p>I don't get why the (a).i. uses (,) coordinates whereas (b).i. uses boolean list. I guess they can be used interchangeablly right?</p>
  </blockquote>
  <p>No these cannot be used interchangeably. The situations really are different enough that completely different state representations are necessary.</p>
  <p>In the case of (a) you know the current bug's location, and nothing else about the problem changes over time. So any state representation that captures a single bug's location is valid. The (x,y) coordinates are a natural choice given the framing of the question, but also you could enumerate all the possible grid positions for the bug, giving the same size of state space.</p>
  <p>In case of (b) you <em>do not know</em> where either bug is, but you don't need to care about the difference between each bug to track it separately (this is becasue your goal state does not rely on the identity of either bug). Therefore the state representation has to capture where any bug could possibly be.</p>
  <p>The proposed solution is simple, but you could also do it by tracking possible locations of each bug. That could work with <span class="math-container">$17^2$</span> <span class="math-container">$(x_1,y_1,x_2,y_2)$</span> tuples initialised to all possible position combinations that the two bugs start in. The state space in that case is large (it is not just <span class="math-container">$17^2$</span>, but includes all valid reachable combinations of the combined <span class="math-container">$17^2$</span> <span class="math-container">$(x_1,y_1,x_2,y_2)$</span> tuples) and difficult to assess because many state combinations are not reachable. Also note this alternative proposal does differentiate between the bugs - you could potentially improve upon that by removing start states that simply swap between bug locations, although this is still not as efficient as the binary representation.</p>
  <p>Technically the proposed solution for (b) also works the same for any number of bugs that are spread out in the maze and want to all be in the same location at the end.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-02-25T12:03:09.177Z
Answers.Text: Didnt get 2nd last paragraph from "The state space in that case is large...".  For single flea maze, representation $(x,y)$ will have $M\times N$ state space, while boolean list will have $2^{M\times N}$ state space. For two bug maze, representation $(x_1,y_1,x_2,y_2)$ will have $(M\times N)^2$ state space, while boolean list will have $2^{M\times N}$ state space. We prefer $(x,y)$ representation for single flea maze since $M\times N < 2^{M\times N}$. But for two bug maze, why we prefer boolean list representation and not $(x_1,y_1,x_2,y_2)$ representation, since $(M\times N)^2<2^{M\times N}$?
Answers.UserDisplayName: Mahesha999
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-02-25T13:57:38.283Z
Answers.Text: The two bug version does **not** have $(M \times N)^2$ state space, because you do not know where the bugs are. The state space has to cover all possible locations that the bugs could be at the same time. Hence the representation starts as $17^2$ instances of the tuple, covering all combinations of start positions - that is the representation of the *single* starting state. This is a key part of the problem.
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-02-25T14:04:22.133Z
Answers.Text: Sorry, am unable to get how not knowing where the bugs are makes it not to have $(M\times N)^2$ space? Also, with $(x_1,y_1,x_2,y_2)$ representation, first bug is at $(x_1,y_1)$ and second bug is at $(x_2,y_2)$. Doesnt that cover all possible locations that the bugs could be at the same time?
Answers.UserDisplayName: Mahesha999
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-02-25T14:16:24.290Z
Answers.Text: @anir: The state represents *your* current knowledge, not a hypothetical position in a simulation that internally knows where the bugs are. If you don't know where the bugs are, and they could be anywhere, the state needs to represent that fact in a data structure somehow. The binary representation in the answer you posted does this efficiently. If you use (x,y) coordinates, then you need a way to represent which (x,y) vales are *currently possible* (my suggestion as an alternative here to help you understand). A single (x,y) position (or just two) is not useful to resolve the problem
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-02-25T14:24:21.917Z
Answers.Text: It may help if you understand the solution to second problem. It will be something like W, W, W, W, S, S, E, E, E, S, S - if you can understand why that is a good solution, it may be another way to help you visualise how the binary representation works (and why a coordinate-based system is more complex)
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-02-25T11:38:42.423Z
Answers.LastActivityDate: 2021-02-25T11:38:42.423Z
Answers.UserDisplayName: Neil Slater
Body: <p>I came across <a href="https://inst.eecs.berkeley.edu/%7Ecs188/sp12/section_handouts/sp12-midterm1-soln.pdf" rel="nofollow noreferrer">this question</a> set. It asks following question:</p>
  <blockquote>
  <p>Let’s revisit our bug friends from assignment 2. To recap, you control one or more insects in a rectangular maze-like environment with dimensions M × N , as shown in the figures below. At each time step, an insect can move North, East, South, or West (but not diagonally) into an adjacent square if that square is currently free, or the insect may stay in its current location. Squares may be blocked by walls (as denoted by the black squares), but the map is known.<br />
  For the following questions, you should answer for a general instance of the problem, not simply for the example maps shown.</p>
  <p><strong>(a)</strong> You now control a single flea as shown in the maze above, which must reach a designated target location X. However, in addition to moving along the maze as usual, your flea can jump on top of the walls. When on a wall, the flea can walk along the top of the wall as it would when in the maze. It can also jump off of the wall, back into the maze. Jumping onto the wall has a cost of 2, while all other actions (including jumping back into the maze) have a cost of 1. Note that the flea can only jump onto walls that are in adjacent squares (either north, south, west, or east of the flea).<br />
  <a href="https://i.sstatic.net/z3wGM.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/z3wGM.png" alt="enter image description here" /></a><br />
  <strong>i.</strong> Give a minimal state representation for the above search problem.<br />
  <strong>Sol.</strong> The location of the flea as an (x, y) coordinate.<br />
  <strong>ii.</strong> Give the size of the state space for this search problem.<br />
  <strong>Sol.</strong> M ∗ N</p>
  <p><strong>(b)</strong> You now control a pair of long lost bug friends. You know the maze, but you do not have any information about which square each bug starts in. You want to help the bugs reunite. You must pose a search problem whose solution is an all-purpose sequence of actions such that, after executing those actions, both bugs will be on the same square, regardless of their initial positions. Any square will do, as the bugs have no goal in mind other than to see each other once again. Both bugs execute the actions mindlessly and do not know whether their moves succeed; if they use an action which would move them in a blocked direction, they will stay where they are. Unlike the flea in the previous question, bugs cannot jump onto walls. Both bugs can move in each time step. Every time step that passes has a cost of one.<br />
  <a href="https://i.sstatic.net/vQq17.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/vQq17.png" alt="enter image description here" /></a><br />
  <strong>i.</strong> Give a minimal state representation for the above search problem.<br />
  <strong>Sol.</strong> A list of boolean variables, one for each position in the maze, indicating whether the position could contain a bug. You don’t keep track of each bug separately because you don’t know where each one
  starts; therefore, you need the same set of actions for each bug to ensure that they meet.<br />
  <strong>ii.</strong> Give the size of the state space for this search problem.<br />
  <strong>Sol.</strong> <span class="math-container">$2^{MN}$</span></p>
  </blockquote>
  <p>I don't get why the (a).i. uses <span class="math-container">$(x,y)$</span> coordinates whereas (b).i. uses boolean list. I guess they can be used interchangeablly right? And correspondingly the answers to ii will change.</p>
  <p><strong>Update</strong></p>
  <p>I now understand following:</p>
  <blockquote>
  <p>For single flea maze, the representation <span class="math-container">$(x,y)$</span> will have <span class="math-container">$M\times N$</span> state space, whereas boolean list will have <span class="math-container">$2^{M\times N}$</span> state space. For two bug maze, the representation <span class="math-container">$(x_1,y_1,x_2,y_2)$</span> will have <span class="math-container">$(M\times N)^2$</span> state space, whereas boolean list will have <span class="math-container">$2^{M\times N}$</span> state space. I am able to understand, we prefer <span class="math-container">$(x,y)$</span> representation for single flea maze since <span class="math-container">$M\times N &lt; 2^{M\times N}$</span>. But for two bug maze, I am not able to understand why we prefer boolean list representation (and not <span class="math-container">$(x_1,y_1,x_2,y_2)$</span> representation), since <span class="math-container">$(M\times N)^2&lt;2^{M\times N}$</span>.</p>
  </blockquote>
  
Tags: <game-ai><search><heuristics>
Title: Determining minimal state representation for maze game
UserDisplayName: Mahesha999
ThreadText: # Determining minimal state representation for maze game
  
  (Asked by: username_0 on 2021-02-25)
  
  I came across [this question](https://inst.eecs.berkeley.edu/%7Ecs188/sp12/section_handouts/sp12-midterm1-soln.pdf) set. It asks following question:
  
  > Let’s revisit our bug friends from assignment 2. To recap, you control one or more insects in a rectangular maze-like environment with dimensions M × N , as shown in the figures below. At each time step, an insect can move North, East, South, or West (but not diagonally) into an adjacent square if that square is currently free, or the insect may stay in its current location. Squares may be blocked by walls (as denoted by the black squares), but the map is known.  
  > For the following questions, you should answer for a general instance of the problem, not simply for the example maps shown.
  >
  > **(a)** You now control a single flea as shown in the maze above, which must reach a designated target location X. However, in addition to moving along the maze as usual, your flea can jump on top of the walls. When on a wall, the flea can walk along the top of the wall as it would when in the maze. It can also jump off of the wall, back into the maze. Jumping onto the wall has a cost of 2, while all other actions (including jumping back into the maze) have a cost of 1. Note that the flea can only jump onto walls that are in adjacent squares (either north, south, west, or east of the flea).  
  > [![enter image description here](https://i.sstatic.net/z3wGM.png)](https://i.sstatic.net/z3wGM.png)  
  > **i.** Give a minimal state representation for the above search problem.  
  > **Sol.** The location of the flea as an (x, y) coordinate.  
  > **ii.** Give the size of the state space for this search problem.  
  > **Sol.** M ∗ N
  >
  > **(b)** You now control a pair of long lost bug friends. You know the maze, but you do not have any information about which square each bug starts in. You want to help the bugs reunite. You must pose a search problem whose solution is an all-purpose sequence of actions such that, after executing those actions, both bugs will be on the same square, regardless of their initial positions. Any square will do, as the bugs have no goal in mind other than to see each other once again. Both bugs execute the actions mindlessly and do not know whether their moves succeed; if they use an action which would move them in a blocked direction, they will stay where they are. Unlike the flea in the previous question, bugs cannot jump onto walls. Both bugs can move in each time step. Every time step that passes has a cost of one.  
  > [![enter image description here](https://i.sstatic.net/vQq17.png)](https://i.sstatic.net/vQq17.png)  
  > **i.** Give a minimal state representation for the above search problem.  
  > **Sol.** A list of boolean variables, one for each position in the maze, indicating whether the position could contain a bug. You don’t keep track of each bug separately because you don’t know where each one
  > starts; therefore, you need the same set of actions for each bug to ensure that they meet.  
  > **ii.** Give the size of the state space for this search problem.  
  > **Sol.** $2^{MN}$
  
  I don't get why the (a).i. uses $(x,y)$ coordinates whereas (b).i. uses boolean list. I guess they can be used interchangeablly right? And correspondingly the answers to ii will change.
  
  **Update**
  
  I now understand following:
  
  > For single flea maze, the representation $(x,y)$ will have $M\times N$ state space, whereas boolean list will have $2^{M\times N}$ state space. For two bug maze, the representation $(x\_1,y\_1,x\_2,y\_2)$ will have $(M\times N)^2$ state space, whereas boolean list will have $2^{M\times N}$ state space. I am able to understand, we prefer $(x,y)$ representation for single flea maze since $M\times N < 2^{M\times N}$. But for two bug maze, I am not able to understand why we prefer boolean list representation (and not $(x\_1,y\_1,x\_2,y\_2)$ representation), since $(M\times N)^2<2^{M\times N}$.
  
  **Tags:** game-ai, search, heuristics
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2021-02-25. Score: 0
  
  > I don't get why the (a).i. uses (,) coordinates whereas (b).i. uses boolean list. I guess they can be used interchangeablly right?
  
  No these cannot be used interchangeably. The situations really are different enough that completely different state representations are necessary.
  
  In the case of (a) you know the current bug's location, and nothing else about the problem changes over time. So any state representation that captures a single bug's location is valid. The (x,y) coordinates are a natural choice given the framing of the question, but also you could enumerate all the possible grid positions for the bug, giving the same size of state space.
  
  In case of (b) you *do not know* where either bug is, but you don't need to care about the difference between each bug to track it separately (this is becasue your goal state does not rely on the identity of either bug). Therefore the state representation has to capture where any bug could possibly be.
  
  The proposed solution is simple, but you could also do it by tracking possible locations of each bug. That could work with $17^2$ $(x\_1,y\_1,x\_2,y\_2)$ tuples initialised to all possible position combinations that the two bugs start in. The state space in that case is large (it is not just $17^2$, but includes all valid reachable combinations of the combined $17^2$ $(x\_1,y\_1,x\_2,y\_2)$ tuples) and difficult to assess because many state combinations are not reachable. Also note this alternative proposal does differentiate between the bugs - you could potentially improve upon that by removing start states that simply swap between bug locations, although this is still not as efficient as the binary representation.
  
  Technically the proposed solution for (b) also works the same for any number of bugs that are spread out in the maze and want to all be in the same location at the end.
  
  > **Comments:**
  > **username_0**: Didnt get 2nd last paragraph from "The state space in that case is large...".  For single flea maze, representation $(x,y)$ will have $M\times N$ state space, while boolean list will have $2^{M\times N}$ state space. For two bug maze, representation $(x_1,y_1,x_2,y_2)$ will have $(M\times N)^2$ state space, while boolean list will have $2^{M\times N}$ state space. We prefer $(x,y)$ representation for single flea maze since $M\times N < 2^{M\times N}$. But for two bug maze, why we prefer boolean list representation and not $(x_1,y_1,x_2,y_2)$ representation, since $(M\times N)^2<2^{M\times N}$?  
  > **username_1**: The two bug version does **not** have $(M \times N)^2$ state space, because you do not know where the bugs are. The state space has to cover all possible locations that the bugs could be at the same time. Hence the representation starts as $17^2$ instances of the tuple, covering all combinations of start positions - that is the representation of the *single* starting state. This is a key part of the problem.  
  > **username_0**: Sorry, am unable to get how not knowing where the bugs are makes it not to have $(M\times N)^2$ space? Also, with $(x_1,y_1,x_2,y_2)$ representation, first bug is at $(x_1,y_1)$ and second bug is at $(x_2,y_2)$. Doesnt that cover all possible locations that the bugs could be at the same time?  
  > **username_1**: @anir: The state represents *your* current knowledge, not a hypothetical position in a simulation that internally knows where the bugs are. If you don't know where the bugs are, and they could be anywhere, the state needs to represent that fact in a data structure somehow. The binary representation in the answer you posted does this efficiently. If you use (x,y) coordinates, then you need a way to represent which (x,y) vales are *currently possible* (my suggestion as an alternative here to help you understand). A single (x,y) position (or just two) is not useful to resolve the problem  
  > **username_1**: It may help if you understand the solution to second problem. It will be something like W, W, W, W, S, S, E, E, E, S, S - if you can understand why that is a good solution, it may be another way to help you visualise how the binary representation works (and why a coordinate-based system is more complex)  
  
  ---
  
  