Repository: ASPP/pelita

Issue:
Add width and height to the layout dictionary
As it is needed in several places, it makes sense to just stick two additional keys into the layout dictionary. Fixing this bug also means getting rid of all `max(walls)[0]+1`, `max(walls)[1]+1`, `sorted(walls)[-1][0]`, `sorted(walls)[-1][1]` spread in the pelita and pelita_template code.

Discussion:
codecov-commenter: # [Codecov](https://codecov.io/gh/ASPP/pelita/pull/708?src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=ASPP) Report
> Merging [#708](https://codecov.io/gh/ASPP/pelita/pull/708?src=pr&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=ASPP) (a4e248c) into [master](https://codecov.io/gh/ASPP/pelita/commit/254a9f4dfd142f05999462c645fd81bc3f5a27a2?el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=ASPP) (254a9f4) will **decrease** coverage by `0.35%`.
> The diff coverage is `75.86%`.

[![Impacted file tree graph](https://codecov.io/gh/ASPP/pelita/pull/708/graphs/tree.svg?width=650&height=150&src=pr&token=xtDBW6of7R&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=ASPP)](https://codecov.io/gh/ASPP/pelita/pull/708?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=ASPP)

```diff
@@            Coverage Diff             @@
##           master     #708      +/-   ##
==========================================
- Coverage   59.36%   59.00%   -0.36%     
==========================================
  Files          32       32              
  Lines        3733     3710      -23     
==========================================
- Hits         2216     2189      -27     
- Misses       1517     1521       +4     
```


| [Impacted Files](https://codecov.io/gh/ASPP/pelita/pull/708?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=ASPP) | Coverage Δ | |
|---|---|---|
| [pelita/ui/tk\_canvas.py](https://codecov.io/gh/ASPP/pelita/pull/708/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=ASPP#diff-cGVsaXRhL3VpL3RrX2NhbnZhcy5weQ==) | `0.00% <0.00%> (ø)` | |
| [pelita/utils.py](https://codecov.io/gh/ASPP/pelita/pull/708/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=ASPP#diff-cGVsaXRhL3V0aWxzLnB5) | `62.36% <ø> (ø)` | |
| [pelita/layout.py](https://codecov.io/gh/ASPP/pelita/pull/708/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=ASPP#diff-cGVsaXRhL2xheW91dC5weQ==) | `94.11% <80.00%> (-0.48%)` | :arrow_down: |
| [pelita/player/team.py](https://codecov.io/gh/ASPP/pelita/pull/708/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=ASPP#diff-cGVsaXRhL3BsYXllci90ZWFtLnB5) | `84.24% <87.50%> (-0.09%)` | :arrow_down: |
| [pelita/game.py](https://codecov.io/gh/ASPP/pelita/pull/708/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=ASPP#diff-cGVsaXRhL2dhbWUucHk=) | `86.59% <100.00%> (ø)` | |
| [pelita/gamestate\_filters.py](https://codecov.io/gh/ASPP/pelita/pull/708/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=ASPP#diff-cGVsaXRhL2dhbWVzdGF0ZV9maWx0ZXJzLnB5) | `94.87% <100.00%> (-0.26%)` | :arrow_down: |
| [pelita/scripts/pelita\_player.py](https://codecov.io/gh/ASPP/pelita/pull/708/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=ASPP#diff-cGVsaXRhL3NjcmlwdHMvcGVsaXRhX3BsYXllci5weQ==) | `84.97% <0.00%> (-4.75%)` | :arrow_down: |
| [pelita/tournament/\_\_init\_\_.py](https://codecov.io/gh/ASPP/pelita/pull/708/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=ASPP#diff-cGVsaXRhL3RvdXJuYW1lbnQvX19pbml0X18ucHk=) | `70.63% <0.00%> (-1.08%)` | :arrow_down: |
| ... and [1 more](https://codecov.io/gh/ASPP/pelita/pull/708/diff?src=pr&el=tree-more&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=ASPP) | |

------

[Continue to review full report at Codecov](https://codecov.io/gh/ASPP/pelita/pull/708?src=pr&el=continue&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=ASPP).
> **Legend** - [Click here to learn more](https://docs.codecov.io/docs/codecov-delta?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=ASPP)
> `Δ = absolute <relative> (impact)`, `ø = not affected`, `? = missing data`
> Powered by [Codecov](https://codecov.io/gh/ASPP/pelita/pull/708?src=pr&el=footer&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=ASPP). Last update [254a9f4...a4e248c](https://codecov.io/gh/ASPP/pelita/pull/708?src=pr&el=lastupdated&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=ASPP). Read the [comment docs](https://docs.codecov.io/docs/pull-request-comments?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=ASPP).

Debilski: Here’s an in-progress update on the speed:

First with the background_games demo.

```
./pelita_template (master)
❯ time python demo08_background_games.py
Games played: 100
Attacker wins: 17
Defender wins: 79
Draws: 4
Average score difference: -14.71

________________________________________________________
Executed in   92.99 secs    fish           external
   usr time   90.31 secs  203.00 micros   90.31 secs
   sys time    0.64 secs  898.00 micros    0.63 secs
```

```
./pelita_template (this PR)
❯ time python demo08_background_games.py
Games played: 100
Attacker wins: 18
Defender wins: 77
Draws: 5
Average score difference: -18.29

________________________________________________________
Executed in   20.08 secs    fish           external
   usr time   19.55 secs  276.00 micros   19.55 secs
   sys time    0.32 secs  959.00 micros    0.32 secs
```


Now with the benchmark that I created for this PR:

```
❯ python demo/benchmark_game.py --number 5 --max-rounds 300
Running 5 times with max 300 rounds. Fastest out of 5:
Stopping            : 0.6716697419999997
NQ_Random           : 0.9012290820000004
Stopping (remote)   : 4.812962928999998
NQ_Random (remote)  : 5.1260686190000015
```

```
❯ python demo/benchmark_game.py --number 5 --max-rounds 300
Running 5 times with max 300 rounds. Fastest out of 5:
Stopping            : 4.707969789
NQ_Random           : 6.251112241999998
Stopping (remote)   : 10.743467068000001
NQ_Random (remote)  : 11.85318602800001
```

As we can see, the new PR can make the code between 2 times and up to 8 times faster in the best case in a local game. Of course, the optimisations are only relevant for code that accesses the shape (this won’t happen too often to be a relevant factor) and checks `bot.walls`. As many good bots will at some point switch over to using some sort of a graph, they also shouldn’t need to access `bot.walls` more than once (and `bot.legal_positions` wouldn’t be needed either), but our own code already profits a lot from the changes.


My suggestion would be to merge this in the coming days (I still want to have another look at the code and docs) with the current changes:

  * added a `shape` to `game_state` and `bot` to avoid having to use the costly and error-prone `max(walls)[0]+1`
  * made `walls` a `Set[Tuple[int]]`
  * made `homezone` a `Set[Tuple[int]]` (we can still make this a special object with `__contains__` syntax later)

Notably, `walls` and `homezone` are no `frozenset`s yet. Also, given the problems with `random.choice`, `food` is still a `List[Tuple[int]]`. I haven’t checked it, but the access pattern for food might not profit from it being a set *that* much. (Arguably, the *usual* access pattern for food also doesn’t include `random.choice`, but I think it’s still useful for experimenting.)


I have rewritten Pietro’s bots to use networkx while using this branch and haven’t really run into problems (one usual change was the need to do `homezone[:]` → `homezone.copy()` but that’s a minor thing). I’d say it is safe to use.


Patch:
diff --git a/check_layout_consistency.py b/check_layout_consistency.py
index f3e873c6..cb6b9689 100644
--- a/check_layout_consistency.py
+++ b/check_layout_consistency.py
@@ -1,36 +1,11 @@
 """Detect if a layout contains "chambers" with food"""
 import sys
 
-import networkx
+import networkx as nx
 from pelita.layout import parse_layout
+from pelita.utils import walls_to_graph
 
 
-def get_hw(layout):
-    walls = layout['walls']
-    width = max([coord[0] for coord in walls]) + 1
-    height = max([coord[1] for coord in walls]) + 1
-    return height, width
-
-def layout_to_graph(layout):
-    """Return a networkx.Graph object given the layout
-    """
-    graph = networkx.Graph()
-    height, width = get_hw(layout)
-    walls = layout['walls']
-    for x in range(width):
-        for y in range(height):
-            if (x, y) not in walls:
-                # this is a free position, get its neighbors
-                for delta_x, delta_y in ((1,0), (-1,0), (0,1), (0,-1)):
-                    neighbor = (x + delta_x, y + delta_y)
-                    # we don't need to check for getting neighbors out of the maze
-                    # because our mazes are all surrounded by walls, i.e. our
-                    # deltas will not put us out of the maze
-                    if neighbor not in walls:
-                        # this is a genuine neighbor, add an edge in the graph
-                        graph.add_edge((x, y), neighbor)
-    return graph
-
 if __name__ == '__main__':
 
     # either read a file or read from stdin
@@ -44,8 +19,8 @@ if __name__ == '__main__':
 
     # first of all, check for symmetry
     # if something is found on the left, it should be found center-mirrored on the right
-    height, width = get_hw(layout)
-    known = layout['walls']+layout['food']
+    width, height = layout['shape']
+    known = layout['walls'] | set(layout['food'])
     layout['empty'] = [(x,y) for x in range(width) for y in range(height) if (x,y) not in known]
     for x in range(width // 2):
         for y in range(height):
@@ -56,14 +31,14 @@ if __name__ == '__main__':
                         print(f'{flname}: Layout is not symmetric {coord} != {cmirror}')
 
 
-    graph = layout_to_graph(layout)
+    graph = walls_to_graph(layout['walls'])
 
     # check for dead_ends
     for node, degree in graph.degree():
         if degree < 2:
             print(f'{flname}: found dead end in {node}')
 
-    if networkx.node_connectivity(graph) < 2:
-        entrance = networkx.minimum_node_cut(graph).pop()
+    if nx.node_connectivity(graph) < 2:
+        entrance = nx.minimum_node_cut(graph).pop()
         print(f'{flname}: Detected chamber, entrance: {entrance}')
 
diff --git a/demo/benchmark_game.py b/demo/benchmark_game.py
index 1f5df3c6..cdc6dedc 100644
--- a/demo/benchmark_game.py
+++ b/demo/benchmark_game.py
@@ -1,8 +1,14 @@
 #!/usr/bin/env python3
 
+import argparse
+import cProfile
+import functools
+import subprocess
+import timeit
+
 from pelita.layout import parse_layout
 from pelita.game import run_game
-from pelita.player import stopping_player
+from pelita.player import stopping_player, nq_random_player
 
 LAYOUT="""
 ##################################
@@ -27,15 +33,41 @@ LAYOUT="""
 
 layout = parse_layout(LAYOUT)
 
-def run():
-    return run_game([stopping_player, stopping_player], max_rounds=10, layout_dict=layout)
+def run(teams, max_rounds):
+    return run_game(teams, max_rounds=max_rounds, layout_dict=layout, print_result=False, allow_exceptions=True, store_output=subprocess.DEVNULL)
+
+def parse_args():
+    parser = argparse.ArgumentParser(description='Benchmark pelita run_game')
+    parser.add_argument('--repeat', help="Number of repeats of timeit.", default=5, type=int)
+    parser.add_argument('--number', help="Number of iterations inside timeit.", default=10, type=int)
+    parser.add_argument('--max-rounds', help="Max rounds.", default=300, type=int)
+
+    parser.add_argument('--cprofile', help="Show cProfile output with test teams (int).", default=None, type=int)
+
+    return parser.parse_args()
 
 if __name__ == '__main__':
-    import timeit
-    REPEAT = 5
-    NUMBER = 10
-    result = min(timeit.repeat(run, repeat=REPEAT, number=NUMBER))
-    print("Fastest out of {}: {}".format(REPEAT, result))
-
-    import cProfile
-    cProfile.runctx("""run()""", globals(), locals())
+    args = parse_args()
+    REPEAT = args.repeat
+    NUMBER = args.number
+    MAX_ROUNDS = args.max_rounds
+
+    tests = [
+        ("Stopping", [stopping_player, stopping_player]),
+        ("NQ_Random", [nq_random_player, nq_random_player]),
+        ("Stopping (remote)", ["pelita/player/StoppingPlayer.py", "pelita/player/StoppingPlayer.py"]),
+        ("NQ_Random (remote)", ["pelita/player/RandomPlayers.py", "pelita/player/RandomPlayers.py"]),
+    ]
+
+    if args.cprofile is None:
+        print(f"Running {NUMBER} times with max {MAX_ROUNDS} rounds. Fastest out of {REPEAT}:")
+
+        for name, teams in tests:
+            result = min(timeit.repeat(functools.partial(run, teams=teams, max_rounds=MAX_ROUNDS), repeat=REPEAT, number=NUMBER))
+            print(f"{name:<20}: {result}")
+
+    else:
+        name, teams = tests[args.cprofile]
+        print(f"Running cProfile for teams {name} with max {MAX_ROUNDS} rounds:")
+        max_rounds = MAX_ROUNDS
+        cProfile.runctx("""run(teams, max_rounds)""", globals(), locals())
diff --git a/pelita/game.py b/pelita/game.py
index 04cc7e58..3c1c816b 100644
--- a/pelita/game.py
+++ b/pelita/game.py
@@ -268,6 +268,8 @@ def setup_game(team_specs, *, layout_dict, max_rounds=300, layout_name="", seed=
         raise ValueError("Number of bots in layout must be 4.")
 
     width, height = layout.wall_dimensions(layout_dict['walls'])
+    if not (width, height) == layout_dict['shape']:
+        raise ValueError(f"layout_dict['walls'] does not match layout_dict['shape'].")
 
     for idx, pos in enumerate(layout_dict['bots']):
         if pos in layout_dict['walls']:
@@ -300,8 +302,11 @@ def setup_game(team_specs, *, layout_dict, max_rounds=300, layout_name="", seed=
 
     game_state = dict(
         ### The layout attributes
-        #: Walls. List of (int, int)
-        walls=layout_dict['walls'][:],
+        #: Walls. Set of (int, int)
+        walls=set(layout_dict['walls']),
+
+        #: Shape of the maze. (int, int)
+        shape=layout_dict['shape'],
 
         #: Food per team. List of sets of (int, int)
         food=food,
@@ -507,6 +512,7 @@ def prepare_bot_state(game_state, idx=None):
     enemy_team = 1 - own_team
     enemy_positions = game_state['bots'][enemy_team::2]
     noised_positions = noiser(walls=game_state['walls'],
+                              shape=game_state['shape'],
                               bot_position=bot_position,
                               enemy_positions=enemy_positions,
                               noise_radius=game_state['noise_radius'],
@@ -560,6 +566,7 @@ def prepare_bot_state(game_state, idx=None):
     if bot_initialization:
         bot_state.update({
             'walls': game_state['walls'], # only in initial round
+            'shape': game_state['shape'], # only in initial round
             'seed': seed # only used in set_initial phase
         })
 
@@ -739,6 +746,7 @@ def apply_move(gamestate, bot_position):
     score = gamestate["score"]
     food = gamestate["food"]
     walls = gamestate["walls"]
+    shape = gamestate["shape"]
     food = gamestate["food"]
     n_round = gamestate["round"]
     kills = gamestate["kills"]
@@ -756,7 +764,7 @@ def apply_move(gamestate, bot_position):
     team_errors = gamestate["errors"][team]
 
     # the allowed moves for the current bot
-    legal_positions = get_legal_positions(walls, gamestate["bots"][gamestate["turn"]])
+    legal_positions = get_legal_positions(walls, shape, gamestate["bots"][gamestate["turn"]])
 
     # unless we have already made an error, check if we made a legal move
     if not (n_round, turn) in team_errors:
@@ -787,12 +795,11 @@ def apply_move(gamestate, bot_position):
     _logger.info(f"Bot {turn} moves to {bot_position}.")
     # then apply rules
     # is bot in home or enemy territory
-    x_walls = [i[0] for i in walls]
-    boundary = max(x_walls) / 2  # float
+    boundary = gamestate['shape'][0] / 2
     if team == 0:
         bot_in_homezone = bot_position[0] < boundary
     elif team == 1:
-        bot_in_homezone = bot_position[0] > boundary
+        bot_in_homezone = bot_position[0] >= boundary
     # update food list
     if not bot_in_homezone:
         if bot_position in food[1 - team]:
@@ -806,7 +813,7 @@ def apply_move(gamestate, bot_position):
         for enemy_idx in killed_enemies:
             _logger.info(f"Bot {turn} eats enemy bot {enemy_idx} at {bot_position}.")
             score[team] = score[team] + KILL_POINTS
-            init_positions = initial_positions(walls)
+            init_positions = initial_positions(walls, shape)
             bots[enemy_idx] = init_positions[enemy_idx]
             kills[turn] += 1
             deaths[enemy_idx] += 1
@@ -818,7 +825,7 @@ def apply_move(gamestate, bot_position):
         if len(enemies_on_target) > 0:
             _logger.info(f"Bot {turn} was eaten by bots {enemies_on_target} at {bot_position}.")
             score[1 - team] = score[1 - team] + KILL_POINTS
-            init_positions = initial_positions(walls)
+            init_positions = initial_positions(walls, shape)
             bots[turn] = init_positions[turn]
             deaths[turn] += 1
             kills[enemies_on_target[0]] += 1
diff --git a/pelita/gamestate_filters.py b/pelita/gamestate_filters.py
index 84c7eb7c..e43de6ce 100644
--- a/pelita/gamestate_filters.py
+++ b/pelita/gamestate_filters.py
@@ -5,7 +5,7 @@ import copy
 ### The main function
 
 
-def noiser(walls, bot_position, enemy_positions, noise_radius=5, sight_distance=5, rnd=None):
+def noiser(walls, shape, bot_position, enemy_positions, noise_radius=5, sight_distance=5, rnd=None):
     """Function to make bot positions noisy in a game state.
 
     Applies uniform noise in maze space. Noise will only be applied if the
@@ -36,7 +36,7 @@ def noiser(walls, bot_position, enemy_positions, noise_radius=5, sight_distance=
 
     Parameters
     ----------
-    walls : list of (int, int)
+    walls : set of (int, int)
     noise_radius : int, optional, default: 5
         the radius for the uniform noise
     sight_distance : int, optional, default: 5
@@ -67,7 +67,7 @@ def noiser(walls, bot_position, enemy_positions, noise_radius=5, sight_distance=
 
         if cur_distance is None or cur_distance > sight_distance:
             # If so then alter the position of the enemy
-            new_pos, noisy_flag = alter_pos(b, noise_radius, rnd, walls)
+            new_pos, noisy_flag = alter_pos(b, noise_radius, rnd, walls, shape)
             noised_positions[count] = new_pos
             is_noisy[count] = noisy_flag
         else:
@@ -80,26 +80,22 @@ def noiser(walls, bot_position, enemy_positions, noise_radius=5, sight_distance=
 ### The subfunctions
 
 
-def alter_pos(bot_pos, noise_radius, rnd, walls):
+def alter_pos(bot_pos, noise_radius, rnd, walls, shape):
     """ alter the position """
 
-    # extracting from walls the maximum width and height
-    max_walls = max(walls)
-    min_walls = min(walls)
-
     # get a list of possible positions
     x_min, x_max = bot_pos[0] - noise_radius, bot_pos[0] + noise_radius
     y_min, y_max = bot_pos[1] - noise_radius, bot_pos[1] + noise_radius
 
-    # filter them so the we return no positions outsided the maze
+    # filter them so that we return no positions outside the maze
     if x_min < 0:
         x_min = 1
-    if x_max > max_walls[0]:
-        x_max = max_walls[0]
+    if x_max >= shape[0]:
+        x_max = shape[0] - 1
     if y_min < 0:
         y_min = 1
-    if y_max > max_walls[1]:
-        y_max = max_walls[1]
+    if y_max >= shape[1]:
+        y_max = shape[1] - 1
 
     possible_positions = [
         (i, j)
diff --git a/pelita/layout.py b/pelita/layout.py
index a45a6f3e..3039bbc2 100644
--- a/pelita/layout.py
+++ b/pelita/layout.py
@@ -111,16 +111,18 @@ def parse_layout(layout_str, food=None, bots=None):
 
 
     Return a dict
-        {'walls': list_of_wall_coordinates,
+        {'walls': set_of_wall_coordinates,
          'food' : list_of_food_coordinates,
-         'bots'  : list_of_bot_coordinates in the order (a,x,b,y) }
+         'bots'  : list_of_bot_coordinates in the order (a,x,b,y),
+         'shape': tuple of (height, width) of the layout}
 
     In the example above:
-    {'walls': [(0, 0), (0, 1), (0, 2), (0, 3), (0, 4), (1, 0), (1, 4), (2, 0),
+    {'walls': {(0, 0), (0, 1), (0, 2), (0, 3), (0, 4), (1, 0), (1, 4), (2, 0),
                (2, 4), (3, 0), (3, 2), (3, 4), (4, 0), (4, 2), (4, 4), (5, 0),
-               (5, 4), (6, 0), (6, 4), (7, 0), (7, 1), (7, 2), (7, 3), (7, 4)],
+               (5, 4), (6, 0), (6, 4), (7, 0), (7, 1), (7, 2), (7, 3), (7, 4)},
      'food': [(3, 3), (4, 1)],
-     'bots': [(1, 1), (6, 2), (1, 2), (6, 3)]}
+     'bots': [(1, 1), (6, 2), (1, 2), (6, 3)],
+     'shape': (8, 4)}
 
     Additional food and bots can be passed:
 
@@ -135,7 +137,7 @@ def parse_layout(layout_str, food=None, bots=None):
         food = []
 
     # set empty default values
-    lwalls = []
+    lwalls = set()
     lfood = []
     lbots = [None] * 4
 
@@ -190,7 +192,7 @@ def parse_layout(layout_str, food=None, bots=None):
             # assign the char to the corresponding list
             if char == '#':
                 # wall
-                lwalls.append(coord)
+                lwalls.add(coord)
             elif char == '.':
                 # food
                 lfood.append(coord)
@@ -212,7 +214,6 @@ def parse_layout(layout_str, food=None, bots=None):
             missing_bots.append(BOT_I2N[i])
     if missing_bots:
             raise ValueError(f"Missing bot(s): {missing_bots}")
-    lwalls.sort()
     lfood.sort()
 
     # if additional food was supplied, we add it
@@ -239,25 +240,27 @@ def parse_layout(layout_str, food=None, bots=None):
 
     # build parsed layout, ensuring walls and food are sorted
     parsed_layout = {
-        'walls': sorted(lwalls),
+        'walls': lwalls,
         'food': sorted(lfood),
-        'bots': lbots
+        'bots': lbots,
+        'shape': (width, height)
     }
 
     return parsed_layout
 
 
-def layout_as_str(*, walls, food=None, bots=None):
+def layout_as_str(*, walls, food=None, bots=None, shape=None):
     """Given a dictionary with walls, food and bots coordinates return a string layout representation
 
     Example:
 
     Given:
-    {'walls': [(0, 0), (0, 1), (0, 2), (0, 3), (0, 4), (1, 0), (1, 4), (2, 0),
+    {'walls': {(0, 0), (0, 1), (0, 2), (0, 3), (0, 4), (1, 0), (1, 4), (2, 0),
                (2, 4), (3, 0), (3, 2), (3, 4), (4, 0), (4, 2), (4, 4), (5, 0),
-               (5, 4), (6, 0), (6, 4), (7, 0), (7, 1), (7, 2), (7, 3), (7, 4)],
+               (5, 4), (6, 0), (6, 4), (7, 0), (7, 1), (7, 2), (7, 3), (7, 4)},
      'food': [(3, 3), (4, 1)],
-     'bots': [(1, 1), (6, 2), (1, 2), (6, 3)]}
+     'bots': [(1, 1), (6, 2), (1, 2), (6, 3)],
+     'shape': (8, 4)}
 
     Return:
     ########
@@ -268,10 +271,14 @@ def layout_as_str(*, walls, food=None, bots=None):
 
     Overlapping items are discarded. When overlapping, walls take precedence over
     bots, which take precedence over food.
+
+    The shape is optional. When it does not match the borders of the maze, a ValueError
+    is raised.
     """
-    walls = sorted(walls)
-    width = max(walls)[0] + 1
-    height = max(walls)[1] + 1
+    width, height = wall_dimensions(walls)
+
+    if shape is not None and not (width, height) == shape:
+        raise ValueError(f"Given shape {shape} does not match width and height of layout {(width, height)}.")
 
     # initialized empty containers
     if food is None:
@@ -299,13 +306,14 @@ def layout_as_str(*, walls, food=None, bots=None):
 
 
 def wall_dimensions(walls):
-    """ Given a list of walls, returns a tuple of (width, height)."""
-    width = max(walls)[0] + 1
-    height = max(walls)[1] + 1
+    """ Given a list of walls, returns the shape of the maze as a tuple of (width, height)"""
+    max_elem = max(walls)
+    width = max_elem[0] + 1
+    height = max_elem[1] + 1
     return (width, height)
 
 
-def initial_positions(walls):
+def initial_positions(walls, shape):
     """Calculate initial positions.
 
     Given the list of walls, returns the free positions that are closest to the
@@ -314,8 +322,7 @@ def initial_positions(walls):
     for judging what is closest. On equal distances, a smaller distance in the
     x value is preferred.
     """
-    width = max(walls)[0] + 1
-    height = max(walls)[1] + 1
+    width, height = shape
 
     left_start = (1, height - 2)
     left = []
@@ -370,13 +377,13 @@ def initial_positions(walls):
     return [left[0], right[0], left[1], right[1]]
 
 
-def get_legal_positions(walls, bot_position):
+def get_legal_positions(walls, shape, bot_position):
     """ Returns all legal positions that a bot at `bot_position`
     can go to.
 
      Parameters
     ----------
-    walls : list
+    walls : set of (int, int)
         position of the walls of current layout.
     bot_position: tuple
         position of current bot.
@@ -391,7 +398,7 @@ def get_legal_positions(walls, bot_position):
     ValueError
         if bot_position invalid or on wall
     """
-    width, height = wall_dimensions(walls)
+    width, height = shape
     if not (0, 0) <= bot_position < (width, height):
         raise ValueError(f"Position {bot_position} not inside maze ({width}x{height}).")
     if bot_position in walls:
diff --git a/pelita/network.py b/pelita/network.py
index 7cd5f29c..0a444ef4 100644
--- a/pelita/network.py
+++ b/pelita/network.py
@@ -96,6 +96,14 @@ def bind_socket(socket, address, option_hint=None):
                 (option_hint,), file=sys.stderr)
         raise
 
+
+class SetEncoder(json.JSONEncoder):
+   def default(self, obj):
+      if isinstance(obj, set):
+         return list(obj)
+      return json.JSONEncoder.default(self, obj)
+
+
 def json_default_handler(o):
     """ Pythons built-in json handler has problems converting numpy.in64
     to json. By adding this method as a default= to json.dumps, we can
@@ -164,7 +172,7 @@ class ZMQConnection:
             # race condition if a connection was closed between poll and send.
             # NOBLOCK should raise, so we can catch that
             message_obj = {"__uuid__": msg_id, "__action__": action, "__data__": data}
-            json_message = json.dumps(message_obj)
+            json_message = json.dumps(message_obj, cls=SetEncoder)
             try:
                 self.socket.send_unicode(json_message, flags=zmq.NOBLOCK)
             except zmq.ZMQError as e:
@@ -275,7 +283,6 @@ class ZMQConnection:
     def __repr__(self):
         return "ZMQConnection(%r)" % self.socket
 
-
 class ZMQPublisher:
     """ Sets up a simple Publisher which sends all viewed events
     over a zmq connection.
@@ -298,7 +305,7 @@ class ZMQPublisher:
             info['gameover'] = True
         _logger.debug(f"--#> [{action}] %r", info)
         message = {"__action__": action, "__data__": data}
-        as_json = json.dumps(message)
+        as_json = json.dumps(message, cls=SetEncoder)
         self.socket.send_unicode(as_json)
 
     def show_state(self, game_state):
diff --git a/pelita/player/team.py b/pelita/player/team.py
index dc693bf7..e2ded2fc 100644
--- a/pelita/player/team.py
+++ b/pelita/player/team.py
@@ -6,7 +6,6 @@ import random
 import subprocess
 import sys
 import traceback
-from functools import reduce
 from io import StringIO
 from pathlib import Path
 
@@ -14,12 +13,31 @@ import zmq
 
 from .. import layout
 from ..exceptions import PlayerDisconnected, PlayerTimeout
-from ..layout import layout_as_str, parse_layout, wall_dimensions, BOT_I2N
+from ..layout import layout_as_str, BOT_I2N
 from ..network import ZMQClientError, ZMQConnection, ZMQReplyTimeout, ZMQUnreachablePeer
 
 _logger = logging.getLogger(__name__)
 
 
+def _ensure_list_tuples(list):
+    """ Ensures that an iterable is a list of position tuples. """
+    return [tuple(item) for item in list]
+
+def _ensure_set_tuples(set):
+    """ Ensures that an iterable is a set of position tuples. """
+    return {tuple(item) for item in set}
+
+
+def create_homezones(shape):
+    width, height = shape
+    return [
+        {(x, y) for x in range(0, width // 2)
+                for y in range(0, height)},
+        {(x, y) for x in range(width // 2, width)
+                for y in range(0, height)}
+    ]
+
+
 class Team:
     """
     Wraps a move function and forwards it the `set_initial`
@@ -78,7 +96,16 @@ class Team:
         self._bot_track = [[], []]
 
         # Store the walls, which are only transmitted once
-        self._walls = game_state['walls']
+        self._walls = _ensure_set_tuples(game_state['walls'])
+
+        # Store the shape, which is only transmitted once
+        self._shape = tuple(game_state['shape'])
+
+        # Cache the initial positions so that we don’t have to calculate them at each step
+        self._initial_positions = layout.initial_positions(self._walls, self._shape)
+
+        # Cache the homezone so that we don’t have to create it at each step
+        self._homezone = create_homezones(self._shape)
 
         return self.team_name
 
@@ -98,6 +125,9 @@ class Team:
         move : dict
         """
         me = make_bots(walls=self._walls,
+                       shape=self._shape,
+                       initial_positions=self._initial_positions,
+                       homezone=self._homezone,
                        team=game_state['team'],
                        enemy=game_state['enemy'],
                        round=game_state['round'],
@@ -107,7 +137,7 @@ class Team:
         team = me._team
 
         for idx, mybot in enumerate(team):
-            # If a bot has been killed, we reset it’s bot track
+            # If a bot has been killed, we reset its bot track
             if mybot.was_killed:
                 self._bot_track[idx] = []
 
@@ -117,7 +147,7 @@ class Team:
 
         for idx, mybot in enumerate(team):
             # If the track of any bot is empty,
-            # Add its current position
+            # add its current position
             if me._bot_turn != idx:
                 self._bot_track[idx].append(mybot.position)
 
@@ -397,26 +427,13 @@ def make_team(team_spec, team_name=None, zmq_context=None, idx=None, store_outpu
     return team_player, zmq_context
 
 
-def create_homezones(walls):
-    width = max(walls)[0]+1
-    height = max(walls)[1]+1
-    return [
-        [(x, y) for x in range(0, width // 2)
-                for y in range(0, height)],
-        [(x, y) for x in range(width // 2, width)
-                for y in range(0, height)]
-    ]
-
-def _ensure_tuples(list):
-    """ Ensures that an iterable is a list of position tuples. """
-    return [tuple(item) for item in list]
-
 class Bot:
     def __init__(self, *, bot_index,
                           is_on_team,
                           position,
                           initial_position,
                           walls,
+                          shape,
                           homezone,
                           food,
                           score,
@@ -443,10 +460,11 @@ class Bot:
         self.random = random
         self.position = tuple(position)
         self._initial_position = tuple(initial_position)
-        self.walls = _ensure_tuples(walls)
+        self.walls = walls
 
-        self.homezone = _ensure_tuples(homezone)
-        self.food = _ensure_tuples(food)
+        self.homezone = homezone
+        self.food = food
+        self.shape = shape
         self.score  = score
         self.kills = kills
         self.deaths = deaths
@@ -554,8 +572,7 @@ class Bot:
     def _repr_html_(self):
         """ Jupyter-friendly representation. """
         bot = self
-        width = max(bot.walls)[0] + 1
-        height = max(bot.walls)[1] + 1
+        width, height = bot.shape
 
         with StringIO() as out:
             out.write("<table>")
@@ -589,8 +606,6 @@ class Bot:
 
     def __str__(self):
         bot = self
-        width = max(bot.walls)[0] + 1
-        height = max(bot.walls)[1] + 1
 
         if bot.is_blue:
             blue = bot if not bot.turn else bot.other
@@ -628,9 +643,10 @@ class Bot:
         with StringIO() as out:
             out.write(header)
 
-            layout = layout_as_str(walls=bot.walls[:],
+            layout = layout_as_str(walls=bot.walls.copy(),
                                    food=bot.food + bot.enemy[0].food,
-                                   bots=bot_positions)
+                                   bots=bot_positions,
+                                   shape=bot.shape)
 
             out.write(str(layout))
             out.write(footer)
@@ -638,14 +654,12 @@ class Bot:
 
 
 # def __init__(self, *, bot_index, position, initial_position, walls, homezone, food, is_noisy, score, random, round, is_blue):
-def make_bots(*, walls, team, enemy, round, bot_turn, rng):
+def make_bots(*, walls, shape, initial_positions, homezone, team, enemy, round, bot_turn, rng):
     bots = {}
 
     team_index = team['team_index']
     enemy_index = enemy['team_index']
 
-    homezone = create_homezones(walls)
-    initial_positions = layout.initial_positions(walls)
     team_initial_positions = initial_positions[team_index::2]
     enemy_initial_positions = initial_positions[enemy_index::2]
 
@@ -659,8 +673,9 @@ def make_bots(*, walls, team, enemy, round, bot_turn, rng):
             was_killed=team['bot_was_killed'][idx],
             is_noisy=False,
             error_count=team['error_count'],
-            food=team['food'],
+            food=_ensure_list_tuples(team['food']),
             walls=walls,
+            shape=shape,
             round=round,
             bot_turn=bot_turn,
             bot_char=BOT_I2N[team_index + idx*2],
@@ -683,8 +698,9 @@ def make_bots(*, walls, team, enemy, round, bot_turn, rng):
             was_killed=enemy['bot_was_killed'][idx],
             is_noisy=enemy['is_noisy'][idx],
             error_count=enemy['error_count'],
-            food=enemy['food'],
+            food=_ensure_list_tuples(enemy['food']),
             walls=walls,
+            shape=shape,
             round=round,
             bot_char = BOT_I2N[team_index + idx*2],
             random=rng,
@@ -700,5 +716,3 @@ def make_bots(*, walls, team, enemy, round, bot_turn, rng):
     bots['enemy'] = enemy_bots
     return team_bots[bot_turn]
 
-
-
diff --git a/pelita/ui/tk_canvas.py b/pelita/ui/tk_canvas.py
index 671ac456..025f7e5d 100644
--- a/pelita/ui/tk_canvas.py
+++ b/pelita/ui/tk_canvas.py
@@ -8,6 +8,7 @@ import tkinter
 import tkinter.font
 
 from ..game import next_round_turn
+from ..player.team import _ensure_list_tuples
 from .tk_sprites import BotSprite, Food, Wall, col
 from .tk_utils import wm_delete_window_handler
 from .tk_sprites import BotSprite, Food, Wall, RED, BLUE, YELLOW, GREY, BROWN
@@ -15,10 +16,6 @@ from .. import layout
 
 _logger = logging.getLogger(__name__)
 
-def _ensure_tuples(list):
-    """ Ensures that an iterable is a list of position tuples. """
-    return [tuple(item) for item in list]
-
 
 def guess_size(display_string, bounding_width, bounding_height, rel_size=0):
     no_lines = display_string.count("\n") + 1
@@ -341,8 +338,7 @@ class TkApplication:
 
 
     def init_mesh(self, game_state):
-        width = max(game_state['walls'])[0] + 1
-        height = max(game_state['walls'])[1] + 1
+        width, height = game_state['shape']
 
         if self.geometry is None:
             screensize = (
@@ -425,8 +421,8 @@ class TkApplication:
         self.size_changed = False
 
     def draw_universe(self, game_state):
-        self.mesh_graph.num_x = max(game_state['walls'])[0] + 1
-        self.mesh_graph.num_y = max(game_state['walls'])[1] + 1
+        self.mesh_graph.num_x = game_state['shape'][0]
+        self.mesh_graph.num_y = game_state['shape'][1]
 
         self.draw_grid()
         self.draw_selected(game_state)
@@ -578,7 +574,7 @@ class TkApplication:
                 has_food = pos in game_state['food']
                 is_wall = pos in game_state['walls']
                 bots = [idx for idx, bot in enumerate(game_state['bots']) if bot==pos]
-                if pos[0] < (max(game_state['walls'])[0] + 1) // 2:
+                if pos[0] <= (game_state['shape'][0] // 2):
                     zone = "blue"
                 else:
                     zone = "red"
@@ -796,9 +792,10 @@ class TkApplication:
             skip_request = False
             self._observed_steps.add(step)
         # ensure walls, foods and bots positions are list of tuples
-        game_state['walls'] = _ensure_tuples(game_state['walls'])
-        game_state['food'] = _ensure_tuples(game_state['food'])
-        game_state['bots'] = _ensure_tuples(game_state['bots'])
+        game_state['walls'] = _ensure_list_tuples(game_state['walls'])
+        game_state['food'] = _ensure_list_tuples(game_state['food'])
+        game_state['bots'] = _ensure_list_tuples(game_state['bots'])
+        game_state['shape'] = tuple(game_state['shape'])
         self.update(game_state)
         if self._stop_after is not None:
             if self._stop_after == 0:
diff --git a/pelita/utils.py b/pelita/utils.py
index d92dfad5..b56f3c72 100644
--- a/pelita/utils.py
+++ b/pelita/utils.py
@@ -1,11 +1,11 @@
 import random
 
-import networkx
+import networkx as nx
 
 
-from .player.team import make_bots
+from .player.team import make_bots, create_homezones
 from .layout import (get_random_layout, get_layout_by_name, get_available_layouts,
-                     parse_layout, BOT_N2I)
+                     parse_layout, BOT_N2I, initial_positions, wall_dimensions)
 
 RNG = random.Random()
 
@@ -14,8 +14,8 @@ def walls_to_graph(walls):
 
     Parameters
     ----------
-    walls : list[(x0,y0), (x1,y1), ...]
-         a list of wall coordinates
+    walls : set[(x0,y0), (x1,y1), ...]
+         a set of wall coordinates
 
     Returns
     -------
@@ -32,10 +32,9 @@ def walls_to_graph(walls):
     adjacent squares. Adjacent means that you can go from one square to one of
     its adjacent squares by making ore single step (up, down, left, or right).
     """
-    graph = networkx.Graph()
-    extreme = max(walls)
-    width =  extreme[0] + 1
-    height = extreme[1] + 1
+    graph = nx.Graph()
+    width, height = wall_dimensions(walls)
+
     for x in range(width):
         for y in range(height):
             if (x, y) not in walls:
@@ -110,7 +109,7 @@ def run_background_game(*, blue_move, red_move, layout=None, max_rounds=300, see
     game_state : dict
               the final game state as a dictionary. Dictionary keys are:
               - 'seed' : the seed used to initialize the random number generator
-              - 'walls' : list of walls coordinates for the layout
+              - 'walls' : set of wall coordinates for the layout
               - 'layout' : the name of the used layout
               - 'round' : the round at which the game was over
               - 'draw' : True if the game ended in a draw
@@ -246,7 +245,7 @@ def setup_test_game(*, layout, is_blue=True, round=None, score=None, seed=None,
 
     layout, layout_name = _parse_layout_arg(layout=layout, food=food, bots=bots)
 
-    width = max(layout['walls'])[0] + 1
+    width, height = layout['shape']
 
     def split_food(width, food):
         team_food = [set(), set()]
@@ -296,7 +295,10 @@ def setup_test_game(*, layout, is_blue=True, round=None, score=None, seed=None,
         'name': "red" if is_blue else "blue"
     }
 
-    bot = make_bots(walls=layout['walls'][:],
+    bot = make_bots(walls=layout['walls'].copy(),
+                    shape=layout['shape'],
+                    initial_positions=initial_positions(layout['walls'], layout['shape']),
+                    homezone=create_homezones(layout['shape']),
                     team=team,
                     enemy=enemy,
                     round=round,
diff --git a/pelita/viewer.py b/pelita/viewer.py
index 73ab01b9..c9d6c414 100644
--- a/pelita/viewer.py
+++ b/pelita/viewer.py
@@ -6,6 +6,7 @@ import logging
 import zmq
 
 from . import layout
+from .network import SetEncoder
 
 _logger = logging.getLogger(__name__)
 
@@ -128,7 +129,7 @@ class ReplyToViewer:
     def _send(self, message):
         socks = dict(self.pollout.poll(300))
         if socks.get(self.sock) == zmq.POLLOUT:
-            as_json = json.dumps(message)
+            as_json = json.dumps(message, cls=SetEncoder)
             self.sock.send_unicode(as_json, flags=zmq.NOBLOCK)
 
     def show_state(self, game_state):
@@ -142,7 +143,7 @@ class ReplayWriter:
         self.stream = stream
 
     def _send(self, message):
-        as_json = json.dumps(message)
+        as_json = json.dumps(message, cls=SetEncoder)
         self.stream.write(as_json)
         # We use 0x04 (EOT) as a separator between the events.
         # The additional newline is for improved readability


Test patch:
diff --git a/test/test_filter_gamestates.py b/test/test_filter_gamestates.py
index a12fcd27..2110f957 100644
--- a/test/test_filter_gamestates.py
+++ b/test/test_filter_gamestates.py
@@ -85,10 +85,11 @@ def test_noiser_no_negative_coordinates(bot_id):
     gamestate = make_gamestate()
     old_bots = gamestate["bots"][:]
     walls = gamestate['walls']
+    shape = gamestate['shape']
     bot_position = gamestate['bots'][bot_id]
     enemy_group = 1 - (bot_id // 2)
     enemy_positions = gamestate['bots'][enemy_group::2]
-    noised = gf.noiser(walls, bot_position=bot_position, enemy_positions=enemy_positions,
+    noised = gf.noiser(walls, shape=shape, bot_position=bot_position, enemy_positions=enemy_positions,
                        noise_radius=5, sight_distance=5, rnd=None)
     new_bots = noised["enemy_positions"]
     print(noised)
@@ -291,6 +292,7 @@ def test_noiser_noising_at_noise_radius_extreme(ii):
     team_bots = old_bots[team_id::2]
     enemy_bots = old_bots[1 - team_id::2]
     noised = gf.noiser(walls=gamestate["walls"],
+                       shape=gamestate["shape"],
                        bot_position=gamestate["bots"][gamestate["turn"]],
                        enemy_positions=enemy_bots,
                        noise_radius=50, sight_distance=5, rnd=None)
@@ -326,6 +328,7 @@ def test_uniform_noise_manhattan(noise_radius, expected, test_layout=None):
     position_bucket = collections.defaultdict(int)
     for i in range(200):
         noised = gf.noiser(walls=parsed['walls'],
+                            shape=parsed["shape"],
                             bot_position=parsed['bots'][1],
                             enemy_positions=[parsed['bots'][0]],
                             noise_radius=noise_radius)
@@ -474,6 +477,7 @@ def test_uniform_noise_manhattan_graphical_distance(test_layout, is_noisy):
     NUM_TESTS = 400
     for i in range(NUM_TESTS):
         noised = gf.noiser(walls=parsed['walls'],
+                            shape=parsed['shape'],
                             bot_position=parsed['bots'][1],
                             enemy_positions=[parsed['bots'][0]])
                             # use default values for radius and distance
@@ -511,6 +515,7 @@ def test_uniform_noise_4_bots_manhattan():
 
     for i in range(200):
         noised = gf.noiser(walls=parsed['walls'],
+                           shape=parsed['shape'],
                            bot_position=parsed['bots'][1],
                            enemy_positions=parsed['bots'][0::2])
 
@@ -544,6 +549,7 @@ def test_uniform_noise_4_bots_no_noise_manhattan():
 
     for i in range(200):
         noised = gf.noiser(walls=parsed['walls'],
+                           shape=parsed['shape'],
                            bot_position=parsed['bots'][1],
                            enemy_positions=parsed['bots'][0::2])
 
@@ -575,6 +581,7 @@ def test_noise_manhattan_failure():
     # check a few times
     for i in range(5):
         noised = gf.noiser(walls=parsed['walls'],
+                            shape=parsed['shape'],
                             bot_position=parsed['bots'][1],
                             enemy_positions=parsed['bots'][0::2])
 
diff --git a/test/test_game.py b/test/test_game.py
index 23916ac9..9d3be610 100644
--- a/test/test_game.py
+++ b/test/test_game.py
@@ -34,8 +34,8 @@ def test_initial_positions_basic():
     #x   y #
     ########
     """
-    walls = layout.parse_layout(simple_layout)['walls']
-    out = initial_positions(walls)
+    parsed = layout.parse_layout(simple_layout)
+    out = initial_positions(parsed['walls'], parsed['shape'])
     exp = [(1, 1), (6, 2), (1, 2), (6, 1)]
     assert len(out) == 4
     assert out == exp
@@ -72,7 +72,7 @@ def test_initial_positions_basic():
     ])
 def test_initial_positions(simple_layout):
     parsed = layout.parse_layout(simple_layout)
-    i_pos = initial_positions(parsed['walls'])
+    i_pos = initial_positions(parsed['walls'], parsed['shape'])
     expected = parsed['bots']
     assert len(i_pos) == 4
     assert i_pos == expected
@@ -85,7 +85,8 @@ def test_initial_positions_same_in_layout_random(layout_t):
     parsed_l = layout.parse_layout(layout_string)
     exp = parsed_l["bots"]
     walls = parsed_l["walls"]
-    out = initial_positions(walls)
+    shape = parsed_l["shape"]
+    out = initial_positions(walls, shape)
     assert out == exp
 
 @pytest.mark.parametrize('layout_name', layout.get_available_layouts())
@@ -95,14 +96,15 @@ def test_initial_positions_same_in_layout(layout_name):
     parsed_l = layout.parse_layout(l)
     exp = parsed_l["bots"]
     walls = parsed_l["walls"]
-    out = initial_positions(walls)
+    shape = parsed_l["shape"]
+    out = initial_positions(walls, shape)
     assert out == exp
 
 def test_get_legal_positions_basic():
     """Check that the output of legal moves contains all legal moves for one example layout"""
     l = layout.get_layout_by_name(layout_name="small_100")
     parsed_l = layout.parse_layout(l)
-    legal_positions = get_legal_positions(parsed_l["walls"], parsed_l["bots"][0])
+    legal_positions = get_legal_positions(parsed_l["walls"], parsed_l["shape"], parsed_l["bots"][0])
     exp = [(1, 4), (1, 6), (1, 5)]
     assert legal_positions == exp
 
@@ -113,7 +115,7 @@ def test_get_legal_positions_random(layout_t, bot_idx):
     layout_name, layout_string = layout_t # get_random_layout returns a tuple of name and string
     parsed_l = layout.parse_layout(layout_string)
     bot = parsed_l["bots"][bot_idx]
-    legal_positions = get_legal_positions(parsed_l["walls"], bot)
+    legal_positions = get_legal_positions(parsed_l["walls"], parsed_l["shape"], bot)
     for move in legal_positions:
         assert move not in parsed_l["walls"]
         assert  abs((move[0] - bot[0])+(move[1] - bot[1])) <= 1
@@ -134,7 +136,7 @@ def test_play_turn_apply_error(turn):
     # so that the error dictionaries are sane
     game_state["round"] = 3
 
-    illegal_position = game_state["walls"][0]
+    illegal_position = (0, 0) # should always be a wall
     game_state_new = apply_move(game_state, illegal_position)
     assert game_state_new["gameover"]
     assert len(game_state_new["errors"][team]) == 5
@@ -150,7 +152,7 @@ def test_play_turn_fatal(turn):
     fatal_list = [{}, {}]
     fatal_list[team] = {"error":True}
     game_state["fatal_errors"] = fatal_list
-    move = get_legal_positions(game_state["walls"], game_state["bots"][turn])
+    move = get_legal_positions(game_state["walls"], game_state["shape"], game_state["bots"][turn])
     game_state_new = apply_move(game_state, move[0])
     assert game_state_new["gameover"]
     assert game_state_new["whowins"] == int(not team)
@@ -161,11 +163,11 @@ def test_play_turn_illegal_position(turn):
     game_state = setup_random_basic_gamestate()
     game_state["turn"] = turn
     team = turn % 2
-    illegal_position = game_state["walls"][0]
+    illegal_position = (0, 0) # should always be a wall
     game_state_new = apply_move(game_state, illegal_position)
     assert len(game_state_new["errors"][team]) == 1
     assert game_state_new["errors"][team][(1, turn)].keys() == set(["reason", "bot_position"])
-    assert game_state_new["bots"][turn] in get_legal_positions(game_state["walls"], game_state["bots"][turn])
+    assert game_state_new["bots"][turn] in get_legal_positions(game_state["walls"], game_state["shape"], game_state["bots"][turn])
 
 @pytest.mark.parametrize('turn', (0, 1, 2, 3))
 @pytest.mark.parametrize('which_food', (0, 1))
@@ -729,6 +731,7 @@ def test_play_turn_move():
         "food": parsed_l["food"],
         "walls": parsed_l["walls"],
         "bots": parsed_l["bots"],
+        "shape": parsed_l["shape"],
         "max_rounds": 300,
         "team_names": ("a", "b"),
         "turn": turn,
@@ -746,7 +749,7 @@ def test_play_turn_move():
         "fatal_errors": [{}, {}],
         "rnd": random.Random()
         }
-    legal_positions = get_legal_positions(game_state["walls"], game_state["bots"][turn])
+    legal_positions = get_legal_positions(game_state["walls"], game_state["shape"], game_state["bots"][turn])
     game_state_new = apply_move(game_state, legal_positions[0])
     assert game_state_new["bots"][turn] == legal_positions[0]
 
diff --git a/test/test_layout.py b/test/test_layout.py
index 110fd98a..72363c71 100644
--- a/test/test_layout.py
+++ b/test/test_layout.py
@@ -56,18 +56,19 @@ def test_legal_layout():
              ######
              """
     parsed_layout = parse_layout(layout)
-    ewalls = []
+    ewalls = set()
     for x in range(6):
         for y in range(6):
             if (x == 0 or x == 5) or (y == 0 or y == 5):
-                ewalls.append((x,y))
-    ewalls.extend([(3, 2),(2, 3)])
-    ewalls.sort()
+                ewalls.add((x,y))
+    ewalls.update([(3, 2),(2, 3)])
     efood = sorted([(2, 1), (1, 2), (4, 3), (3, 4)])
     ebots = [(1, 3), (4, 2), (1, 4), (4, 1)]
     assert parsed_layout['walls'] == ewalls
     assert parsed_layout['food'] == efood
     assert parsed_layout['bots'] == ebots
+    assert parsed_layout['shape'] == (6, 6)
+    assert wall_dimensions(parsed_layout['walls']) == parsed_layout['shape']
 
 def test_legal_layout_with_added_items():
     layout = """
@@ -81,18 +82,19 @@ def test_legal_layout_with_added_items():
     added_food = [(1,1), (4,4)]
     added_bots = {'b': (1,4)}
     parsed_layout = parse_layout(layout, food=added_food, bots=added_bots)
-    ewalls = []
+    ewalls = set()
     for x in range(6):
         for y in range(6):
             if (x == 0 or x == 5) or (y == 0 or y == 5):
-                ewalls.append((x,y))
-    ewalls.extend([(3, 2),(2, 3)])
-    ewalls.sort()
+                ewalls.add((x,y))
+    ewalls.update([(3, 2),(2, 3)])
     efood = sorted([(2, 1), (1, 2), (4, 3), (3, 4)]+added_food)
     ebots = [(1, 3), (4, 2), (1, 4), (4, 1)]
     assert parsed_layout['walls'] == ewalls
     assert parsed_layout['food'] == efood
     assert parsed_layout['bots'] == ebots
+    assert parsed_layout['shape'] == (6, 6)
+    assert wall_dimensions(parsed_layout['walls']) == parsed_layout['shape']
 
 def test_hole_in_horizontal_border():
     layout = """
@@ -335,7 +337,7 @@ def test_legal_positions(pos, legal_positions):
             #xy  #
             ###### """)
     parsed = parse_layout(test_layout)
-    assert set(get_legal_positions(parsed['walls'], pos)) == legal_positions
+    assert set(get_legal_positions(parsed['walls'], parsed['shape'], pos)) == legal_positions
 
 
 @pytest.mark.parametrize('pos', [
@@ -354,7 +356,7 @@ def test_legal_positions_fail(pos):
             ###### """)
     parsed = parse_layout(test_layout)
     with pytest.raises(ValueError):
-        get_legal_positions(parsed['walls'], pos)
+        get_legal_positions(parsed['walls'], parsed['shape'], pos)
 
 
 def test_load():
diff --git a/test/test_network.py b/test/test_network.py
index 49de48e7..f1c6a6d5 100644
--- a/test/test_network.py
+++ b/test/test_network.py
@@ -76,6 +76,7 @@ def test_simpleclient(zmq_context):
                           (0, 2),                 (3, 2),
                           (0, 3), (1, 3), (2, 3), (3, 3),
                           ],
+                'shape': (4, 4)
             }
         }
     }
diff --git a/test/test_team.py b/test/test_team.py
index 24ac7fd8..703ed53d 100644
--- a/test/test_team.py
+++ b/test/test_team.py
@@ -328,7 +328,7 @@ def test_initial_position(_n_test):
     """ Test that out test team receives the correct initial positions."""
     layout_name, layout_string = get_random_layout()
     l = parse_layout(layout_string)
-    initial_pos = initial_positions(l['walls'])
+    initial_pos = initial_positions(l['walls'], l['shape'])
 
     def move(bot, state):
         if bot.is_blue and bot.turn == 0: