Project - Hex

Background

Hex is a connection game. The game can never end in a draw (tie), in other words, Hex is also a “determined game”.

Hex is a finite, perfect information game, and an abstract strategy game that belongs to the general category of connection games. Hex is a special case of the “node” version of the Shannon switching game.

As a product, Hex is a board game; it may also be played with paper and pencil.

John Nash was the first to prove Hayward and van Rijswijck [HvanRijswijck06] that Hex cannot end in a draw, a non-trivial result colloquially called the “Hex theorem.”

In 1976, Shimon Even and Robert Tarjan proved that determining whether a position in a game of generalized Hex played on arbitrary graphs is a winning position is PSPACE-complete Even and Tarjan [ET76].

Due to the simplicity of the rules and its computation hardness, Hex is a very popular adversarial game in Artificial Intelligence.

Objectives

The objective of this project is to make you work a research project that is interesting and fun (I hope).

You are not expected to produce the best algorithm for this game! However, you are expected to create a new algorithm based on what we saw during the lectures, the reading materials provided and your own research.

This will lead you to write a report similar to a research article detailing your algorithm and heuristics, the background that led you there (articles, etc.) and the results obtain compared to a common algorithm.

The code itself will not be marked. What matters at the end is the quality of your report and the relevance of your choices.

Even if the performance is not as good as other algorithms, if the theory behind your approach is good and the experiments well down, you can achieve the highest grade.

The report will be written in Latex (https://www.latex-project.org/), the language used to write and compile scientific articles.

Problem

A Hex game follows simple rules:

• Each player plays one after the other by placing a coloured hex on the board.

• The first to connect the two sides of his colour win.

• You cannot play on a player tile.

The following image is a game in which blue won:

Algorithms and Heuristics

First, you need to know what is an adversarial game. An adversarial game where two or more players plays against each other. These types of games are very hard to solve due to their combinatorial explosion.

To solve this issue, AI researcher came up with a search algorithm combined with a heuristic function. The search algorithm will explore the tree of the possibilities to evaluate what is the best move to execute. As the number of future possible moves is too large, the heuristic function will help to search only in relevant part of the tree.

Depending on the type of algorithm, the heuristic function can change a lot. Good heuristic functions are not trivial to find, it requires expert knowledge.

Regarding the Hex game, there are different approaches. To give you somewhere to start I will give you two common approaches:

• Minimax algorithm combined with a heuristic evaluating the quality of the move

• Approach based on pattern recognition.

Adversarial games will be covered more in depth during the term.

Implementation

You will be provided a simple Python framework. The GUI will allow you to launch two automated players.

You will need to create a new player by inheriting the class Player.

class Player:
"""
Class representing a player.
You need to inherit from this class.
"""
def __init__(self, size, player_number, adv_number):
    self.name = "Player"
    self._size = size
    self.player_number = player_number
    self.adv_number = adv_number

def step(self):
    """
    The function needs to return the coordinates of the next move of the player.
    It should call your algorithm. Don't forget to memorize your move.
    :return: Coordinates following the data structure: [x,y]
    """
    pass

def update(self, move_other_player):
    """
    The game will call this function with the move of the other player.
    :param move_player: Move of the other player in this format: [x, y]
    :return: Nothing
    """
    pass

The function step(self) is called by the program to get the next move of the player and this where you need to call your algorithm.

The function update(self, move_other_player) is called by the program to get the send to the player the move made by the opponent. This is where you update the state of the problem.

My only requirement regarding your algorithm is that you put it in the same file. You should not touch the other part of the code, as you will only submit your player file.

If you think necessary modifications to the code need to be made, you can create a pull request on GitHub and I will take it into account.

Warning

This is not a programming assignment! Producing and submitting a good code alone will not grant you a passing grade. However, your code needs to be clear, modular and easily understandable. If the code submitted does not respect these conditions, penalty can be applied. Finally, this is an individual work; thus you cannot use or share your code with other students.

Important

The code can be find here: GitHub.

Report

After running your experiments, you are required to write a report in Latex. Latex is free and open-source, but by default does not propose an editor. Some solutions exist like TexMaker (Software) or Overleaf (Web application).

The report needs to have the following structure:

• Introduction

  • State of the art

  • Your contribution

• Problem definition

  • Mathematical formulation of the problem

  • Algorithms used

  • Heuristics

• Experiments

• Results

• Conclusion

The problem definition is very important, it is not a programming project! You need to formulate the problem, your algorithm and the heuristic correctly, as it is done in class or in the material given.

You are highly encouraged to ask questions on the project regularly throughout the term to ensure that you are on the good path or obtain complementary information.

Submission

The submission of the assignment needs to be done on Moodle. I am expecting the following files:

• Your report in pdf.

• Your player file in python

Warning

It is your responsibility to submit the required files on Moodle before the deadline. Issues with Moodle are not valid excuses for late submission.

Grading Scheme

The assignment is graded based on the report submitted.

The report will be graded on the following points:

• The problem is correctly defined

• The quality of the experiments

  • Relevance of the experiments

  • Quantity of the experiments

  • Correctness of the protocol

• Results and Conclusion

Note

Points can be deduced if the code is not up to the standard specified before.

Bibliography

ET76

S. Even and R. E. Tarjan. A combinatorial problem which is complete in polynomial space. J. ACM, 23(4):710–719, October 1976. URL: https://doi.org/10.1145/321978.321989, doi:10.1145/321978.321989.

HvanRijswijck06

Ryan B. Hayward and Jack van Rijswijck. Hex and combinatorics. Discrete Mathematics, 306(19):2515–2528, 2006. Creation and Recreation: A Tribute to the Memory of Claude Berge. URL: https://www.sciencedirect.com/science/article/pii/S0012365X06003542, doi:https://doi.org/10.1016/j.disc.2006.01.029.