Grid Game Painter

Introduction:

The assignment for my CS5100: Foundations in Artificial Intelligence class served as an exploration of local search methods. Given an n x n grid with some cells pre-filled with one of four colors at random, a "paintbrush" capable of painting in one of the four colors and eight differently sized and oriented shapes, the AI agent colors the grid using as few colors as possible and as few shapes as possible. The AI agent must interact with the environment solely using the actions as if it were a 3rd person player. 

​

My method:

I used a greedy implementation that pans over every cell and, if the cell is unpainted, chooses the largest shape and first color in a fixed sequence of the four color options. 

​

What is local search and what other methods could have been used?

Local search is a broad term that encompasses many methods that can be used to observe the conditions of an environment. Local search can usually be associated to graph/maze problems. 

​

Breadth First Search (BFS): A local search method where an agent explores every possible action from a given source before proceeding to the next state. In this application, BFS could iterate through all of the shapes and colors and save the maximal shape/color possible to use at the end.

​

Depth First Search (DFS): A local search method where an agent explores as deeply along a path as it can until no other action can be taken.​

Assignment

Code