-
Notifications
You must be signed in to change notification settings - Fork 0
Home
This wiki documents the development of an AI agent capable of beating the classic Snake Game. My approach involves implementing and evaluating various search algorithms, drawing inspiration from Artificial Intelligence: A Modern Approach (AIMA) by Russell and Norvig.
The primary goal is to create a Snake AI that can consistently achieve high scores by efficiently navigating the game environment and consuming food. This involves exploring and comparing different search algorithms to determine the most effective strategies.
I have successfully implemented four fundamental search algorithms:
- Breadth-First Search (BFS)
- Depth-First Search (DFS)
- Uniform Cost Search (UCS)
- A* Search
These algorithms enable the snake to find paths to the food. However, their effectiveness diminishes as the snake grows longer. Obstacles created by the snake's own body can block direct paths, leading to suboptimal decisions or even failure.
The main challenge encountered so far is the snake's inability to effectively navigate when its own body obstructs the path to the food. While the implemented algorithms work well in open environments, they struggle in more complex scenarios created by the increasing length of the snake. Randomly selecting a seemingly safe path is a temporary solution but has significant limitations.
My current focus is on implementing online search algorithms, as described in Chapter 5 of AIMA. These algorithms will enable the snake to dynamically adapt its path-finding strategy based on the current game state. In addition to online search, I am exploring planning techniques that will allow the snake to anticipate future moves and avoid self-collision more effectively.
A core feature of this project is its modular design. The AI agent is separated from the core game logic, allowing for easy experimentation with different algorithms. This modularity provides a dedicated "experiment space" where new algorithms can be integrated and tested without affecting the rest of the code. You can add your algorithms and test them without affecting the rest of the code.
- Greedy Best-First Search: Uses a heuristic to choose the most promising path without considering path cost.
- Iterative Deepening A* (IDA*): Combines depth-first search with iterative deepening and uses A* for evaluation.
- Planning Agents based on Chapter 5 and 6 of AIMA.
Through continued development and experimentation, I aim to achieve the following:
- Implement and evaluate a range of online search and planning algorithms.
- Develop a Snake AI that can consistently achieve high scores, even in complex scenarios.
- Provide a well-documented and modular codebase that can serve as a foundation for further research and development in this area.