NATIONAL UNIVERSITY OF SCIENCES AND TECHNOLOGY

School of Electrical Engineering and Computer Sciences

Artificial Intelligence (CS-272)

Assignment #1

Title of the assignment: Treasure Hunt Game

____________________________________________

SUBMITTED TO: Dr Junaid Younas

SUBMITTED BY: Ali Safdar Saeed - 474219

Abdul Mannan

Saqib Mehmood - 460430

CLASS + SECTION: BSCS-13D

Date of Submission: 30/10/2024

Project Proposal: Treasure Hunt Game Using
Pebbles
Introduction

The treasure hunt game is a classic exploration challenge that engages

players in a quest to locate hidden treasures while navigating a grid-based
environment. In this project, we introduce an innovative twist to the
traditional gameplay by integrating the concept of pebbles as strategic
markers to guide the agent's search efforts. The player starts at a defined
location and must explore the grid, encountering treasures and potential
dangers, such as a monster, along the way.

The game is designed to enhance the player's problem-solving skills and

decision-making abilities, utilizing basic search algorithms to optimize
treasure retrieval while avoiding hazards. By marking visited and dangerous
locations with pebbles, the agent can effectively navigate the grid, ensuring
a systematic exploration that maximizes efficiency and safety.

From the next page is the research part from every project member.
Ali Safdar Saeed (474219)
An overview of path planning algorithm
(by Zhuozhen Tang and Hongzhong Ma)
This research paper provided a comprehensive overview of path planning
algorithms for unmanned systems. I found this research paper compelling
because it gives a general view of how path planning algorithms work in
different situations. We obviously need to understand some of these
algorithms in order to tackle various difficulty levels in our project.

This paper basically emphasizes the need for adaptive, efficient path
planning algorithms that can handle the complexities of different scenarios.
An algorithm that may work well in one case may not work well in another.

This paper describes how path planning may vary depending on what kind of
environment we are dealing with. It talks about environment modeling,
differentiating between static and dynamic environments. Traditional
methods like Dijkstra's, A*, D*, LPA*, and D* Lite are also discussed in this
paper. I learned about the algorithms like PRM (Probabilistic Roadmap) and
RRT (Rapidly exploring Random Trees) that rely on sampling to explore
feasible paths and are effective for complex, high-dimensional spaces.

A Systematic Literature Review of A* Pathfinding

(by Daneil Foead, Alifio Ghifari, Marchel Budi Kusuma,
Novita Hanafiah, Eric Gunawan)
I wanted to learn a bit more about the Heuristic search algorithms, and how
these work with A* algorithm to give an efficient and flexible way of
pathfinding, and this paper helped me do exactly that. This paper offered a
comprehensive overview of the A* algorithm, emphasizing its applications,
strengths, weaknesses, and certain improvements that could be made.

The A* search algorithm is a pathfinding method that uses a heuristic to

efficiently find the shortest path from a start node to a goal node by
minimizing the total estimated cost (which is actual cost + heuristic cost).

This paper explained that A* performs well in many path-finding scenarios,

especially when combined with heuristic methods that help it estimate the
path distance efficiently. However, this algorithm has its limitations when
dealing with larger grid sizes or multi-agent pathfinding.
This algorithm is very versatile and can be used when the maze difficulty is
increasing. Its effectiveness heavily depends on the chosen heuristic. We can
make certain modifications, such as Euclidean distance, diagonal distance, or
Manhattan distance, to improve its path-finding accuracy or speed.

Advice Complexity of Treasure Hunt in Geometric Terrains

(by Andrzej Pelc and Ram Narayan Yadav)
We wanted to add a feature to our project where the agent might get some
‘clues’ along the way as to where the treasure is. To understand some of the
concepts related to this functionality, I read this paper.

This paper explained the concept of ‘advice complexity’ in the context of a

mobile agent performing a treasure hunt in a geometric terrain with
obstacles. The paper focuses on minimizing the cost, defined as the
trajectory length from the agent's starting point to the treasure, while
measuring how much external information "advice" is necessary to achieve
this efficiently.

Advice complexity measures the minimum amount of information needed for

the agent to navigate successfully. This advice is provided as a binary string
by an "oracle" aware of the complete environment. The goal is to get the
agent to the goal in minimum steps possible, and minimum advice given.
The paper shows that the advice complexity increases exponentially in
arbitrary terrains, making it much harder for the agent to navigate.

Research Gaps and Improvements:

Although there are many search algorithms but finding the one that hits the
sweet spot between speed and performance will be the key. An algorithm like
A* although an efficient one, does not give good results while dealing with
complex mazes. We will try to make the mentioned modifications to make
our algorithm more adaptative to a variety of challenges.
As for the advice complexity, it is very effective in simple terrains but not so
good when dealing with arbitrary routes. We will possibly try some sort of an
algorithm that would divide the route to the treasure into several ‘check
points’ which would decrease the overall burden in an overly complex game.
Abdul Mannan:
In this section, we will include citations of relevant research papers related to
treasure hunt algorithms, search strategies, and the use of pebbles in
guiding agents. These citations will provide a theoretical framework for the
project and support the implementation of the proposed gameplay
mechanics.

 Pebble Guided Near Optimal Treasure Hunt in Anonymous Graphs

 Treasure Hunt in Graph Using Pebbles

 Advice complexity of treasure hunt in geometric terrains

Explanation:

These three papers investigate the challenge of guiding a mobile agent to

locate a hidden treasure in an anonymous graph, where neither the structure
of the graph nor the treasure’s position is known. The agent begins at an
initial node and must find the treasure, which is located at a distance \( D \)
without labeled nodes. To aid the agent, pebbles are strategically placed at
nodes to direct it efficiently, balancing the number of pebbles with the time
required for the search.

The first paper explores the relationship between pebble quantity and search
time, presenting algorithms that achieve nearly optimal results based on the
number of pebbles and node degrees. The second paper refines this idea by
proposing a deterministic treasure hunt algorithm, showing that an agent can
locate the treasure within close-to-minimal edge traversal costs, even with
movement constraints, disproving a long-standing conjecture about graph
exploration costs. The third paper seeks the fastest treasure hunt algorithm
possible, regardless of pebble count, presenting an approach that optimizes
both the pebble use and search time relative to the graph's properties.

Together, these studies provide foundational strategies for treasure hunts in

unknown graphs, highlighting that carefully placed pebbles can create
efficient search paths while minimizing the time required for exploration,
forming the basis of our approach to developing a near-optimal treasure hunt
algorithm for arbitrary graphs.
3. Proposed Approach

In this project, we propose an approach that leverages the concept of

pebbles to enhance the agent's navigation and exploration capabilities in the
treasure hunt game. The approach consists of the following key components:

1. Grid Environment:

o The game is structured as a grid (e.g., 5x5), where the agent

starts at a designated location, and treasures and monsters are
randomly placed within the grid.

2. Pebble Mechanism:

o Marking Visited Locations: As the agent explores the grid, it

will place pebbles at locations it has already visited. This
prevents redundant movements and ensures that the agent
focuses on unvisited areas.

o Tracking Dangerous Areas: If the agent encounters danger

(e.g., being near a monster), it will place a pebble to indicate the
unsafe location, enabling the agent to avoid these areas in future
moves.

3. Exploration Strategy:

o The agent will adopt a systematic exploration strategy,

prioritizing movement toward the nearest unvisited location. The
presence of pebbles will guide the agent in making informed
decisions about where to explore next, effectively managing its
search space.

4. Dynamic Adaptation:

o The agent's decision-making process will dynamically adapt

based on the pebbles' information, allowing it to optimize its path
toward collecting all treasures while minimizing the risk of
encountering the monster.

5. Game Loop:

o A continuous game loop will facilitate user interaction, where

players input commands (move left, right, up, down, or quit) and
receive real-time feedback on their position, encountered
treasures, and proximity to danger.
Muhammad Saqib Mehmood (460430)
In this section, I will include citations of relevant research papers related to
treasure hunt algorithms, search strategies, and the use of pebbles in
guiding agents. These citations will provide a theoretical framework for the
project and support the implementation of the proposed gameplay
mechanics. Here are the citations:

Learning-Based Algorithms for Graph Searching Problems ( Adela

Frances DePavia , Erasmo Tani - University of Chicago & Ali Vakilian TTIC )

A New Solution for N-Queens Problem using Blind Approaches: DFS

and BFS Algorithms

Improvement of Dijkstra’s Algorithm and Its Application in Route

Planning

Literature Review and Research Gaps

BFS and DFS in N-Queens Problem:

 Summary: BFS and DFS are applied to solve the N-Queens problem,
highlighting DFS’s efficiency in low-memory and constrained search
areas, despite BFS’s broader exploration benefits.
 Gaps Identified: The standard BFS/DFS lacks optimization for
environments with many obstacles, which increases computational
demand and memory usage.
 Proposed Solution: Incorporate hybrid search approaches or
heuristics that direct the search toward probable treasure locations,
reducing unnecessary path exploration.

Learning-Based Algorithms for Graph Searching:

 Summary: Learning-based algorithms improve search efficiency by

using predictive hints, often with noisy data, to guide the search agent.
Performance is optimal when hints are accurate, though errors can
degrade outcomes.
 Gaps Identified: The learning model's dependency on accurate hints
limits robustness when prediction errors are high, impacting practical
navigation in uncertain environments.
 Proposed Solution: Implement adaptive strategies that handle hint
inaccuracies. For example, allowing the AI to recalculate paths when
hints are inconsistent, improving navigation in the grid.

Improvement of Dijkstra’s Algorithm in Route Planning:

 Summary: Optimized Dijkstra's algorithm improves storage and

search areas, significantly lowering search time by narrowing the
search to likely paths.
 Gaps Identified: The optimized Dijkstra’s algorithm sacrifices
absolute path accuracy for reduced search areas, which may miss
optimal paths in complex grids.
 Proposed Solution: Employ restricted search areas for efficiency but
supplement with periodic full-search checks, balancing accuracy with
optimized computation for the treasure hunt.

Agent Pathfinding:

BFS/DFS Foundations: The agent begins with basic BFS or DFS to explore
the grid systematically. DFS will be used for deeper search in paths with
minimal obstacles, while BFS is suitable for finding the shortest route in
obstacle-dense regions.

Dijkstra’s Optimized Algorithm: For grids with complex obstacles,

Dijkstra’s algorithm, with restricted search areas, will efficiently limit
exploration to likely paths to the treasure.

Learning-Based Adaptations: Hints in certain cells guide the AI using

predictive paths, updated with error-handling to manage inaccurate hints.
This approach allows for adaptive learning as the agent progresses.

Research Gaps and Improvements in Treasure Hunt Context

 Hybrid Pathfinding Approach: While BFS and DFS provide strong

foundational exploration, integrating Dijkstra’s optimizations and hint-
based learning can handle complex or changing environments better.
 Error-Adaptive Learning: Implement error-tolerant hint processing,
allowing the agent to adapt to and correct path predictions
dynamically.
 Storage and Memory Optimization: For large grids, store only
necessary paths or hints using adjacency lists to conserve memory,
following improvements seen in the optimized Dijkstra’s approach.

Implementation Roadmap

Phase 1: Develop the base grid structure and implement BFS and DFS for
initial exploration.

Phase 2: Introduce Dijkstra’s algorithm, optimized with restricted search

areas, for faster route identification in complex grids.

Phase 3: Add hint-based cells and integrate learning-based algorithms to

guide the AI agent, with adaptive error-handling to refine path predictions.

Phase 4: Test and refine the AI’s navigation with increasing grid complexity,
balancing efficiency with accuracy in treasure discovery.

Conclusion
This treasure hunt game presents an engaging and educational platform to
explore fundamental concepts in search algorithms and decision-making
processes. By integrating the pebble mechanism into the gameplay, we aim
to provide a sophisticated approach to guiding agents in complex
environments, ultimately enhancing the player’s experience and
understanding of strategic exploration.