SECTION A2 (25 marks): Using the game of checkers to model and explore agent theories. Each question is worth 5 marks. Answer EVERY question.

Indicative word length per question: 75-100 words. DO NOT EXCEED THIS WORDCOUNT.

  1. What type of ENVIRONMENT is exhibited by the game of checkers? Give reasons your answer.

The game of checkers exhibits a Discrete of a continuous environment, given that there are finite number of moves or actions that can be performed while playing. Although the number of moves may vary during a game of checkers, it is still finite. A player is forced to enforce a specific move based on the move taken by the opponent player, every situation may involve a number of optional moves and every player makes a specific move based on strategy.

  • Indicate what types of minimal behaviours are required for a purely REACTIVE agent to play the game. What game play corresponds to this minimal specification?

Purely Reactive agents choose their actions with no basis to previous information. Actions are chosen based on current information and just respond to the environment in which they exist in. The game of checkers represents behaviours as checkers, the minimal checkers required are two one for infected and the other one for infected. One game play that corresponds to such minimal specification is Draught’s game.

  • What are the advantages and disadvantages of pure reactivity in the context of checkers?

Advantages include the simplicity of options, a player does not have to think hard beforehand, the computational tractability such that based on opponents moves one can be pursued to make a specific move and fault tolerance, a player can continue to make moves even after making an error. Disadvantages include the need for critical thinking before choosing a specific move, agents are also sort of short sighted which may hamper the quality of decision making and finally, the relationship between moves is not so clear.

  • To think strategically, a PRO-ACTIVE agent would need to PLAN ahead. With reference to the STRIPS ACTION DESCRIPTION LANGUAGE:
  1. Consider at least 4 GOALS a checker agent may generate to optimise game-play

Goals may include;

  1. Remove every opposing piece from the board
    1. Win the player that stalemates the opponent.
    2. Leave Your Home Row Checkers Until You Need Them
    3. Blocking all the pieces of the enemy
  2. The ACTIONS required to fulfil the goals
    1. Jump diagonally
    2. Jump forward
    3. Single Jump
    4. Multi Jump
  3. The PRE-CONDITIONS necessary for an action to be triggered
  4. Opponent moves to new position
  5. Opponent piece captured

iv) How the ADD and DELETE lists generated by each action are updated to reflect how the ENVIRONMENT has changed

The first ACTION SCHEMA is given:

GOAL: jump

PRECONDITION: opponent in adjacent square

ADD: opponent taken; new position

DELETE: old position

  • What types of UTILITY FUNCTIONS could an agent checker player devise to optimise the utility and effectiveness of each move?

The effectiveness of each move can be made effective by backing up two or more checkers to improve immunity from capture. A player can also trade a capture for another capture if it provides more advantage. Leave home row checkers until when needed, this prevents the opponent from having king pieces. You can also move to block an opponent move as much as possible to reduce their ability to capture your pieces.

SECTION B (50 marks):

This section refers to the practical exercises we undertook towards the end of semester two and the research paper: “A Comparative Study of ACO, GA and SA for Solving Travelling Salesman Problem” Kumbharana et al., as previously studied, and expected answers relate to this paper but other answers are acceptable. Where the algorithms are; ant colony optimization (ACO), genetic algorithms (GA), and simulated annealing (SA).

1. Explain why the travelling salesman problem is of interest to computer scientists.

The travelling salesman problem is of specific interest to computer scientists as it seems so easy to describe but complex to solve. The criticality of the travelling salesman problem is illustrative of a bigger set of combinational optimization problems. It offers theoretical computer scientists the ability to tests the boundaries of efficient computation.  Furthermore, it is important when applied to problems with many variants.  Its inherent practical nature which enables computer scientists to apply routing problems not only for tourism or leisure scenarios, but also situations relevant to business and logistics.  It also allows computer scientists to put into practice theories of machine learning. In addition, the problem has applications from different fields including computer science, transportation and logistics, genetics and electronics. Despite the fact that the problem has been studied for decades, to date, there is no universal solution which offers a much greater reason to study it for computer scientists.

2. The pseudo code for GA is to remind you of the algorithm. With reference to the TSP, explain how TWO of the items ‘crossover’, ‘mutation’ and ‘evaluate fitness’ could be implemented.

begin procedure GA

generate populations and fitness function

evaluate population

while(termination criteria not meet)

{

while (best solution not meet)

{

crossover

mutation

evaluate fitness

}

}

post-process results and output

end GA procedure

The approach utilizes chromosomes population at the start point then eery chromosome is tested based on the idealness using a fitness function. Based on the pseudo code, best chromosomes are picked then taken through a process of mutation and crossover to establish a new group of chromosomes. In this case the crossover operator borrows from the good features of the parent population and are passed over to the next population, which would then have a better fitness compared to the parent.

Mutation in this context results in diversity of the population through local modifications to the new generation obtained above via a random process. The outcome is similar to the parent except for the changes achieved through mutation. Through a repeat iteration process, continuously a better generation is achieved, guaranteeing a better generation each time to a point where not more enhanced generations can be obtained. It is a process that offers improvements to a problem solution through continuous repeat processes to perfect the solution to a point where the best solution possible is obtained.

3. The pseudo code for ACO is to remind you of the algorithm. Outline the advantages and limitations of the ACO.

begin procedure ACO

generate pheromone trails and other parameters

while(termination criteria not meet)

{

construct solutions

update pheromone Trails

}

post-process results and output

end ACO procedure

The Ant Colony optimization approach to solving the travelling Salesman problem has a number of advantages and disadvantages. Advantages include that it benefits from the concepts of distributed computing drawing from theories of various fields of computing. It is also comprehensive and can easily be applied to other algorithms to enhance other approaches. Furthermore, they have an upper hand over genetic algorithms or simulated annealing approaches of problems such as the travelling salesman, such that when graphs could change dynamically, the approach could be performed incessantly and adapt to variations in real time.

Disadvantages include the fact that the approach is vulnerable to failing in the best fit solution as the ant colony optimization updates the pheromone on the basis of available best path.  Furthermore, as much as the approach can be used to solve specific problems, its convergence cannot be proven.

4. The pseudo code for SA is to remind you.  Explain when the condition ‘if (accept new solution)’ would be met in order to avoid local maxima as the temperature decreases, considering the following situations:

  • a) the new solution is better than the current position
  • b) the new solution is worse than the current position

begin procedure SA

generate initial solutions

set temperature, and cooling rate

while(termination criteria not meet)

{

generate new solutions

access new solutions

if (accept new solution)

{

update storage

decrease temperature

}

}

post-process results and output

end GA procedure

The simulated annealing algorithm adopts a temperature cooling technique. Where through a repeat process, temperature is decreased and storage updated to a point where temperature is the least possible. It offers an approach towards problem solving where not solutions that are not optimally accurate are chosen based on probability, then enhanced through a series of repeat processes up to a point where the best solution is obtained. The simulations are run almost infinitely to a point where the person running the simulation is satisfied that the best solution has been found

5. Performing a Multi-objective Optimization Using the Genetic Algorithm

For the GA, the authors state “it supports multi-objective optimization.”

The graph provides the plot for two objective functions of a multi-objective problem, where, objective1(x) = (x+2)2 – 10, and objective2(x) = (x-2)2 + 20, are on the x-axis.

Using only this graph, what optimization is indicated for our multi-objective fitness function on the x-axis.

From the two objectives, one has is minima at x = -2 while the other has it at x = +2. Nevertheless, in a multi-objective problem, x = -2, x = 2, therefore any solution within the range of -2 <= x <= 2 is deemed equally optimal. As such, there is no single solution to this multi-objective problem. The aim of multi-objective Genetic algorithm is to obtain a group of solutions within that range where all solutions are optimal.

  1. Comment briefly on the extract of a row from the table of results from the research paper. The TSP File used in the paper relates to a library of travelling salesman problems (TSP) (TSBLIB archived at University of Heidelberg).

Table: Comparison between ACO, GA and SA for Solving Standard TSP Instances.

TSP FileNo. of CitiesACOGASA
BestWorstAverageBestWorstAverageBestWorstAverage
           
city5151529.15578.12558.04441.03456.27448.561352.511456.921314.16
           

From the results, it is evident that ACO and GA produce almost similar results. The GA seems to be the most effective by providing the most possible shortest lengths though not so much deviation from the ACO approach. The SA approach provides the longest lengths approximately three times that provided by the GA approach. In this essence it is correct to say that the GA approach provides the best accuracies for the traveling salesman problem with the SA model being the least accurate.

2021-08-09