IART Assignment No. 1 Solved

Assignment No. 1 

Heuristic Search Methods for Problem Solving 

Adversarial Search Methods for Games  Optimization Methods/Meta-Heuristics 

Theme
IART's first practical work consists in the development of a program related to one of three possible topics. 

Topic 1: Heuristic Search Methods for One Player Solitaire Games
A solitaire game is characterized by the type of board and pieces, the rules of movement of the pieces (possible operators/plays), and the conditions for ending the game with defeat (impossibility to solve, maximum number of moves reached, time limit reached) or victory (solitaire solved), together with the respective score. Typically, in the event of a win, a score is awarded depending on the number of moves, resources spent, bonuses collected and/or time spent. 

In addition to implementing a solitaire game for a human player, the program must be able to solve different versions/levels of this game, using appropriate search methods, focusing on the comparison between uninformed search methods (breadth-first search, depth-first search, iterative deepening, uniform cost) and heuristic search methods (greedy search, A* algorithm), with different heuristic functions. The methods applied should be compared at various levels, with emphasis on the quality of the solution obtained, number of operations performed, maximum memory used, and time spent to obtain the solution. 

The application should have a text or graphic view to show the evolution of the board and interact with the user/player. You should allow a game mode in which the PC solves the solitaire alone using the method and its configuration selected by the user. Optionally, you can allow a Human game mode in which the user can solve the game, eventually asking the PC for “hints”. 

Topic 2: Adversarial Search Methods for Two-Player Board Games
A board game is characterized by the type of board and tiles, the rules of movement of the pieces (operators/possible moves) and the finishing conditions of the game with the respective score. In this work, the aim is to implement a game for two players and solve different versions of this game, using the Minimax search method with α cuts and its variants. 

Human-human, human-computer and computer-computer game modes should be developed, where the computer should exhibit different skills (levels of difficulty). Computer performance should be compared regarding the different skills (e.g., hard, medium, easy), corresponding to different evaluation functions, different depth levels of Minimax, different successor generation ordering and/or variants of the Minimax algorithm. Emphasis should be placed on the analysis of the results of the computer players (wins, draws, losses, and other quality parameters, such as the number of plays to obtain the win/loss) and average time spent to obtain the solutions/plays. 

The application to be developed must have a proper user interface in text or graphic mode, to show the evolution of the board and interact with the user / player. You must allow the game modes indicated above, allowing the selection of the game mode, type of each player, and skills of computer players. You should allow different skilled computer players to play with each other. You may also consider providing human players with movement “hints”. 

Topic 3: Metaheuristics for Optimization/Decision Problems
An optimization problem is characterized by the existence of a (typically large) set of possible solutions, comparable to each other, of which one or more are considered (globally) optimal solutions. Depending on the specific problem, an evaluation function allows you to establish this comparison between solutions. In many of these problems, it is virtually impossible to find the optimal solution, or to ensure that the solution found is optimal and, as such, the goal is to try to find a local optimal solution that maximizes/minimizes a given evaluation function to the extent possible. 

In this work, the aim is to implement a system to solve an optimization problem, using different algorithms or meta-heuristics such as: hill-climbing, simulated annealing, tabu search, and genetic algorithms (you may include other algorithms or variations of these). Multiple instances of the chosen problem must be solved, and the results obtained by each algorithm must be compared. Different parameterizations of the algorithms should be tested and compared, in terms of the average quality of the solution obtained and the average time spent to obtain the solutions. 

The application to be developed should have an appropriate visualization in text or graphic mode, to show the evolution of the quality of the solution obtained along the way and the final solutions, and to interact with the user. You should allow the selection and parameterization of the algorithms and the selection of the instance of the problem to be solved. 

Programming Language
Any programming language and development system can be used, including, at the language level, C++, Java, Python, C#, Prolog, among others. The choice of language and development environment to be used is the entire responsibility of the students. In previous years, Python, C++ and Java were the languages selected by most of the students. 

Groups
Groups must be composed of 3 students (exceptionally 2). Individual groups or groups composed of 4 students are not accepted. Groups can be composed of students from different classes (a maximum of two different classes) but all students must be present in the checkpoint sessions and presentation/demonstration of the work. The establishment of groups composed of students from different classes is not advised, given the logistic difficulties of performing work that this can cause. 

Checkpoint
Each group must submit in Moodle a brief presentation (max. 5 slides), in PDF format, which will be used in the class to analyze, together with the teacher, the progress of the work. The presentation should contain:    (1) specification of the work to be performed (definition of the game or optimization problem to be solved), (2) related work with references to works found in a bibliographic search (articles, web pages and/or source code), (3) formulation of the problem as a search problem (state representation, initial state, objective test, operators (names, preconditions, effects and costs), heuristics/evaluation function) or optimization problem (solution representation, neighborhood/mutation and crossover functions, rigid constraints, evaluation functions), and (4) implementation work already carried out (programming language, development environment, data structures, file structure, among others). 

Final Delivery
Each group must submit in Moodle two files: a presentation (max. 10 slides), in PDF format, and the implemented code, properly commented, including a “readme” file with instructions on how to compile, run and use the program. Based on the submitted presentation, the students must carry out a demonstration (about 10 minutes) of the work, in the practical class, or in another period to be designated by the teachers of the course. 

The file with the final presentation should include, in addition to the aforementioned for the checkpoint, details on: (5) the approach (heuristics, evaluation functions, operators, ...) and (6) algorithms implemented (search algorithms, minimax, metaheuristics), as well as (7) experimental results, using appropriate tables/plots and comparing the various methods, heuristics, algorithms and respective parameterizations for different scenarios/problems. The presentation shall include a slide of conclusions and another of references consulted and materials used (software, websites, scientific articles, ...). 

Suggested Problems
Topic 1: One Player Solitaire Games
1A) Match the Tiles 

1B) Ball Sort Puzzle 

1C) TenPair  

1D) Aquarium 

Topic 2: Two-Player Adversarial Games
2A) Neutreeko (online) 

2B) Emergo (online) 

2C) Tak (online) 

2D) Shobu (video) 

Topic 3: Optimization Problems
3A) Book scanning (data) 

3B) Router placement (data) 

3C) Streaming videos (data) 

3D) Delivery (data)