CS-E4800 Tournament Solution

Welcome to the "CS-E4800 Tournament"!




In this tournament, we will develop an agent to play the Konquest game.







Konquest

^^^^^^^^

This game is based on the Konquest game in KDE/Ubuntu. The game starts with some

planets scattered in space and two players. Each planet can produce some ships.

Using ships, players can attack other planets to conquer them. The goal is to

build a unified interstellar empire by eliminating the other player.




In the beginning, each player owns one planet. The other planets are neutral.

A planet can be described by the following properties:

* Name

* Owner: its owner, or it might be neutral if it belongs to nobody

* Position: its position in 2D space

* Ships: number of ships currently located on the planet

* Capacity: maximum number of ships that can be stationed on the planet

* Production: the rate of producing ship




In each turn, players can send some ships from one of their planets to any

other planet. The source planet should be owned by the current player, and it

must contain at least the specified number of ships in the order. Depending on

the distance between the source and the destination it takes some turns for the

fleet to reach the destination. The fleet size can be 2, 4, or 8 ships. At the

time of arrival, if the destination and the fleet are owned by the same

player, then the fleet reinforces the planet. Otherwise, it attacks the

destination. The kill rate in an attack is 70 percent. For example, if a fleet

with 2 ships attacks some planet, it can destroy 1.4 ships of the defender. If

the attacker defeats the defender, the ownership of the planet will change to

the owner.




Players have a specified amount of time to make a decision (e.g., 5 seconds).

This time limit may be varied at different stages of the game. As it would be 

difficult to adjust to any given time-bound, each player can generate a sequence

of increasing good actions in each turn, and the last action within the time

limit will be considered as the chosen action for that turn. If a player does

not choose any action within the time limit or chooses an invalid move, a random

action will be selected for the player. When all players make their decisions,

the simulation for that turn begins in the following order:

1. fleets depart from their source planets

2. planets produce new ships based on their production rate

3. If there is any combat, it begins after the production.




Ultimately, the game ends when:

1. A player loses all of its planets and ships to the winner of the game

2. Both players can survive for 200 turns; in this case, the winner is the

player who has the most ships in the game. If they have the same amount

of ships, the game ends with a draw.







This game is a modified version of the Konquest game in KDE/Ubuntu. You can

play the original version from here:

* https://apps.kde.org/konquest/







Requirements

^^^^^^^^^^^^

To run this program, we need to install `Pillow==9.4.0` and `numpy==1.24.2`.

You can install these dependencies by using the following command:

`pip3 install -r requirements.txt`




NOTE: We use `python3.9` for the tournament (more precisely, we disable the

visualization and use `pypy` compatible with `python3.9` to improve the

performance).







Instructions

^^^^^^^^^^^^

0. (Optional) Watch the game to learn and understand its rules.

You can watch the game by running the following command:

`python3 main.py`

You can compare the performance of different agents, by choosing them as the

players. To specify the type of players, you can modify the `players`

variable in the `main.py`.




1. Copy `agent-template.py` to `agent.py`.




2. Read and understand the `agent.py`.




3. Take a brief look at the following agents:

3.1. the `RandomAgent` in `random_agent.py`,

3.2. the `MarkovAgent` in `markov_agent.py`,

3.3. the `MinimaxAgent` in `minimax_agent.py`,

3.4. the `IterativeDeepening` in `iterative_deepening.py`, and,

3.5. the `IDMinimaxAgent` in `id_minimax_agent.py`.




4. Complete the `info` method of the `Agent` class




5. Complete the `decide` method of the `Agent` class by developing an algorithm

to overcome all opponents. You are free to choose any kind of game-playing 

agent to implement. Some obvious approaches are the following:

5.1 Implement alpha-beta (and investigate its potential for searching deeper

than what is possible with Minimax). Also, the order in which the actions

are tried in a given node impacts the effectiveness of alpha-beta: you could

investigate different ways of ordering the actions/successor states.

5.2 Try out better heuristics.

5.3 You could try out more advanced Monte Carlo search methods; however, we do

not know whether MCTS is competitive because of the high cost of the full

gameplay.

5.4 You could, of course, try something completely different if you are willing to

invest more time.







Simulation

^^^^^^^^^^

For simulating the game, you can use the `main.py` script. Just import your agent

and `play` the game with an instance of your agent.







GL HF :)