{
    "info": {
        "author": "Max-Philipp Schrader",
        "author_email": "",
        "bugtrack_url": null,
        "classifiers": [
            "License :: OSI Approved :: MIT License",
            "Operating System :: OS Independent",
            "Programming Language :: Python :: 3"
        ],
        "description": "# gym-sokoban \n[Sokoban](https://en.wikipedia.org/wiki/Sokoban) is Japanese for warehouse keeper and a traditional video game.\nThe game is a transportation puzzle, where the player has to push all boxes in the room on the storage locations/ targets.\nThe possibility of making irreversible mistakes makes these puzzles so challenging especially for [Reinforcement Learning](https://en.wikipedia.org/wiki/Reinforcement_learning) algorithms, which mostly lack the ability to think ahead.\n<br/>The repository implements the game Sokoban based on the rules presented [DeepMind's]() paper [Imagination Augmented Agents for Deep Reinforcement Learning](https://papers.nips.cc/paper/7152-imagination-augmented-agents-for-deep-reinforcement-learning). \nThe room generation is random and therefore, will allow to train Deep Neural Networks without overfitting on a set of predefined rooms.\n\n\n| Example Game 1 | Example Game 2 | Example Game 3 |\n| :---: | :---: | :---: \n| ![Game 1](/docs/Animations/solved_3.gif?raw=true) | ![Game 2](/docs/Animations/solved_4.gif?raw=true) | ![Game 3](/docs/Animations/solved_5.gif?raw=true) |\n\n\n## 1 Installation\n\n### Via PIP\n```bash\npip install gym-sokoban\n```\n\n### From Repository\n```bash\ngit clone git@github.com:mpSchrader/gym-sokoban.git\ncd gym-sokoban\npip install -e .\n```\nCheckout the [examples](https://github.com/mpSchrader/gym-sokoban/examples) on how to use an external gym environment.\n\n## 2 Game Environment\n\n### 2.1 Room Elements\nEvery room consists of five main elements: walls, floor, boxes, box targets, and a player. They might have different states whether they overlap with a box target or not. \n\n| Type       | State      | Graphic | TinyWorld |\n| ---        | -----      | :---: | :---: |\n| Wall       | Static     | ![Wall](https://github.com/mpSchrader/gym-sokoban/gym_sokoban/envs/surface/wall.png \"Wall\") | ![Wall](https://github.com/mpSchrader/gym-sokoban/gym_sokoban/envs/surface/tiny_world/wall.png \"Wall\") |\n| Floor      | Empty      | ![Floor](https://github.com/mpSchrader/gym-sokoban/gym_sokoban/envs/surface/floor.png \"Floor\") | ![Floor](https://github.com/mpSchrader/gym-sokoban/gym_sokoban/envs/surface/tiny_world/floor.png \"Floor\") |\n| Box Target | Empty      | ![BoxTarget](https://github.com/mpSchrader/gym-sokoban/gym_sokoban/envs/surface/box_target.png \"Box Target\") | ![BoxTarget](https://github.com/mpSchrader/gym-sokoban/gym_sokoban/envs/surface/tiny_world/box_target.png \"Box Target\") |\n| Box        | Off Target | ![BoxOffTarget](https://github.com/mpSchrader/gym-sokoban/gym_sokoban/envs/surface/box.png \"Box\") | ![BoxOffTarget](https://github.com/mpSchrader/gym-sokoban/gym_sokoban/envs/surface/tiny_world/box.png \"Box\") |\n| Box        | On Target  | ![BoxOnTarget](https://github.com/mpSchrader/gym-sokoban/gym_sokoban/envs/surface/box_on_target.png \"Box\") | ![BoxOnTarget](https://github.com/mpSchrader/gym-sokoban/gym_sokoban/envs/surface/tiny_world/box_on_target.png \"Box\") |\n| Player     | Off Target | ![PlayerOffTarget](https://github.com/mpSchrader/gym-sokoban/gym_sokoban/envs/surface/player.png \"Player\") | ![PlayerOffTarget](https://github.com/mpSchrader/gym-sokoban/gym_sokoban/envs/surface/tiny_world/player.png \"Player\") |\n| Player     | On Target  | ![PlayerOnTarget](https://github.com/mpSchrader/gym-sokoban/gym_sokoban/envs/surface/player_on_target.png \"Player\") | ![PlayerOnTarget](https://github.com/mpSchrader/gym-sokoban/gym_sokoban/envs/surface/tiny_world/player_on_target.png \"Player\") |\n\n### 2.2 Actions\nThe game provides 9 actions to interact with the environment. \nPush and Move actions into the directions Up, Down, Left and Right.\nThe No Operation action is a void action, which does not change anything in the environment.\nThe mapping of the action numbers to the actual actions looks as follows\n\n | Action       | ID    | \n | --------     | :---: | \n | No Operation | 0     | \n | Push Up      | 1     |  \n | Push Down    | 2     | \n | Push Left    | 3     |   \n | Push Right   | 4     |   \n | Move Up      | 5     |\n | Move Down    | 6     |\n | Move Left    | 7     |\n | Move Right   | 8     |\n\n**Move** simply moves if there is a free field in the direction, which means no blocking box or wall.\n\n**Push** push tries to move an adjacent box if the next field behind the box is free.\nThis means no chain pushing of boxes is possible.\nIn case there is no box at the adjacent field, the push action is handled the same way as the move action into the same direction.\n\n### 2.3 Rewards\nFinishing the game by pushing all on the targets gives a reward of 10 in the last step. \nAlso pushing a box on or off a target gives a reward of 1 respectively of -1. \nIn addition a reward of -0.1 is given for every step, this penalizes solutions with many steps.\n\n| Reason                    | Reward |\n| ------------------------- | ----:  |\n| Perform Step              | -0.1   |\n| Push Box on Target        |  1.0   |\n| Push Box off Target       | -1.0   |\n| Push all boxes on targets | 10.0   |\n\n### 2.4 Level Generation\nEvery time a Sokoban environment is loaded or reset a new room is randomly generated.\nThe generation consists of 3 phases: Topology Generation, Placement of Targets and Players, and Reverse Playing.\n#### 2.4.1 Topology Generation\nTo generate the basic topology of the room, consisting of walls and empty floor, is based on a random walk, which changes its direction at probability 0.35.\nAt every step centered at the current position, a pattern of fields is set to empty spaces.\nThe patterns used can be found in [Figure 2](#topologyMask).\n<div style=\"padding:20%\">\n  <p align=\"center\">\n    <img src=\"/docs/masks.png?raw=true\">\n  </p>\n  <p align=\"center\" id=\"topologyMask\">\n    Figure 2: Masks for creating a topology\n  </p>\n</div>\n\n\n#### 2.4.2 Placement of Elements\nDuring this phase, the player including all n box targets are placed on randomly chosen empty spaces.\n\n#### 2.4.3 Reverse Playing\nThis is the crucial phase to  ensure a solvable room.\nNow Sokoban is played in a reverse fashion, where a player can move and pull boxes.\nThe goal of this phase is to find the room state, with the highest room score, with a [Depth First Search](https://en.wikipedia.org/wiki/Depth-first_search).\nFor every room explored during the search is a room score is calculated with the equation shown below.\nThe equation is a heuristic approach to evaluate the difficulty of the room.\nBoxSwaps counts the number of times a player changes the box to pull.\nBoxDisplacement is the [Manhattan Distance](https://en.wikipedia.org/wiki/Manhattan_distance) between a specific box and its origin box target. \nAs long as at least one box is on a target the RoomScore is always 0.\n<div style=\"padding:10%\">\n  <p align=\"center\">\n   <img src=\"https://latex.codecogs.com/svg.latex?\\Large&space;RoomScore&space;=&space;BoxSwaps&space;\\times&space;\\sum_{i&space;\\in&space;Boxes}_{BoxDisplacement_{i}}\" title=\"Room Score\" />\n  </p>\n</div>\n\n### 2.5 Configuration\nSokoban has many different variations, such as: Room Size, Number of Boxes, Rendering Modes, or Rules.\n\n#### 2.5.1 Rendering Modes\nBesides the regular Sokoban rendering, each configuration can be rendered as TinyWorld, which has a pixel size equal to the grid size. \nTo get an environment rendered as a tiny world just add `tiny_` in front of the rendering mode. E.g: `env.render('tiny_rgb_array', scale=scale_tiny)`. Scale allows to increase the size of the rendered tiny world observation. Using scale in combination with the rendering modes, `human` or `rgb_array`, does not influence the output size.\nAvailable rendering modes are:\n\n| Mode | Description |\n| ---  | --- \n| rgb_array | Well looking 2d rgb image\n| human | Displays the current state on screen\n| tiny_rgb_array | Each pixel describing one element in the room\n| tiny_human | Displays the tiny rgb_array on screen\n\n\n#### 2.5.2 Size Variations\nThe available room configurations are shown in the table below. \n\n| Room Id | Grid-Size | Pixels | #Boxes | Example | TinyWorld |\n| --- | :---: | :---: | :---: | :---: | :---: |\n| Sokoban-v0 | 10x10 | 160x160 | 3 | ![Sokoban-v0](https://github.com/mpSchrader/gym-sokoban/blob/master/docs/rooms/Sokoban-v0.png)  | ![Sokoban-v0](https://github.com/mpSchrader/gym-sokoban/blob/master/docs/rooms/Tiny_World_Sokoban-v0.png) | \n| Sokoban-v1 | 10x10 | 160x160 | 4 | ![Sokoban-v1](https://github.com/mpSchrader/gym-sokoban/blob/master/docs/rooms/Sokoban-v1.png) | ![Sokoban-v1](https://github.com/mpSchrader/gym-sokoban/blob/master/docs/rooms/Tiny_World_Sokoban-v1.png) |\n| Sokoban-v2 | 10x10 | 160x160 | 5 | ![Sokoban-v2](https://github.com/mpSchrader/gym-sokoban/blob/master/docs/rooms/Sokoban-v2.png) | ![Sokoban-v2](https://github.com/mpSchrader/gym-sokoban/blob/master/docs/rooms/Tiny_World_Sokoban-v2.png) |\n| Sokoban-small-v0 | 7x7 | 112x112 | 2 |  ![Sokoban-small-v0](https://github.com/mpSchrader/gym-sokoban/blob/master/docs/rooms/Sokoban-small-v0.png) | ![Sokoban-small-v0](https://github.com/mpSchrader/gym-sokoban/blob/master/docs/rooms/Tiny_World_Sokoban-small-v0.png) |\n| Sokoban-small-v1 | 7x7 | 112x112 | 3 | ![Sokoban-small-v1](https://github.com/mpSchrader/gym-sokoban/blob/master/docs/rooms/Sokoban-small-v1.png) | ![Sokoban-small-v1](https://github.com/mpSchrader/gym-sokoban/blob/master/docs/rooms/Tiny_World_Sokoban-small-v1.png) |\n| Sokoban-large-v0 | 13x11 | 208x176 | 3 | ![Sokoban-large-v0](https://github.com/mpSchrader/gym-sokoban/blob/master/docs/rooms/Sokoban-large-v0.png) | ![Sokoban-large-v0](https://github.com/mpSchrader/gym-sokoban/blob/master/docs/rooms/Tiny_World_Sokoban-large-v0.png) |\n| Sokoban-large-v1 | 13x11 | 208x176 | 4 | ![Sokoban-large-v1](https://github.com/mpSchrader/gym-sokoban/blob/master/docs/rooms/Sokoban-large-v1.png) |  ![Sokoban-large-v1](https://github.com/mpSchrader/gym-sokoban/blob/master/docs/rooms/Tiny_World_Sokoban-large-v1.png) |\n| Sokoban-large-v2 | 13x11 | 208x176 | 5 | ![Sokoban-large-v2](https://github.com/mpSchrader/gym-sokoban/blob/master/docs/rooms/Sokoban-large-v2.png) | ![Sokoban-large-v2](https://github.com/mpSchrader/gym-sokoban/blob/master/docs/rooms/Tiny_World_Sokoban-large-v2.png) | \n| Sokoban-huge-v0 | 13x13 | 208x208 | 5 | ![Sokoban-huge-v0](https://github.com/mpSchrader/gym-sokoban/blob/master/docs/rooms/Sokoban-huge-v0.png) | ![Sokoban-huge-v0](https://github.com/mpSchrader/gym-sokoban/blob/master/docs/rooms/Tiny_World_Sokoban-huge-v0.png)\n\nPlease note that the larger rooms might take some time to be created, especially on a laptop.\n\n#### 2.5.3 Other Variations\nBesides the regular game of Sokoban, this repository implements or will implement variations, which might make the game easier or more complicated. Except noted differently the variations do not implement a Tiny-World version.\n\n| Variation | Summary | Expected Difficulty | Example | Tiny World | Status | Details |\n| ---       | :---:   | :---:               | :---:   | :---: | :---: | :---: |\n| Fixed Targets | Every box has to be pushed on the target with the same color. | More difficult | ![Fixed-Targets](https://github.com/mpSchrader/gym-sokoban/blob/master/docs/rooms/Sokoban-Fixed-Targets-Example.png) | Yes | implemented | [ReadMe](/docs/variations/FixedTargets.md) |\n| Multiple Player | There are two players in the room. Every round one of the two players can be used. There is no order of moves between the two players. | More difficult | ![TwoPlayer](https://github.com/mpSchrader/gym-sokoban/blob/master/docs/rooms/TwoPlayer-Sokoban-v2.png) | Yes | implemented | [ReadMe](/docs/variations/TwoPlayer.md) |\n| Push&Pull | The player can not only push the boxes, but also pull them. Therefore, no more irreversible moves exist. | Easier | ![PushAndPull-Targets](https://github.com/mpSchrader/gym-sokoban/blob/master/docs/rooms/Sokoban-v1.png) | Yes | implemented | [ReadMe](/docs/variations/PushAndPull.md) |\n| Boxoban | Uses by DeepMind [pregenerated Sokoban puzzles](https://github.com/deepmind/boxoban-levels). | Similar | ![PushAndPull-Targets](https://github.com/mpSchrader/gym-sokoban/blob/master/docs/rooms/Sokoban-v1.png) | Yes | Implemented | [ReadMe](/docs/variations/Boxoban.md) |\n\n## 3 Cite\nIf you are using this repository for your research please cite it with the following information:\n```\n@misc{SchraderSokoban2018,\n  author = {Schrader, Max-Philipp B.},\n  title = {gym-sokoban},\n  year = {2018},\n  publisher = {GitHub},\n  journal = {GitHub repository},\n  howpublished = {\\url{https://github.com/mpSchrader/gym-sokoban}},\n  commit = {#CommitId}\n}\n```\n\n## 4 Connect & Contribute\n\n### 4.1 Connect\nFeel free to get in touch with me to talk about this or other projects. \nEither by creating an [issue](https://github.com/mpSchrader/gym-sokoban/issues) or mail me on [LinkedIn](https://www.linkedin.com/in/max-philipp-schrader/).\n\nIf you reached the end and liked the project, please **show your appreciation by starting this project**.\n\n### 4.2 Contribute\nFeel free to contribute to this project by forking the repo and implement whatever you are missing. \nAlternatively, open a new issue in case you need help or want to have a feature added.\n\n\n",
        "description_content_type": "text/markdown",
        "docs_url": null,
        "download_url": "",
        "downloads": {
            "last_day": -1,
            "last_month": -1,
            "last_week": -1
        },
        "home_page": "https://github.com/mpSchrader/gym-sokoban",
        "keywords": "",
        "license": "",
        "maintainer": "",
        "maintainer_email": "",
        "name": "gym-sokoban",
        "package_url": "https://pypi.org/project/gym-sokoban/",
        "platform": "",
        "project_url": "https://pypi.org/project/gym-sokoban/",
        "project_urls": {
            "Homepage": "https://github.com/mpSchrader/gym-sokoban"
        },
        "release_url": "https://pypi.org/project/gym-sokoban/0.0.6/",
        "requires_dist": [
            "gym (>=0.2.3)",
            "numpy (>=1.14.1)",
            "tqdm (>=4.32.1)",
            "imageio (>=2.3.0)",
            "requests (>=2.22.0)"
        ],
        "requires_python": "",
        "summary": "Sokoban environment for OpenAI Gym",
        "version": "0.0.6"
    },
    "last_serial": 5557345,
    "releases": {
        "0.0.6": [
            {
                "comment_text": "",
                "digests": {
                    "md5": "4a9ea37c5d85da9553e4b11395750d10",
                    "sha256": "14e50b1ed985f78b69278af6edb2246dfd4b467cd7adf8e9877b175c328f59ab"
                },
                "downloads": -1,
                "filename": "gym_sokoban-0.0.6-py3-none-any.whl",
                "has_sig": false,
                "md5_digest": "4a9ea37c5d85da9553e4b11395750d10",
                "packagetype": "bdist_wheel",
                "python_version": "py3",
                "requires_python": null,
                "size": 36386,
                "upload_time": "2019-07-19T16:01:52",
                "url": "https://files.pythonhosted.org/packages/4c/7f/e58f969b87f4fedb688e7abac0e369c3b55c4b6886015b2d5337b70be9f5/gym_sokoban-0.0.6-py3-none-any.whl"
            },
            {
                "comment_text": "",
                "digests": {
                    "md5": "15c91c03c6286f05e027563947b55ebf",
                    "sha256": "2e51ccbf9869a3d446ba471e4f6f9230d453e2378c354c46331d023e0ed50156"
                },
                "downloads": -1,
                "filename": "gym_sokoban-0.0.6.tar.gz",
                "has_sig": false,
                "md5_digest": "15c91c03c6286f05e027563947b55ebf",
                "packagetype": "sdist",
                "python_version": "source",
                "requires_python": null,
                "size": 16446,
                "upload_time": "2019-07-19T16:01:53",
                "url": "https://files.pythonhosted.org/packages/04/7f/f48a268c8b4edb5672a6c6ffab122d2cf900eecdc373ee89ef6069c15e03/gym_sokoban-0.0.6.tar.gz"
            }
        ]
    },
    "urls": [
        {
            "comment_text": "",
            "digests": {
                "md5": "4a9ea37c5d85da9553e4b11395750d10",
                "sha256": "14e50b1ed985f78b69278af6edb2246dfd4b467cd7adf8e9877b175c328f59ab"
            },
            "downloads": -1,
            "filename": "gym_sokoban-0.0.6-py3-none-any.whl",
            "has_sig": false,
            "md5_digest": "4a9ea37c5d85da9553e4b11395750d10",
            "packagetype": "bdist_wheel",
            "python_version": "py3",
            "requires_python": null,
            "size": 36386,
            "upload_time": "2019-07-19T16:01:52",
            "url": "https://files.pythonhosted.org/packages/4c/7f/e58f969b87f4fedb688e7abac0e369c3b55c4b6886015b2d5337b70be9f5/gym_sokoban-0.0.6-py3-none-any.whl"
        },
        {
            "comment_text": "",
            "digests": {
                "md5": "15c91c03c6286f05e027563947b55ebf",
                "sha256": "2e51ccbf9869a3d446ba471e4f6f9230d453e2378c354c46331d023e0ed50156"
            },
            "downloads": -1,
            "filename": "gym_sokoban-0.0.6.tar.gz",
            "has_sig": false,
            "md5_digest": "15c91c03c6286f05e027563947b55ebf",
            "packagetype": "sdist",
            "python_version": "source",
            "requires_python": null,
            "size": 16446,
            "upload_time": "2019-07-19T16:01:53",
            "url": "https://files.pythonhosted.org/packages/04/7f/f48a268c8b4edb5672a6c6ffab122d2cf900eecdc373ee89ef6069c15e03/gym_sokoban-0.0.6.tar.gz"
        }
    ]
}