COMPUTATIONAL-INTELLIGENCE

Labs and exercises from the course Computational Intelligence:

• Traveling Salesman Problem
• Connect 4
• Tic Tac Toe
• Ant Colony Optimization

Traveling Salesman Problem

The file tsp.py contains a genetic algorithm for the solution of the traveling salesman problem in Python.

Algorithm

The genetic algorithm implemented has the following characteristics:

• parents are selected with a tournament of size 2 (pick the best among 2 randomly selected individuals)
• the offspring is generated by applying crossing over on the parents' genomes and then mutations
• the crossover type is randomly selected among different types: cycle crossover, partially mapped crossover, inver over
• the mutation type is randomly selected among different types: swap mutation, inversion mutation, scramble mutation, insert mutation
• the algorithm is terminated when the best solution is steady for a specified number of generations

Connect 4

The file connect_four.py contains an algorithm playing Connect-4.

Algorithm

The algorithm consists of a Minimax search with limited depth and alpha-beta pruning. Possible moves are represented by a tree, and all nodes of the tree are expanded until a depth limit is reached. Then, the value of a node is estimated through a Monte Carlo evaluation (average the results of a specified number of random simulations starting from that node), and the node with the highest value is selected. Two pruning approaches are also implemented:

• alpha-beta pruning: when the value of a node is surely worse than the value of a previously evaluated node, the expansion of that node is stopped
• when a player finds a move that will lead to a sure win (not necessarily with the lowest number of moves), the search is stopped

Data structure

Initially, the playing board is represented using a numpy array. An empty cell contains a 0, the maximizing player places 1s and the minimizing player places -1s in the board. However, this structure is not efficient and slows down the search. Therefore, a more optimized representation has been implemented, inspired by this article (which provides a more detailed description of the representation). In particular, the board is represented as a sequence of bits that are then converted to integer numbers. Two variables are used:

• mask: empty cells are 0, full cells are 1
• position: cells occupied by the player currently playing are 1, the others are 0 (note that the position of the stones of the other player can be obtained with mask XOR position).

In this way, operations on the board such as checking if a player has won, adding a cell etc. can be performed using bit-wise operations which are very efficient.

Modalities

The program allows to play agains the algorithm or to have two instances of the algorithm playing against each other, by setting the appropriate parameters. For the playing algorithm, it is possible to specify the following parameters:

• depth: depth of the MinMax algorithm
• num_samples: number of simulations performed by the Monte Carlo evaluation to provide the value of a node

Increasing these values leads to better players, but the time required for each move increases. A reasonable setting (around 10 seconds for the first moves) is depth = 4 and num_samples = 100.

Tic Tac Toe

The file tic_tac_toe.py contains a reinforcement learning algorithm to play tic tac toe.

Algorithm

The reinforcement learning agent is trained against a random player. At each training step:

• the action which brings to the state with the highest value is performed
• the value of the previous state is updated

Ant Colony Optimization

The file ant_colony_optimization.py contains an implementation of the ant colony optimization algorithm for the Traveling Salesman Problem. The algorithm is inspired by https://github.com/johnberroa/Ant-Colony-Optimization.