AAA-Advanced Analysis of Algorithms Solved

1       Introduction
The most famous AI challenge of the 20th century was to defeat humans in the game of chess. Beginning with Claude Shannon’s paper in 1950,[1] this goal was finally achieved in 1997, when IBM’s Deep Blue defeated world champion Garry Kasparov. To honour this accomplishment, we will be developing an AI agent that plays the board game known as Congo. This document will outline exactly how the game works, what the assignment will consist of, and how marks will be allocated. More documents will be sent out at a later stage to expand on the requirements of Section 3.

2        The Game of Congo
Congo is a variant of chess that was invented in the 80s. It contains elements of chess, checkers and shogi (also known as Japanese chess), but the main philosophy is the same: to capture your opponent’s most valuable piece. You can try out the game yourself here https://mindsports. nl/index.php/dagaz/882-congo and read more about it at https://mindsports.nl/index. php/the-pit/523-congo and https://en.wikipedia.org/wiki/Congo_(chess_variant). For ease of reference, we describe the rules below.

The game is played on a 7×7 board. In the descriptions below, rows are called ranks and columns are called files. The start state looks as follows:

 Z
 Z Z
 Z
po
pop
op
Z0
Z0Z
0Z
0Z
0Z0
Z0
Z0
Z0Z
0Z
PO
POP
OP
 Z
 Z Z
 Z
7

6

5

4

3

2

1

                                                           a        b        c        d        e         f        g

Figure 1: The starting position for White and Black. Initial positions: giraffes (a-file), monkeys (b-file), elephants (c- and e-files), lions (d-file), crocodiles (f-file), and zebras (g-file). Pawns fill each player’s second rank. Each player’s castles are highlighted in brown, and the river along the fourth rank is in blue.

Game dynamics
Congo consists of two players, Black and White, who take turns moving (no skipping of turns is allowed). White starts first. The aim of the game is to capture the opponent’s lion—the game is immediately over when one player’s lion has been captured. Players take turns making moves and potentially capturing their opponent’s pieces. If a player moves to a square that is occupied by an opposing piece, that piece is said to be captured and is removed from the board. In Congo, as in chess, a player is not allowed to capture their own pieces, so moving to a square occupied by one’s own piece is prohibited.

Pieces

Each side begins with a number of pieces of various types. These pieces are:

Lion: The lion moves and captures one square in any direction (including diagonally), but it may not leave its 3×3 castle (highlighted in brown in the diagrams). However, there is one exception to this rule: a lion is allowed to move in a straight or diagonal line across the river if it is able to immediately capture the opposing lion. If a player’s lion is captured, that player immediately loses the game. The diagram below shows the moves the white lion is able to make.

Z0
 Z0Z
0Z
0Z
pZ0
Z0
Z0
Z0Z
0Z
0Z0Z0Z0
 Z0Z0Z0Z

0Z0o0Z0

Z0Z0Z0Z
 7 Z0Z0Z0Z 7 6 0Z0Z0Z0 6 5 Z0Z0Z0Z 5 4 0Z0Z0Z0 4 3 Z0Z0Z0Z 3 2 0Z0o0Z0 2 1 Z0Z0Z0Z

1

                                                                                                                    a       b      c       d      e       f       g

            a       b       c       d      e       f       g
 
(a) In the current position, White’s lion on c3 can move to the squares marked by a red square or can capture Black’s pawn on d2 (red circle).
(b) Compared to the position on the left, the White lion on c3 can now also move across the river to capture the Black lion on e5 and win the game (red arrow)! The White lion could also potentially capture Black’s lion anywhere along the c-file.
Zebra: If you are familiar with chess, the zebra moves exactly as the chess knight. That is, it moves two squares vertically and one square horizontally, or two squares horizontally and one square vertically (with both forming the shape of an L). The zebra can jump over pieces to reach its destination.

 Z0Z0Z0Z 0Z0Z0Z0 opZ0Z Z
0ZpZ0Z0
OP
Z0Z
PZ
0Z
0Z 
Z0
Z0
 Z0Z
0Z
 7 Z0Z0Z0Z 7 6 0Z0Z0Z0     6 5 opZ0Z Z       5 4 0ZpZ0Z0     4 3 OPZ0ZPZ  3 2 0Z0Z Z0       2 1 Z0Z0Z0Z     1
                   a       b       c       d       e       f       g                                         a       b      c       d      e       f       g

(a) The White zebra on e2 can move to any (b) The Black zebra can move to any square square indicated by the arrows. It cannot move indicated by the arrows and can thus choose to c1, since that square is occupied by another to capture the White piece on f5. White piece. Note that the pawn on f3 does not prevent the zebra from jumping to f4 or g3.

Elephant: The elephant can move or capture one or two squares horizontally or vertically in any direction. If it moves two squares, this move is a jump. Therefore, if there is any piece in the way, it does not block the elephant from moving two squares.

  7 Z0Z0Z0Z 7 Z0Z0Z0Z 6 0Z0Z0Z0     6 0Z0Z0Z0 5 Z0Z0Z0Z     5 Z0Z0Z0Z 4 0ZpZ0Z0 4 0Z0Z Z0 3 OPZ0ZPZ     3 OPZ0ZPZ 2 0Z0Z Zp  2 0Z0Z0Zp 1 Z0Z0Z0Z     1 Z0Z0Z0Z
            a       b       c       d      e       f       g

(a) The White elephant on e2 can move to any of the squares marked by a red square, and it can capture the Black piece in g2 (circled in red). Note that it cannot move to d2 since another White piece occupies that square, but it can jump to c2 (and is not blocked by the piece on d2).
            a       b       c       d      e       f       g

(b) The White elephant on e3 can move to any of the squares marked by a red square. In addition, it can move one square forward to capture the Black piece on e4, (circled in red), or jump two steps to capture the piece on e5 (in this case, the piece on e4 would remain unaffected).
Giraffe: The giraffe can move one or two steps in any direction (orthogonally or diagonally), but can only make captures two squares away. If the giraffe moves two squares, the intermediate square is jumped.

Z0
 Z0Z
0Z
0Z
0Z0
Z0
Z0
Z0Z
0Z
0Z
 0Z0
 Z0
OP
 Z0Z
PZ
0Z
 0Z
o0
Z0
 Z0Z
0Z
 77 Z0Z0Z0Z 66 0Z0Z0Z0 55 Z0Z0Z0Z 44 0Z0Z0Z 33 OPZ0ZpZ 22 0Z0Z Zp 11 Z0Z0Z0Z
                                                                                                                    a       b      c       d      e       f       g

                   a       b       c       d       e       f       g

(b) The White giraffe on e2 can move to any

(a) The White giraffe on e2 can move to any of of the squares marked by a red square. It

the squares marked by a red square. Note that cannot move to or capture f3 since it is only

it can move to c2, g2 or g4 by jumping over the one square away, but it can jump two squares

intermediate pieces. However, it cannot move to capture the Black piece on g4 or g2 (red

to d2 (which is occupied by a White piece) and circles).

cannot capture the Black piece on f2, since it is only one square away.

Crocodile: The crocodile moves and captures one step in any direction (orthogonally or diagonally). It can also move and capture any number of steps in a straight line towards the river (including entering the river). Once in the river, the crocodile can additionally move and capture any number of steps along the river.

Z0
 Z0Z
0Z
0Z
0Z0
Z0
Z0
Z0Z
0Z
 0Z0Z0Z0
Z0Z0ZPZ

 0Z0ZpZ0 Z0Z0Z Z
 7 Z0Z0Z0Z 7 6 0Z0Z0Z0     6 5 Z0Z0Z0Z     5 4 0Z0Z0Z0   4 3 Z0Z0Z0Z     3 2 0Z0ZpZ0     2 1 Z0Z0Z Z 1
                   a       b       c       d       e       f       g

                                                                                                                    a       b      c       d      e       f       g

(a)    The White crocodile on f1 can move to any

(b)    A similar state to the one on the left. How-

square marked by a red square. This includes ever, the White pawn on f3 now blocks the

any square adjacent to f1, and any square along crocodile on f1 from entering the river (the

the file between the crocodile and the river, incrocodile cannot jump over it). It therefore

cluding entering the river. The crocodile can cannot capture the black piece at f4.

therefore choose to capture the Black piece at e2 or f4 (red circle).

 7 Z Z0Z0Z

6 0Z0Z0Z0

5 Z0Z0Z0Z

4 0Z0Z0Z0

3 Z0Z0Z0Z

2 0Z0Z0Z0

1 Z0Z0Z0Z

                                                                   a       b      c       d       e       f       g

(c) Once in the river, the crocodile can move any number of squares along it. The White crocodile on b4 can move to any of the squares marked by a red square and can also capture the black piece at f4 (circled in red).

Monkey: The monkey can move one step in any direction (orthogonally or diagonally), but cannot make a capture this way. It can also capture an opposing piece on an adjacent square (orthogonally or diagonally) by jumping over it to the vacant square immediately beyond (if the square is not empty, the capture cannot be made). If a capture is made, then multiple captures are permitted (but are not compulsory) with the same piece in the same turn! In a multi-capture move: a) successive jumps can be in different directions; b) a given piece may be jumped only once; c) a given square may be visited more than once; d) all pieces jumped are removed from play only after the entire multi-capture move has been completed.

 7 Z0Z0Z0Z 6 0Z0Z0Z0 5 Z ZpZ0Z 4 0Z0Z0Z0 3 Z0Z0Z0Z 2 0Z0Z0Z0 1 Z0Z0Z0Z
            a       b       c       d      e       f       g

(a) The White monkey on b5 can move to any of the squares marked by a red square. It cannot capture the Black piece on c5 since it must jump over it to do so, but the square it would jump to (d5) is occupied. It can, however, capture the Black piece on b4 by jumping over it to b3 (red arrow). At the end of the turn, the piece on b4 would be removed.

 7 Z0Z0Z0Z 6 0Z0Z0Z0 5 Z ZpZ0Z 4 0Z0Z Z0 3 Z0Z0Z0Z 2 0Z0Z0Z0 1 Z0Z0Z0Z
            a       b       c       d      e       f       g

(b) An example of a multi-capture move. The White monkey on b5 first jumps to b3, capturing the Black piece on b4. It then continues by jumping to d3, capturing the piece on c3. Finally, it jumps to f5, capturing the piece on e4. This ends the turn, at which point all the pieces are removed from the board. All jumps are indicated by red arrows.

Pawn: A pawn can move and capture one step straight or diagonally forward. (Black pawns move forward towards rank 1, while White pawns move forward towards the rank 7.) When past the river, it can move (but not capture) one or two steps straight backwards. However, this is not a jumping move, and so the pawn may not move backwards if there is a piece in its path.

If a pawn reaches the opposite side of the board, it is promoted to a superpawn. A superpawn has the abilities of a regular pawn, but can additionally move and capture one square sideways. It may now retreat one or two squares straight or diagonally backwards, and this ability no longer depends on its position with regard to the river. However, just like the regular pawn, it may not capture or jump over a piece when retreating.
 7 Z0Z0Z0Z 6 0Z0Z0o0 5 Z0Z0Z Z 4 0O0Z0Z0 3 Z0Z Z0Z 2 0Z0Z0Z0 1 Z0Z0Z0Z
            a       b       c       d      e       f       g

(a)                 In this position, neither pawn has managedto cross the river completely yet. The White pawn on b4 can therefore only advance onto any square indicated by a red square, while the Black pawn on f6 can only advance to any square indicated by a green square or capture the White piece on f5 (green circle).

 Z0Z Z0Z

0Z0Z0Z0

ZPZ0Z0Z
 0Z0Z0Z0
 Z0
Z Z
0Z
0Z
0Z0
Z0
Z0
Z0Z
0Z
7

6

5

4

3

2

1

            a       b       c       d      e       f       g

(b)                 The White pawn on b5 has crossed the riverand so now can retreat one or two squares straight backwards (indicated by red circles) in addition to advancing forward (red squares). The Black superpawn on e5 can move and capture forwards or sideways (green squares) and can retreat one or two squares straight or diagonally backwards (green circles). In the case of the superpawn, retreating can happen anywhere on the board. The superpawn cannot retreat to c7, since there is a piece on d6 blocking its path.

Other Game Features
The River: As you saw in the initial setup, the board has a river running across the middle of it! Any piece may move into the river, but if that piece does not leave the river on its next turn, it is said to have drowned. The piece may not have moved at all, or may have moved within the river, or even, in the monkey’s case, out of and back into the river. In all cases, the piece is removed from the board. The only piece this does not apply to is the crocodile, which cannot drown and can stay in the river forever!

Z0
 Z0Z
0Z
0Z
0Z0
Z0
Z0
Z0Z
0Z
0Z
0Z0
Z0
Z0
Z0Z
0Z
0Z
 0Z0
Z0
Z0
Z0Z
0Z
 7 Z0Z0Z0Z 6 0Z0Z0Z0 5 Z0Z0Z0Z 4 0Z Z0Z0 3 ZpZ Z0Z 2 0Z0Z0Z0 1 Z0Z0Z0Z
7

6

5

4

3

2

1

                   a       b       c       d       e       f       g

                                                                                                                    a       b      c       d      e       f       g

(a)    An example of drowning. The White mon-

(b)    The state of the board after the move ends.

key begins in the river on c4 and executes a

The three Black pieces that were jumped over

multi-capture move, jumping to a4, then c2 are removed from the board, but as the monkey

and finally e4, which leads it back into the landed back in the river, it too is removed.

river.

End of game:      The game ends when one of the lions is captured. If only two lions remain, the game is a draw. However, a lion and any piece will win against just a lion.