Explore Courses Blog Tutorials Interview Questions
0 votes
in AI and Deep Learning by (50.2k points)

I am currently working on an AI Agent that will be able to identify both the start state and the goal state of the famous old plumbing game found here

The idea is to allow the water to flow from the start point to the exit point, the AI only rotate the tiles, and not all tiles and populated, The problem that this will be an unguided search. I am really lost and help will be appreciated.

What I thought about is that I should assign a number for each tile and rotation and make a series of allowed sequences? but I am not sure if that's the best way to go or not, because the sequence will be 10! which is huge. The other approach can be assigning the holes of each pipe as North, West, South, East and check if the tiles link?

The solution should be flexible and tiles might shuffle/Change so assigning the goal state manually won't work.

Any ideas will be greatly appreciated.

1 Answer

0 votes
by (108k points)

In the original plumbing game, the player can click on a tile and change it's direction clockwise only. This allows generating a path for the water flow from start to the goal. The amount of possible actions is indeed exponential and can't be calculated on a normal computer.

To solve this problem, macro actions will be a perfect choice. A macro action is a virtual action not available in the original game. It's a self-invented abstract game on top of the original one. A possible macro action would build a path to a waypoint in the middle, and a second macro action generates a path from the middle to the end. The newly created macro actions can be solved independently by a hierarchical planner and the resulting low-level actions are executed in the original game.

A possible programming language to realize macro actions is the game description language, PDDL or formal grammar. If the concept was understood, even normal Python code can be used to realize the abstract game. A possible macro action results in a state, similar to what is called in the deep learning community a reward. This allows subdividing the problem into smaller chunks.

For the plumbing game, no ready-to-run solver is described in the literature, but the Sokoban game was discussed before: Zhou, Neng-Fa, and Agostino Dovier. "A tabled Prolog program for solving Sokoban." Fundamenta Informaticae 124.4 (2013): 561-575.

Browse Categories