This tutorial uses a genetic algorithm (GA) for optimizing the 8 Queen Puzzle. Starting from an initial state of the puzzle where some queens may be attacking each other, the goal is to evolve such a state using GA to find a state in which no 2 queens are attacking each other.
Optimization is a crucial part of developing any machine learning (ML) application. Despite being simple, GA proves that it’s a powerful technique for solving different types of ML problems. One of the areas that tests this optimization technique is game solving.
Given a game with a bit of complex strategy and a distinct goal (reaching a state in which no 2 queens are attacking each other in the 8 Queen Puzzle), is the technique able to reach this goal? GA is a meta-heuristic optimization technique used for solving hard problems. We can easily tweak many parameters in GA, which makes it flexible and customizable to various problems. Let’s see what the GA can do with such a puzzle.
The GitHub project of this tutorial is available here. In order to run the project, Kivy must be installed. You can read about its installation here, according to the platform used [Windows, Linux, OS X].
You can also read about Kivy in these previous tutorials:
- Running NumPy in Android Devices using the Kivy Python Framework
- Image Classification for Android Devices Using NumPy and Kivy
The tutorial starts by giving a brief review of the puzzle and then goes through discussing the project. The points covered in this tutorial are as follows:
- 8 Queen Puzzle Review
- Building the 8×8 Board using Kivy
- Adding Widgets to Control the Project
- Initializing the Population
- Visualizing the Best Solution with a Population
- Optimization using GA
- Running the Project
8 Queen Puzzle Review
In chess, there is an 8×8 board in which each player starts with 6 unique pieces, as given in the next figure. The pieces names from right to left are king, queen, bishop, knight, rook, and pawn. There are only 1 king and 1 queen but some pieces appear more than once. There are 2 bishops, 2 knights, 2 rooks, and 8 pawns. As a result, there’s a total of 1+1+2+2+2+8=16 pieces for a single player. Given 2 players, there will be a total of 32 pieces on the board. This is for regular chess.
Each piece has a path to move through. Because this tutorial focuses on a single piece (the queen), let’s look at how it can move. The queen moves vertically, horizontally, and diagonally. There is no limit in the number of squares it moves. If a queen is located at the bottom right corner, it can move diagonally directly to the top left corner, as long as there is no enemy in its path. This also happens vertically and horizontally. The next figure gives the possible paths in which the queen can move.
A standard chess game includes 8 unique pieces placed on the 8×8 board. In terms of the 8 queen puzzle, the 8×8 board will just include a single unique piece which is, of course, the queen. There are 8 such pieces distributed on the board.
In order to solve the puzzle, no 2 queens are to attack each other. In other words, no 2 queens are on the same row, column, and diagonal. The next figure gives a possible solution to this puzzle. This project assumes that no 2 queens are in the same row. As a result, we are sure that no 2 queens will attack each other horizontally. This leaves us with the 2 other directions of attack (vertical and diagonal).
Building the 8×8 Board using Kivy
This part of the tutorial builds the puzzle. Later, we’ll apply the GA to solve it. The first step towards building the puzzle is to create the 8×8 board. Kivy is used for this purpose. As a start, the following code builds a simple Kivy application in which a new class named BuzzleApp is created, which extends the App class in the kivy.app module.
import kivy.app
import kivy.uix.gridlayout
import kivy.uix.button
class BuzzleApp(kivy.app.App):
def build(self):
gridLayout = kivy.uix.gridlayout.GridLayout()
button = kivy.uix.button.Button(text="Button")
gridLayout.add_widget(button )
return gridLayout
buzzleApp = BuzzleApp()
buzzleApp.run()
The place to define the user interface (UI) of the app is inside the build() method. Within it, a GridLayout is created in which a single Button widget is added. The GridLayout is the root widget of the application. The next figure shows the result after running this application.
The previous application just includes a single Button widget. The puzzle requires an 8×8 board. This board will be created as a matrix of 8×8 Button widgets. So rather than adding just a single Button widget within the GridLayout, 8×8=64 widgets will be added within it.
The reason for using the GridLayout is that it arranges the widgets into a matrix, which serves our purpose. We eventually need an 8×8 matrix. As widgets are added into the GridLayout, they’ll be automatically arranged into a matrix. The next code uses the GridLayout for building an 8×8 matrix of Button widgets.
The first line within the build() method creates the GridLayout (as a reminder, the root widget). It uses the rows argument for specifying that the number of rows in the grid is 8. This arranges all added widgets within the layout into 8 rows, and the number of columns is deduced automatically. It adds widgets row by row. When 8 widgets are added [that is where the rows limit is reached], a new column is created in which the other 8 widgets could be added, each in a single row. The process continues until all widgets are added.
import kivy.app
import kivy.uix.gridlayout
import kivy.uix.boxlayout
import kivy.uix.button
import kivy.uix.textinput
import kivy.uix.label
import numpy
class BuzzleApp(kivy.app.App):
def build(self):
gridLayout = kivy.uix.gridlayout.GridLayout(rows=8)
# Preparing the 8x8 board.
self.all_widgets = numpy.zeros(shape=(8,8), dtype="O")
for row_idx in range(self.all_widgets.shape[0]):
for col_idx in range(self.all_widgets.shape[1]):
self.all_widgets[row_idx, col_idx] = kivy.uix.button.Button(text=str(row_idx)+", "+str(col_idx), font_size=25)
gridLayout.add_widget(self.all_widgets[row_idx, col_idx])
return gridLayout
buzzleApp = BuzzleApp()
buzzleApp.run()
all_widgets is a NumPy array of objects that holds all Button widgets so we can easily reference them later. The argument dtype is set to “O” to reflect that it’s an array of objects, not numbers. The Button widgets are created inside 2 for loops in order to build the 8×8 board. The buttons are firstly added into this variable and then added to the GridLayout.
The variables created within the build() method will not be accessed outside it. In order to be able to access the all_widgets variable outside this method, the variable name is prepended by the word self to associate this variable to the current object. By doing this, the variable can be accessed outside this method.
After running the above code, the result is given in the next figure. The text of each Button reflects its row and column indices. By doing this, the 8×8 board is successfully created, but it’s currently empty because the 8 queens haven’t been added yet.
Note that the buttons of the 8×8 grid will not be handled. They are only available for visualizing the locations of the 8 queens. As an extension, you might specify the locations of the queens by pressing the buttons.
Adding Widgets to Control the Project
We’ll need to modify the previous application in order to add other widgets for user control. For example, the user can place the queens on the UI and start optimization using GA. Before discussing the code, the interface of the next application is given in the following figure.
The bottom part of the window has 3 Button widgets, 3 TextInput widgets, and 1 Label widget. From left to right, the description of the 3 Button widgets is as follows:
- The Initial Population button creates the initial population of the GA.
- The Show Best Solution button shows the best solution in the last generation the GA stopped at and visualizes it on the UI.
- The Start GA button starts the GA iterations/generations.
Regarding the 3 TextInput widgets, they accept the values of some parameters for the GA. The leftmost one accepts the number of solutions within the population, which is set by default to 8. The next TextInput widget accepts the number of generations, which is set to 10,000 by default. The rightmost TextInput widget accepts the number of genes to change their values randomly within the mutation operation. It is set to 5 by default.
The Label widget simply prints informational messages to the user. For example, it prints the number of attacking queens when the user presses the Show Best Solution button.
All of the 7 widgets discussed above are added to the application’s widget tree, as shown in the following the code. In the previous application, the root widget was the GridLayout. Now, it’s the BoxLayou. This BoxLayout has 2 layouts as children. The first one is the GridLayout previously created. The second one is a new BoxLayout, which groups all 7 widgets previously discussed. The variable boxLayout_buttons represents such a new BoxLayout. The arguments size_hint_x and size_hint_y are used for managing the space covered by the widgets on the application UI.
Using the Config object, the application window size is set to 1,000×600. This makes room for all widgets to completely appear.
import kivy.app
import kivy.uix.gridlayout
import kivy.uix.boxlayout
import kivy.uix.button
import kivy.uix.textinput
import kivy.uix.label
import numpy
from kivy.config import Config
class BuzzleApp(kivy.app.App):
def build(self):
boxLayout = kivy.uix.boxlayout.BoxLayout(orientation="vertical")
gridLayout = kivy.uix.gridlayout.GridLayout(rows=8, size_hint_y=9)
boxLayout_buttons = kivy.uix.boxlayout.BoxLayout(orientation="horizontal")
boxLayout.add_widget(gridLayout)
boxLayout.add_widget(boxLayout_buttons)
# Preparing the 8x8 board.
self.all_widgets = numpy.zeros(shape=(8,8), dtype="O")
for row_idx in range(self.all_widgets.shape[0]):
for col_idx in range(self.all_widgets.shape[1]):
self.all_widgets[row_idx, col_idx] = kivy.uix.button.Button(text=str(row_idx)+", "+str(col_idx), font_size=25)
self.all_widgets[row_idx, col_idx].markup = True
gridLayout.add_widget(self.all_widgets[row_idx, col_idx])
# Preparing buttons inside the child BoxLayout.
initial_button = kivy.uix.button.Button(text="Initial Population", font_size=15, size_hint_x=2)
ga_solution_button = kivy.uix.button.Button(text="Show Best Solution", font_size=15, size_hint_x=2)
start_ga_button = kivy.uix.button.Button(text="Start GA", font_size=15, size_hint_x=2)
self.num_solutions_TextInput = kivy.uix.textinput.TextInput(text="8", font_size=20, size_hint_x=1)
self.num_generations_TextInput = kivy.uix.textinput.TextInput(text="10000", font_size=20, size_hint_x=1)
self.num_mutations_TextInput = kivy.uix.textinput.TextInput(text="5", font_size=20, size_hint_x=1)
self.num_attacks_Label = kivy.uix.label.Label(text="# Attacks/Best Solution", font_size=15, size_hint_x=2)
boxLayout_buttons.add_widget(initial_button)
boxLayout_buttons.add_widget(ga_solution_button)
boxLayout_buttons.add_widget(start_ga_button)
boxLayout_buttons.add_widget(self.num_solutions_TextInput)
boxLayout_buttons.add_widget(self.num_generations_TextInput)
boxLayout_buttons.add_widget(self.num_mutations_TextInput)
boxLayout_buttons.add_widget(self.num_attacks_Label)
return boxLayout
Config.set('graphics', 'width', '1000')
Config.set('graphics', 'height', '600')
buzzleApp = BuzzleApp()
buzzleApp.run()
Initializing the Population
The 3 previously added buttons at the end of the application UI are not handled yet. Let’s start handling the first button, which initializes the population. The button is handled by binding a callback method to the press event. According to the next line, the callback method initialize_population() will be called when the button is pressed.
The previous application is extended by adding the implementation of such a method as given in the following code. The first line within such a method fetches the number of solutions from the num_solutions TextInput widget.
Each time the initialize_population() method is called, the text of the 8 buttons at which the 8 queens exist changes to the word “Queen”. The next line calls a method named reset_board_text(). The purpose of this method is to reset the text of all buttons on the board each time the initial_button button is pressed.
The locations of the 8 queens are selected randomly using the numpy.random.rand() method. It returns a 1D vector of length 8, where each value refers to the column index of each queen. This vector represents a GA solution to the problem.
The population is stored into the population_1D_vector NumPy array. Its shape is set to (self.num_solutions, 8), which creates an array with the number of rows equal to the number of solutions. And each solution consists of 8 genes (values), where each value represents the column index of a queen.
The row indices of the queens are known implicitly, as the first queen will be located in the first row, the second queen in the second row, and so on. Assuming that the returned vector of the numpy.random.rand() method is [3, 6, 4, 2, 2, 4, 0, 2], then the first queen is located at (0, 3)—first row and the forth column. The second queen is located at (1, 6)—second row and the seventh column, and so on. One possible initial population is given below. The population is saved into the population_1D_vector variable.
import kivy.app
import kivy.uix.gridlayout
import kivy.uix.boxlayout
import kivy.uix.button
import kivy.uix.textinput
import kivy.uix.label
import numpy
from kivy.config import Config
class BuzzleApp(kivy.app.App):
pop_created = 0 # 0 means a population is not yet created.
def initialize_population(self, *args):
self.num_solutions = numpy.uint8(self.num_solutions_TextInput.text)
self.reset_board_text()
self.population_1D_vector = numpy.zeros(shape=(self.num_solutions,8)) # Each solution is represented as a row in this array. If there are 5 rows, then there are 5 solutions.
# Creating the initial population RANDOMLY as a set of 1D vectors.
for solution_idx in range(self.num_solutions):
initial_queens_y_indices = numpy.random.rand(8) * 8
initial_queens_y_indices = initial_queens_y_indices.astype(numpy.uint8)
self.population_1D_vector[solution_idx, :] = initial_queens_y_indices
self.vector_to_matrix()
self.pop_created = 1 # indicates that the initial population is created in order to enable drawing solutions on GUI.
self.num_attacks_Label.text = "Initial Population Created."
def vector_to_matrix(self):
# Converts the 1D vector solutions into a 2D matrix solutions representing the board, where 1 means a queen exists. The matrix form of the solutions makes calculating the fitness value much easier.
self.population = numpy.zeros(shape=(self.num_solutions, 8, 8))
solution_idx = 0
for current_solution in self.population_1D_vector:
current_solution = numpy.uint8(current_solution)
row_idx = 0
for col_idx in current_solution:
self.population[solution_idx, row_idx, col_idx] = 1
row_idx = row_idx + 1
# print(self.population[solution_idx, :])
solution_idx = solution_idx + 1
def reset_board_text(self):
# Reset board on GUI.
for row_idx in range(self.all_widgets.shape[0]):
for col_idx in range(self.all_widgets.shape[1]):
self.all_widgets[row_idx, col_idx].text = "[color=ffffff]" + str(row_idx) + ", " + str(col_idx) + "[/color]"
with self.all_widgets[row_idx, col_idx].canvas.before:
kivy.graphics.Color(0, 0, 0, 1) # green; colors range from 0-1 not 0-255
self.rect = kivy.graphics.Rectangle(size=self.all_widgets[row_idx, col_idx].size,
pos=self.all_widgets[row_idx, col_idx].pos)
def build(self):
boxLayout = kivy.uix.boxlayout.BoxLayout(orientation="vertical")
gridLayout = kivy.uix.gridlayout.GridLayout(rows=8, size_hint_y=9)
boxLayout_buttons = kivy.uix.boxlayout.BoxLayout(orientation="horizontal")
boxLayout.add_widget(gridLayout)
boxLayout.add_widget(boxLayout_buttons)
# Preparing the 8x8 board.
self.all_widgets = numpy.zeros(shape=(8,8), dtype="O")
for row_idx in range(self.all_widgets.shape[0]):
for col_idx in range(self.all_widgets.shape[1]):
self.all_widgets[row_idx, col_idx] = kivy.uix.button.Button(text=str(row_idx)+", "+str(col_idx), font_size=25)
self.all_widgets[row_idx, col_idx].markup = True
gridLayout.add_widget(self.all_widgets[row_idx, col_idx])
# Preparing buttons inside the child BoxLayout.
initial_button = kivy.uix.button.Button(text="Initial Population", font_size=15, size_hint_x=2)
initial_button.bind(on_press=self.initialize_population)
ga_solution_button = kivy.uix.button.Button(text="Show Best Solution", font_size=15, size_hint_x=2)
start_ga_button = kivy.uix.button.Button(text="Start GA", font_size=15, size_hint_x=2)
self.num_solutions_TextInput = kivy.uix.textinput.TextInput(text="8", font_size=20, size_hint_x=1)
self.num_generations_TextInput = kivy.uix.textinput.TextInput(text="10000", font_size=20, size_hint_x=1)
self.num_mutations_TextInput = kivy.uix.textinput.TextInput(text="5", font_size=20, size_hint_x=1)
self.num_attacks_Label = kivy.uix.label.Label(text="# Attacks/Best Solution", font_size=15, size_hint_x=2)
boxLayout_buttons.add_widget(initial_button)
boxLayout_buttons.add_widget(ga_solution_button)
boxLayout_buttons.add_widget(start_ga_button)
boxLayout_buttons.add_widget(self.num_solutions_TextInput)
boxLayout_buttons.add_widget(self.num_generations_TextInput)
boxLayout_buttons.add_widget(self.num_mutations_TextInput)
boxLayout_buttons.add_widget(self.num_attacks_Label)
return boxLayout
Config.set('graphics', 'width', '1000')
Config.set('graphics', 'height', '600')
buzzleApp = BuzzleApp()
buzzleApp.run()
After building the population where each solution is represented as a 1D vector, the next step is to convert the solution from being a 1D vector to a 2D matrix using the vector_to_matrix() method. The reason for keeping 2 representations of each solution is that there’s an advantage for each of them. It’s much easier to build the population when each solution is a 1D vector. Also, it’s much easier to calculate the fitness value of each solution when it’s represented as a 2D matrix.
The vector_to_matrix() method is simple. It starts by creating a 2D NumPy array of zeros. According to the column indices of the 8 queens, 8 zeros are changed to 1, where each row has only a single value 1. The 2D representation of the second 1D vector in the previous population is given below. The 2D matrix is saved into the population variable. Remember that the 1D representation is saved into the population_1D_vector variable.
Because the GA can only start after an initial population is created, the class variable pop_created is changed from 0 to 1. This indicates that the GA is ready to start because an initial population has been created. At this point, The text of the num_attacks_Label Label widget changes to “Initial Population Created”.
Visualizing the Best Solution with a Population
By generating the initial population and converting it from 1D to 2D, the action of the initial_button is completed. Let’s move to the next button, which is ga_solution_button. This button has 2 main jobs. The first one is to find the best solution. The second one is visualizing this solution on the UI.
Its action is handled by binding the callback method update_board_UI() to it, according to the line below:
The code of the modified application after implementing this method is given below. The first line in the update_board_UI() method is checking whether a population exists or not.
If the value of the variable pop_created isn’t 0, then a population exists. If it’s 0, then nothing exists, and thus the method returns. If a population exists, then the board UI is reset by calling the reset_board_text() method. This makes the board ready to visualize the best solution.
import kivy.app
import kivy.uix.gridlayout
import kivy.uix.boxlayout
import kivy.uix.button
import kivy.uix.textinput
import kivy.uix.label
import numpy
from kivy.config import Config
class BuzzleApp(kivy.app.App):
pop_created = 0 # 0 means a population is not yet created.
def initialize_population(self, *args):
self.num_solutions = numpy.uint8(self.num_solutions_TextInput.text)
self.reset_board_text()
self.population_1D_vector = numpy.zeros(shape=(self.num_solutions,8)) # Each solution is represented as a row in this array. If there are 5 rows, then there are 5 solutions.
# Creating the initial population RANDOMLY as a set of 1D vectors.
for solution_idx in range(self.num_solutions):
initial_queens_y_indices = numpy.random.rand(8) * 8
initial_queens_y_indices = initial_queens_y_indices.astype(numpy.uint8)
self.population_1D_vector[solution_idx, :] = initial_queens_y_indices
self.vector_to_matrix()
self.pop_created = 1 # indicates that the initial population is created in order to enable drawing solutions on GUI.
self.num_attacks_Label.text = "Initial Population Created."
def vector_to_matrix(self):
# Converts the 1D vector solutions into a 2D matrix solutions representing the board, where 1 means a queen exists. The matrix form of the solutions makes calculating the fitness value much easier.
self.population = numpy.zeros(shape=(self.num_solutions, 8, 8))
solution_idx = 0
for current_solution in self.population_1D_vector:
current_solution = numpy.uint8(current_solution)
row_idx = 0
for col_idx in current_solution:
self.population[solution_idx, row_idx, col_idx] = 1
row_idx = row_idx + 1
solution_idx = solution_idx + 1
def reset_board_text(self):
# Reset board on GUI.
for row_idx in range(self.all_widgets.shape[0]):
for col_idx in range(self.all_widgets.shape[1]):
self.all_widgets[row_idx, col_idx].text = "[color=ffffff]" + str(row_idx) + ", " + str(
col_idx) + "[/color]"
with self.all_widgets[row_idx, col_idx].canvas.before:
kivy.graphics.Color(0, 0, 0, 1) # green; colors range from 0-1 not 0-255
self.rect = kivy.graphics.Rectangle(size=self.all_widgets[row_idx, col_idx].size,
pos=self.all_widgets[row_idx, col_idx].pos)
def update_board_UI(self, *args):
if (self.pop_created == 0):
print("No Population Created Yet. Create the initial Population by Pressing the "Initial Population" Button in Order to Call the initialize_population() Method At First.")
self.num_attacks_Label.text = "Press "Initial Population""
return
self.reset_board_text()
population_fitness, total_num_attacks = self.fitness(self.population)
max_fitness = numpy.max(population_fitness)
max_fitness_idx = numpy.where(population_fitness == max_fitness)[0][0]
best_solution = self.population[max_fitness_idx, :]
self.num_attacks_Label.text = "Max Fitness = " + str(numpy.round(max_fitness, 4)) + "n# Attacks = " + str(
total_num_attacks[max_fitness_idx])
for row_idx in range(8):
for col_idx in range(8):
if (best_solution[row_idx, col_idx] == 1):
self.all_widgets[row_idx, col_idx].text = "[color=22ff22]Queen[/color]"
with self.all_widgets[row_idx, col_idx].canvas.before:
kivy.graphics.Color(0, 1, 0, 1) # green; colors range from 0-1 not 0-255
self.rect = kivy.graphics.Rectangle(size=self.all_widgets[row_idx, col_idx].size,
pos=self.all_widgets[row_idx, col_idx].pos)
def fitness(self, population):
total_num_attacks_column = self.attacks_column(self.population)
total_num_attacks_diagonal = self.attacks_diagonal(self.population)
total_num_attacks = total_num_attacks_column + total_num_attacks_diagonal
# GA fitness is increasing (higher value is favorable) but the total number of attacks (total_num_attacks) is decreasing. An increasing fitness value could be created by dividing 1.0 by the number of attacks. For example, if the number of attacks is 5.0, then the fitness is 1.0/5.0=0.2
population_fitness = numpy.copy(
total_num_attacks) # Direct assignment makes both variables refer to the same array. Use numpy.copy() for creating a new independent copy.
for solution_idx in range(population.shape[0]):
if population_fitness[solution_idx] == 0:
population_fitness[solution_idx] = float("inf")
else:
population_fitness[solution_idx] = 1.0 / population_fitness[solution_idx]
return population_fitness, total_num_attacks
def attacks_diagonal(self, population):
# For a given queen, how many queens sharing the same column? This is how the fitness value is calculated.
total_num_attacks = numpy.zeros(population.shape[0]) # Number of attacks for all solutions (diagonal only).
for solution_idx in range(population.shape[0]):
ga_solution = population[solution_idx, :]
# Padding zeros around the solution board for being able to index the boundaries (leftmost/rightmost columns & top/bottom rows). # This is by adding 2 rows (1 at the top and another at the bottom) and adding 2 columns (1 left and another right).
temp = numpy.zeros(shape=(10, 10))
# Copying the solution board inside the badded array.
temp[1:9, 1:9] = ga_solution
# Returning the indices (rows and columns) of the 8 queeens.
row_indices, col_indices = numpy.where(ga_solution == 1)
# Adding 1 to the indices because the badded array is 1 row/column far from the original array.
row_indices = row_indices + 1
col_indices = col_indices + 1
total = 0 # total number of attacking pairs diagonally for each solution.
for element_idx in range(8):
x = row_indices[element_idx]
y = col_indices[element_idx]
mat_bottom_right = temp[x:, y:]
total = total + self.diagonal_attacks(mat_bottom_right)
mat_bottom_left = temp[x:, y:0:-1]
total = total + self.diagonal_attacks(mat_bottom_left)
mat_top_right = temp[x:0:-1, y:]
total = total + self.diagonal_attacks(mat_top_right)
mat_top_left = temp[x:0:-1, y:0:-1]
total = total + self.diagonal_attacks(mat_top_left)
# Dividing the total by 2 because it counts the solution as attacking itself diagonally.
total_num_attacks[solution_idx] = total_num_attacks[solution_idx] + total / 2
return total_num_attacks
def diagonal_attacks(self, mat):
if (mat.shape[0] < 2 or mat.shape[1] < 2):
# print("LESS than 2x2.")
return 0
num_attacks = mat.diagonal().sum() - 1
return num_attacks
def attacks_column(self, population):
# For a given queen, how many queens sharing the same coulmn? This is how the fitness value is calculated.
total_num_attacks = numpy.zeros(population.shape[0]) # Number of attacks for all solutions (column only).
for solution_idx in range(population.shape[0]):
ga_solution = population[solution_idx, :]
for queen_y_pos in range(8):
# Vertical
col_sum = numpy.sum(ga_solution[:, queen_y_pos])
if (col_sum == 0 or col_sum == 1):
col_sum = 0
else:
col_sum = col_sum - 1 # To avoid regarding a queen attacking itself.
total_num_attacks[solution_idx] = total_num_attacks[solution_idx] + col_sum
return total_num_attacks
def build(self):
boxLayout = kivy.uix.boxlayout.BoxLayout(orientation="vertical")
gridLayout = kivy.uix.gridlayout.GridLayout(rows=8, size_hint_y=9)
boxLayout_buttons = kivy.uix.boxlayout.BoxLayout(orientation="horizontal")
boxLayout.add_widget(gridLayout)
boxLayout.add_widget(boxLayout_buttons)
# Preparing the 8x8 board.
self.all_widgets = numpy.zeros(shape=(8, 8), dtype="O")
for row_idx in range(self.all_widgets.shape[0]):
for col_idx in range(self.all_widgets.shape[1]):
self.all_widgets[row_idx, col_idx] = kivy.uix.button.Button(text=str(row_idx) + ", " + str(col_idx),
font_size=25)
self.all_widgets[row_idx, col_idx].markup = True
gridLayout.add_widget(self.all_widgets[row_idx, col_idx])
# Preparing buttons inside the child BoxLayout.
initial_button = kivy.uix.button.Button(text="Initial Population", font_size=15, size_hint_x=2)
initial_button.bind(on_press=self.initialize_population)
ga_solution_button = kivy.uix.button.Button(text="Show Best Solution", font_size=15, size_hint_x=2)
ga_solution_button.bind(on_press=self.update_board_UI)
start_ga_button = kivy.uix.button.Button(text="Start GA", font_size=15, size_hint_x=2)
self.num_solutions_TextInput = kivy.uix.textinput.TextInput(text="8", font_size=20, size_hint_x=1)
self.num_generations_TextInput = kivy.uix.textinput.TextInput(text="10000", font_size=20, size_hint_x=1)
self.num_mutations_TextInput = kivy.uix.textinput.TextInput(text="5", font_size=20, size_hint_x=1)
self.num_attacks_Label = kivy.uix.label.Label(text="# Attacks/Best Solution", font_size=15, size_hint_x=2)
boxLayout_buttons.add_widget(initial_button)
boxLayout_buttons.add_widget(ga_solution_button)
boxLayout_buttons.add_widget(start_ga_button)
boxLayout_buttons.add_widget(self.num_solutions_TextInput)
boxLayout_buttons.add_widget(self.num_generations_TextInput)
boxLayout_buttons.add_widget(self.num_mutations_TextInput)
boxLayout_buttons.add_widget(self.num_attacks_Label)
return boxLayout
Config.set('graphics', 'width', '1000')
Config.set('graphics', 'height', '600')
buzzleApp = BuzzleApp()
buzzleApp.run()
In order to find the best solution within the population, the fitness value must be calculated. This is why the fitness() method is called. It accepts the population in 2D form and returns 2 1D vectors. One vector represents the fitness values and another represents the number of attacks. The fitness value is calculated based on the number of attacks according to the following equation:
It simply works by counting the number of vertical and diagonal attacks. Remember that no 2 queens exist in the same row, and thus the number of horizontal attacks is 0. The fitness values and the number of attacks of the population listed previously are given below:
According to the number of attacks, the least value is 5 for the fifth solution, which refers to a fitness value of 0.2. Because the fifth solution is the best one, it will be visualized on the UI as given in the next figure. The text color and the boundary box of the Button widgets that hold queens are changed to green. Note that the Label widget prints information about this solution (fitness value and number of attacks).
Optimization using GA
After discussing the second button, the next thing we need to discuss is the last button that starts the GA for optimizing the puzzle. The application is modified as given below to handle its press action using a callback method named start_ga().
This method evolves the initial solutions by applying crossover and mutation until reaching the optimal solution in which no 2 queens are attacking each other, or until reaching the maximum number of generations, set by default to 10,000.
There’s a module loaded named GA. It is simply a file named GA.py, which was originally implemented in GitHub project. It implements the GA operations (crossover and mutation).
For more information about GA, read my tutorial titled “Introduction to Optimization with Genetic Algorithm”.
For implementing the GA in Python, read my tutorial titled “Genetic Algorithm Implementation in Python”. The GA Python implementation is available in this GitHub project.
The number of generations is fetched from the num_generations_TextInput TextInput widget, while the number of mutations to be applied is fetched from the num_mutations_TextInput TextInput widget.
In order to save the progress of the GA through its generations, 2 files are saved, which are:
- best_outputs.npy: Holds the best solution for each generation.
- best_outputs_fitness.npy: Holds the fitness value of the best solution for each generation.
These files are saved once the best solution is reached. You can load these files later for information about the progress of the GA.
import kivy.app
import kivy.uix.gridlayout
import kivy.uix.boxlayout
import kivy.uix.button
import kivy.uix.textinput
import kivy.uix.label
import numpy
from kivy.config import Config
import GA
class BuzzleApp(kivy.app.App):
pop_created = 0 # 0 means a population is not yet created.
def start_ga(self, *args):
best_outputs = []
best_outputs_fitness = []
if (self.pop_created == 0):
print("No Population Created Yet. Create the initial Population by Pressing the "Initial Population" "
"Button in Order to Call the initialize_population() Method At First.")
self.num_attacks_Label.text = "Press "Initial Population""
return
num_generations = numpy.uint16(self.num_generations_TextInput.text)
num_parents_mating = numpy.uint8(self.num_solutions / 2)
for generation in range(num_generations):
print("n** Generation # = ", generation, " **n")
# Measuring the fitness of each chromosome in the population.
population_fitness, total_num_attacks = self.fitness(self.population)
max_fitness = numpy.max(population_fitness)
max_fitness_idx = numpy.where(population_fitness == max_fitness)[0][0]
print("nMax Fitness = ", max_fitness)
best_outputs_fitness.append(max_fitness)
best_outputs.append(self.population_1D_vector[max_fitness_idx, :])
# The best result in the current iteration.
if (max_fitness == float("inf")):
print("Best solution found")
self.num_attacks_Label.text = "Best Solution Found"
print("n1D Population : n", self.population_1D_vector)
print("n** Best soltuion IDX = ", max_fitness_idx, " **n")
best_outputs_fitness_array = numpy.array(best_outputs_fitness)
best_outputs_array = numpy.array(best_outputs)
numpy.save("best_outputs_fitness.npy", best_outputs_fitness)
numpy.save("best_outputs.npy", best_outputs)
print("n** Data Saved Successfully **n")
break
# Selecting the best parents in the population for mating.
parents = GA.select_mating_pool(self.population_1D_vector, population_fitness, num_parents_mating)
# Generating next generation using crossover.
offspring_crossover = GA.crossover(parents, offspring_size=(self.num_solutions - parents.shape[0], 8))
# Adding some variations to the offspring using mutation.
offspring_mutation = GA.mutation(offspring_crossover, num_mutations=numpy.uint8(self.num_mutations_TextInput.text))
# Creating the new population based on the parents and offspring.
self.population_1D_vector[0:parents.shape[0], :] = parents
self.population_1D_vector[parents.shape[0]:, :] = offspring_mutation
# Convert the 1D vector population into a 2D matrix form in order to calculate the fitness values of the new population.
self.vector_to_matrix()
def initialize_population(self, *args):
self.num_solutions = numpy.uint8(self.num_solutions_TextInput.text)
self.reset_board_text()
self.population_1D_vector = numpy.zeros(shape=(self.num_solutions,8)) # Each solution is represented as a row in this array. If there are 5 rows, then there are 5 solutions.
# Creating the initial population RANDOMLY as a set of 1D vectors.
for solution_idx in range(self.num_solutions):
initial_queens_y_indices = numpy.random.rand(8) * 8
initial_queens_y_indices = initial_queens_y_indices.astype(numpy.uint8)
self.population_1D_vector[solution_idx, :] = initial_queens_y_indices
self.vector_to_matrix()
self.pop_created = 1 # indicates that the initial population is created in order to enable drawing solutions on GUI.
self.num_attacks_Label.text = "Initial Population Created."
def vector_to_matrix(self):
# Converts the 1D vector solutions into a 2D matrix solutions representing the board, where 1 means a queen exists. The matrix form of the solutions makes calculating the fitness value much easier.
self.population = numpy.zeros(shape=(self.num_solutions, 8, 8))
solution_idx = 0
for current_solution in self.population_1D_vector:
current_solution = numpy.uint8(current_solution)
row_idx = 0
for col_idx in current_solution:
self.population[solution_idx, row_idx, col_idx] = 1
row_idx = row_idx + 1
solution_idx = solution_idx + 1
def reset_board_text(self):
# Reset board on GUI.
for row_idx in range(self.all_widgets.shape[0]):
for col_idx in range(self.all_widgets.shape[1]):
self.all_widgets[row_idx, col_idx].text = "[color=ffffff]" + str(row_idx) + ", " + str(
col_idx) + "[/color]"
with self.all_widgets[row_idx, col_idx].canvas.before:
kivy.graphics.Color(0, 0, 0, 1) # green; colors range from 0-1 not 0-255
self.rect = kivy.graphics.Rectangle(size=self.all_widgets[row_idx, col_idx].size,
pos=self.all_widgets[row_idx, col_idx].pos)
def update_board_UI(self, *args):
if (self.pop_created == 0):
print("No Population Created Yet. Create the initial Population by Pressing the "Initial Population" Button in Order to Call the initialize_population() Method At First.")
self.num_attacks_Label.text = "Press "Initial Population""
return
self.reset_board_text()
population_fitness, total_num_attacks = self.fitness(self.population)
print(population_fitness, total_num_attacks )
max_fitness = numpy.max(population_fitness)
max_fitness_idx = numpy.where(population_fitness == max_fitness)[0][0]
best_solution = self.population[max_fitness_idx, :]
self.num_attacks_Label.text = "Max Fitness = " + str(numpy.round(max_fitness, 4)) + "n# Attacks = " + str(
total_num_attacks[max_fitness_idx])
for row_idx in range(8):
for col_idx in range(8):
if (best_solution[row_idx, col_idx] == 1):
self.all_widgets[row_idx, col_idx].text = "[color=22ff22]Queen[/color]"
with self.all_widgets[row_idx, col_idx].canvas.before:
kivy.graphics.Color(0, 1, 0, 1) # green; colors range from 0-1 not 0-255
self.rect = kivy.graphics.Rectangle(size=self.all_widgets[row_idx, col_idx].size,
pos=self.all_widgets[row_idx, col_idx].pos)
def fitness(self, population):
total_num_attacks_column = self.attacks_column(self.population)
total_num_attacks_diagonal = self.attacks_diagonal(self.population)
total_num_attacks = total_num_attacks_column + total_num_attacks_diagonal
# GA fitness is increasing (higher value is favorable) but the total number of attacks (total_num_attacks) is decreasing. An increasing fitness value could be created by dividing 1.0 by the number of attacks. For example, if the number of attacks is 5.0, then the fitness is 1.0/5.0=0.2
population_fitness = numpy.copy(total_num_attacks) # Direct assignment makes both variables refer to the same array. Use numpy.copy() for creating a new independent copy.
for solution_idx in range(population.shape[0]):
if population_fitness[solution_idx] == 0:
population_fitness[solution_idx] = float("inf")
else:
population_fitness[solution_idx] = 1.0 / population_fitness[solution_idx]
return population_fitness, total_num_attacks
def attacks_diagonal(self, population):
# For a given queen, how many queens sharing the same coulmn? This is how the fitness value is calculated.
total_num_attacks = numpy.zeros(population.shape[0]) # Number of attacks for all solutions (diagonal only).
for solution_idx in range(population.shape[0]):
ga_solution = population[solution_idx, :]
# Badding zeros around the solution board for being able to index the boundaries (leftmost/rightmost coumns & top/bottom rows). # This is by adding 2 rows (1 at the top and another at the bottom) and adding 2 columns (1 left and another right).
temp = numpy.zeros(shape=(10, 10))
# Copying the solution board inside the badded array.
temp[1:9, 1:9] = ga_solution
# Returning the indices (rows and columns) of the 8 queeens.
row_indices, col_indices = numpy.where(ga_solution == 1)
# Adding 1 to the indices because the badded array is 1 row/column far from the original array.
row_indices = row_indices + 1
col_indices = col_indices + 1
total = 0 # total number of attacking pairs diagonally for each solution.
for element_idx in range(8):
x = row_indices[element_idx]
y = col_indices[element_idx]
mat_bottom_right = temp[x:, y:]
total = total + self.diagonal_attacks(mat_bottom_right)
mat_bottom_left = temp[x:, y:0:-1]
total = total + self.diagonal_attacks(mat_bottom_left)
mat_top_right = temp[x:0:-1, y:]
total = total + self.diagonal_attacks(mat_top_right)
mat_top_left = temp[x:0:-1, y:0:-1]
total = total + self.diagonal_attacks(mat_top_left)
# Dividing the total by 2 because it counts the solution as attacking itself diagonally.
total_num_attacks[solution_idx] = total_num_attacks[solution_idx] + total / 2
return total_num_attacks
def diagonal_attacks(self, mat):
if (mat.shape[0] < 2 or mat.shape[1] < 2):
# print("LESS than 2x2.")
return 0
num_attacks = mat.diagonal().sum() - 1
return num_attacks
def attacks_column(self, population):
# For a given queen, how many queens sharing the same coulmn? This is how the fitness value is calculated.
total_num_attacks = numpy.zeros(population.shape[0]) # Number of attacks for all solutions (column only).
for solution_idx in range(population.shape[0]):
ga_solution = population[solution_idx, :]
for queen_y_pos in range(8):
# Vertical
col_sum = numpy.sum(ga_solution[:, queen_y_pos])
if (col_sum == 0 or col_sum == 1):
col_sum = 0
else:
col_sum = col_sum - 1 # To avoid regarding a queen attacking itself.
total_num_attacks[solution_idx] = total_num_attacks[solution_idx] + col_sum
return total_num_attacks
def build(self):
boxLayout = kivy.uix.boxlayout.BoxLayout(orientation="vertical")
gridLayout = kivy.uix.gridlayout.GridLayout(rows=8, size_hint_y=9)
boxLayout_buttons = kivy.uix.boxlayout.BoxLayout(orientation="horizontal")
boxLayout.add_widget(gridLayout)
boxLayout.add_widget(boxLayout_buttons)
# Preparing the 8x8 board.
self.all_widgets = numpy.zeros(shape=(8, 8), dtype="O")
for row_idx in range(self.all_widgets.shape[0]):
for col_idx in range(self.all_widgets.shape[1]):
self.all_widgets[row_idx, col_idx] = kivy.uix.button.Button(text=str(row_idx) + ", " + str(col_idx),
font_size=25)
self.all_widgets[row_idx, col_idx].markup = True
gridLayout.add_widget(self.all_widgets[row_idx, col_idx])
# Preparing buttons inside the child BoxLayout.
initial_button = kivy.uix.button.Button(text="Initial Population", font_size=15, size_hint_x=2)
initial_button.bind(on_press=self.initialize_population)
ga_solution_button = kivy.uix.button.Button(text="Show Best Solution", font_size=15, size_hint_x=2)
ga_solution_button.bind(on_press=self.update_board_UI)
start_ga_button = kivy.uix.button.Button(text="Start GA", font_size=15, size_hint_x=2)
start_ga_button.bind(on_press=self.start_ga)
self.num_solutions_TextInput = kivy.uix.textinput.TextInput(text="8", font_size=20, size_hint_x=1)
self.num_generations_TextInput = kivy.uix.textinput.TextInput(text="10000", font_size=20, size_hint_x=1)
self.num_mutations_TextInput = kivy.uix.textinput.TextInput(text="5", font_size=20, size_hint_x=1)
self.num_attacks_Label = kivy.uix.label.Label(text="# Attacks/Best Solution", font_size=15, size_hint_x=2)
boxLayout_buttons.add_widget(initial_button)
boxLayout_buttons.add_widget(ga_solution_button)
boxLayout_buttons.add_widget(start_ga_button)
boxLayout_buttons.add_widget(self.num_solutions_TextInput)
boxLayout_buttons.add_widget(self.num_generations_TextInput)
boxLayout_buttons.add_widget(self.num_mutations_TextInput)
boxLayout_buttons.add_widget(self.num_attacks_Label)
return boxLayout
Config.set('graphics', 'width', '1000')
Config.set('graphics', 'height', '600')
buzzleApp = BuzzleApp()
buzzleApp.run()
Running the Project
The code for this project is available on GitHub. The project includes 2 Python files, which are:
- main.py
- GA.py
The sequence of steps essential to run the project and optimize the 8 queen puzzle using a GA is as follows:
- Run the main.py file.
- Press the Initial Population Button.
- Press the Start GA Button.
After pressing the Start GA button, the GA uses the initial population and evolves its solutions until reaching the best possible solution. After pressing it, the next figure shows one possible initial population, in which 6 out of 8 queens are attacking each other.
In the Label widget, there are 2 values. The first one is the fitness (0.1667) and the second is the number of attacks (6). The fitness value is calculated as 1.0/number of attacks. In this case, the fitness value is equal to 1.0/6.0 which is 0.1667.
The evolution of the GA for reaching the optimal solution in which 0 attacks exists is illustrated in the next figures:
5 Attacks
4 Attacks
3 Attacks
2 Attacks
1 Attack
0 Attacks (Optimal Solution)
It’s very important to note that the GA does not guarantee reaching the optimal solution each time it works. You can make changes in the number of solutions per population, the number of generations, or the number of mutations. Other than doing that, the initial population might also be another factor for not reaching the optimal solution for a given trial.
Comments 0 Responses