Q1: Game Playing and Search (LO2) – 70%

Santorini (default game but without deity powers and no limit on building pieces) is a two-player based game, played on a board of 5×5 squares and it is round based. Each player has two workers. At each round the player picks one of his workers to move to an adjacent spot (horizontally or vertically) and then must build to an adjacent spot from the one that he has moved to; building increases the height of a building by one level (initially all squares start with no buildings, i.e. height is zero); the maximum height of a building is 4 levels high. If a player cannot move one of his workers and then build then he loses the game.

Restrictions on movement: you may move down or stay at the same level, but you may not climb up by more than one level high, for example if the square you start has a level 1 high building, then you can move to an adjacent square with no building (height=0), with a level 1 or 2 height building, but not higher.

2nd restriction on movement: it is impossible to move to a height 4 building, or to a square that already has another worker.

Restriction on building: you may not build on a square that has a worker and you cannot increase a building past height 4.

A player wins immediately after moving to a building of height 3, or if the opponent loses because none of his workers can move or build.

You can find the rules of this game online, e.g. http://roxley.com/wp-content/uploads/2016/08/Santorini-Rulebook-Web-2016.08.14.pdf

Note that you will not use deity powers, and you will not have a limit on how many building pieces you have (so in theory you could build the whole board!)

Instructions for the Design and Implementation

You will be given code that models/plays the game. You must write the AI for the game.

• First, you should implement a greedy algorithm for playing the next move of the game. Implement this in the method that returns the next move of the computer. The hardest part of this process is to implement also an appropriate heuristic function for evaluating board positions. (15%)
• Then extend your previous design by implementing the min max algorithm. You should use a different class in order to preserve both the min-man and greedy methods. (15%)
• Test your two AIs (greedy vs minmax) against each other and report on what you observe; please remember to run several runs in your test as the game includes randomness. For full points not only report on what the scores were, but also give intuition regarding what you observe and which AI outperforms the other. (10%)
• You can also try implement further improvements like using alpha-beta cutoffs (10%). In fact in part c you may include a-b minmax in you comparison.
• Finally, the last 20% of your grade will depend on your code’s performance in the class tournament. You should aim to create a good heuristic (in part a) and implement the most efficient algorithm (e.g. a-b minmax – part d) in order to outperform your opponents.

For full points in each part a-e you need to describe in your report what you implemented and a short evaluation of your efforts (part c will include this for parts a and b potentially, or you can have a different section).

NOTE: IT IS REQUIRED TO PROVIDE A JAR FILE OF YOUR CODE IN ORDER TO PARTICIPATE IN THE CLASS TOURNAMENT – THIS SHOULD HAVE SELECTED THE BEST ALGORITHM THAT YOU WANT TO PARTICIPATE IN THE TOURNAMENT WITH, EVEN THOUGH ALL CLASSES SHOULD BE INCLUDED IN YOUR CODE.