====== Task 3: Gomoku and MCTS ======

===== The Game =====

Gomoku is a simple popular game played on a
square grid. Players alternate in placing their mark (x or o) on an empty
cell. The winner is the first player to get an unbroken row of //exactly// five marks
horizontally, vertically, or diagonally.

An example terminal state -- the winning trace is highlighted by uppercase
letters X:

<code>
.Xo.....
oXxx....
oXoo.x..
.Xo.....
.Xo.....
.....o..
..x.....
........
</code>


===== Your Task =====

Download {{:courses:zui:tasks:task3_mcts.zip}}. In ''student.py'', you should implement the following:

<code python>
class MCTSBot:
    def __init__(self, play_as: int, time_limit: float):
        self.play_as = play_as
        self.time_limit = time_limit * 0.9

    def play_action(self, board):
        # TODO: implement MCTS bot

        start_time = time.time()
        while (time.time() - start_time) < self.time_limit:
        	pass # do some thinking...

        return random.choice( list(board.get_actions()) )
</code>

Your task is to implement the MCTS algorithm to play the game with a time limit of 10 second per move. The size of the board will be 8x8. You are given an example implementation of a bot that makes random actions. If you exceed the allotted time, your bot will be terminated and evaluation will be unsuccessful.
===== Evaluation =====

Upload your solution (only ''student.py'') to
[[https://cw.felk.cvut.cz/brute/teacher/course/1335|Brute]], where it will be
evaluated automatically. The evaluation can take up to 15 minutes, so be patient.

Your bot will be tested against four predefined bots with varying difficulty. If it wins at least 4/6 matches against a particular bot, it is considered victorious and you are given 2.5 points. Good luck.