Skip to content

Project for the Computational Intelligence course 23/24 - Politecnico di Torino

License

Notifications You must be signed in to change notification settings

Vitabile/Quixo-project

Repository files navigation

Computational Intelligence Project - Quixo

Game description

Quixo is a game based on simple rules, but it is by no means simple.

In turn, each player chooses a cube and moves it according to the following rules. In no event can a player miss his/her turn.

Choosing and taking a cube

The player chooses and takes a blank cube, or one with his/her symbol on it, from the board’s periphery. In the first round, the players have no choice but to take a blank cube. You are not allowed to take a cube bearing your opponent’s symbol.

Changing the cube symbol

Whether the cube taken is blank or already bears the player’s symbol, it must always be replaced by a cube with the player’s symbol on the top face.

Replacing the cube

The player can choose at which end of the incomplete rows made when a cube is taken, the cube is to be replaced; he/she pushes this end to replace the cube. You can never replace the cube just played back in the position from which it was taken.

END OF GAME

The winner is the player to make and announce that he/she has made a horizontal, vertical or diagonal line with 5 cubes bearing his/her symbol. The player to make a line with his/her opponent’s symbol loses the game, even if he/she makes a line with his/her own symbol at the same time.

Players - Design Choices

Since during the semester we developed several agents based on the techniques explained in the lectures, we mainly focused our project on methods which we did not develop in the laboratories or in the additional material we proposed in our personal repositories.

Keeping this in mind, we decided to implement the following methods:

  • Human Player
  • MinMax
  • MinMax + Alpha-Beta pruning
  • Monte Carlo Reinforcement Learning (TD learning + Symmetries)
  • Monte Carlo Tree Search

Although Monte Carlo Tree Search is not a topic of the course, we included it because Quixo has a great branching factor value and we wanted an agent that could overcome this problem.

Space Optimization

Since the Quixo game has a huge amount of states, we focused our attention on optimizing the space required by our serialized agents. Before this new representation, the Monte Carlo RL player weighed more than a GB, while now its size is 57 KB.

Players Improvements

To improve the performance of the players we implemented the following improvements:

  • parallelization
  • hash tables
  • symmetries

Failed Attempts

We also tried to include in the project a Q-learning player, but we failed resoundingly due to the huge amount of state-action pairs to learn. For this reason, we removed it from the repository.

We tried to use the same agents implemented for the last laboratory, but we failed because the formulas we used were not sufficient to learn the return of rewards of the millions and millions of states in which Quixo can be found.
We performed several trials and after a consultation with Riccardo Cardona, we found that the formula he used for the project is quite efficient and effective.

Repository Structure

  • players: this directory contains the implemented agents
  • trained_agents: this directory contains the trained agents
  • utils: this directory contains files which are necessary for the agents to play and implement performance improvements
    • investigate_game.py: class which extends Game and it is used by our agents
    • symmetry.py: class which implements all the possible symmetries and it is used by our agents
  • project_summary.ipynb: notebook used to train agents and to show results

The serialized MinMax and MinMax + Alpha-Beta pruning players with a non-empty hash table can be found in the release section.

How to run

To run a specific module.py file, open the terminal and type the following command from the root of the project:

python -m folder.module

As an example, run the min_max.py file as follows:

python -m players.min_max

If you are using VS Code as editor, you can add

"terminal.integrated.env.[your os]": 
{
    "PYTHONPATH": "${workspaceFolder}"
}

to your settings and run the module directly using the button.

Resources

Authors

License

MIT License