% !TEX program = xelatex

\documentclass{article}

\usepackage{chessboard}

\usepackage[LSBC4,T1]{fontenc}

\let\clipbox\relax

\usepackage{../styles/style}

\usepackage{../styles/langs}

\usepackage{disclaimer}

\usepackage{ulem}

%\usepackage{tipauni}

\tikzset

{%

  pics/piece/.style n args={1}{

    code={%

      \fill[rounded corners]                  (-0.1,-0.1) rectangle (-0.9, -0.9);

      \fill[left color=white,rounded corners,

            right color=gray,

            opacity=0.7]      (-0.1,-0.1) rectangle (-0.9, -0.9);

      \draw[line width=0.4mm,rounded corners] (-0.1,-0.1) rectangle (-0.9, -0.9);

      \draw[line width=0.2mm,rounded corners] (-0.2,-0.2) rectangle (-0.8, -0.8);

      \draw[anchor=mid] (-0.5,-0.6) node {#1};

    }},

  pics/king/.style n args={1}{

    code={%

      \fill[rounded corners]                  (-0.1,-0.1) rectangle (-0.9, -0.9);

      \fill[left color=white,rounded corners,

            right color=gray,

            opacity=0.7]      (-0.1,-0.1) rectangle (-0.9, -0.9);

      \draw[line width=0.4mm,rounded corners] (-0.1,-0.1) rectangle (-0.9, -0.9);

      \draw[line width=0.2mm,rounded corners] (-0.2,-0.2) rectangle (-0.8, -0.8);

      \draw[anchor=mid] (-0.5,-0.6) node {#1};

      \draw[anchor=center] (-0.5,-0.25) node {\includegraphics[scale=0.015]{crown.png}};

    }}

}

\begin{document}

\setchessboard{smallboard,

               zero,

               showmover=false,

               boardfontencoding=LSBC4,

               hlabelformat=\arabic{ranklabel},

               vlabelformat=\arabic{filelabel}}

\mbox{}\\[-18mm]\mbox{}

\section*{Resit:\\ Implementing the Shogun Board Game\\ (Scala, 8 Marks)}

\noindent

You are asked to implement a Scala program for playing the Shogun

board game.  The deadline for your submission is on XXX at

16:00.  Make sure you use \texttt{scala-cli} and Scala version \textbf{3.XX}

for the resit---the same version as during the lectures.  \medskip

\IMPORTANTNONE{}

\noindent

Also note that the running time of each task will be restricted to a

maximum of 30 seconds on my laptop: If you calculate a result once,

try to avoid to calculate the result again.

\DISCLAIMER{}

\subsection*{Background}

Shogun

(\faVolumeUp\,[shōgoon]) is a game played by two players on a chess board and is somewhat

similar to chess and checkers. A real Shogun board looks

like in the pictures on the left.

\begin{center}

\begin{tabular}{@{}ccc@{}}

\raisebox{2mm}{\includegraphics[scale=0.1]{shogun2.jpeg}}

&

\raisebox{2mm}{\includegraphics[scale=0.14]{shogun.jpeg}}

&

\begin{tikzpicture}[scale=0.45,every node/.style={scale=0.45}]

% chessboard

\draw[very thick,gray] (0,0) rectangle (8,8);

\foreach\x in {0,...,7}\foreach\y in {7,...,0}

{

  \pgfmathsetmacro\blend{Mod(\x+\y,2)==0?75:25}

  \fill[gray!\blend] (\x,\y) rectangle ++ (1,1);

}

% black pieces

\foreach\x/\y/\e in {1/1/1,2/1/3,3/1/2,4/1/3,6/1/3,7/1/1,8/1/2}

  \pic[fill=white] at (\x,\y) {piece={\e}};

% white pieces

\foreach\x/\y/\e in {1/8/4,2/8/2,3/8/4,5/8/4,6/8/2,7/8/3,8/8/1}

  \pic[fill=red] at (\x,\y)     {piece={\e}};

\pic[fill=white] at (5.0,1.0) {king={1}};

\pic[fill=red]   at (4.0,8.0) {king={2}};

% numbers

\foreach\x in {1,...,8}

{\draw (\x - 0.5, -0.4) node {\x};

}

\foreach\y in {1,...,8}

{\draw (-0.4, \y - 0.6, -0.4) node {\y};

}

\end{tikzpicture}

\end{tabular}

\end{center}

\noindent

In what follows we shall use board illustrations as shown on the right.  As

can be seen there are two colours in Shogun for the pieces, red and white. Each

player has 8 pieces, one of which is a king (the piece with the crown)

and seven are pawns. At the beginning the pieces are lined up as shown

above.  What sets Shogun apart from chess and checkers is that each

piece has, what I call, a kind of \textit{energy}---which for pawns is

a number between 1 and 4, and for kings between 1 and 2. The energy

determines how far a piece has to move. In the physical version of

Shogun, the pieces and the board have magnets that can change the

energy of a piece from move to move---so a piece on one field can have

energy 2 and on a different field the same piece might have energy

3. There are some further constraints on legal moves, which are

explained below.  The point of the resit is to implement functions

about moving pieces on the Shogun board.\medskip\medskip

%and testing for when a

%checkmate occurs---i.e.~the king is attacked and cannot move

%anymore to an ``unattacked'' field (to simplify matters for

%the resit we leave out the case where the checkmate can be averted by capturing

%the attacking piece).\medskip

\noindent

Like in chess, in Shogun the players take turns of moving and

possibly capturing opposing pieces.

There are the following rules on how pieces can move:

\begin{itemize}

\item The energy of a piece determines how far, that is how many

  fields, a piece has to move (remember pawns have an energy between 1 --

  4, kings have an energy of only 1 -- 2). The energy of a piece might

  change when the piece moves to new field.

\item Pieces can move in straight lines (up, down, left, right), or in

  L-shape moves, meaning a move can make a single

  90$^{\circ}$-turn. S-shape moves with more than one turn are not

  allowed. Also in a single move a piece cannot go forward and then

  go backward---for example with energy 3 you cannot move 2 fields up and

  then 1 field down. A piece can never move diagonally.

\item A piece cannot jump over another piece and cannot stack up on top of your own pieces.

  But you can capture an opponent's piece if you move to an occupied field. A captured

  piece is removed from the board.

\end{itemize}

\noindent

Like in chess, checkmate is determined when the king of a player cannot

move anymore to a field that is not attacked, or a player cannot

capture or block the attacking piece, or the king is the only

piece left for a player. A non-trivial board that is checkmate is the following:

\begin{center}

\begin{tikzpicture}[scale=0.5,every node/.style={scale=0.5}]

% chessboard

\draw[very thick,gray] (0,0) rectangle (8,8);

\foreach\x in {0,...,7}\foreach\y in {7,...,0}

{

  \pgfmathsetmacro\blend{Mod(\x+\y,2)==0?75:25}

  \fill[gray!\blend] (\x,\y) rectangle ++ (1,1);

}

% redpieces

\pic[fill=red]   at (4,2) {king={2}};

\pic[fill=red]   at (6,1) {piece={3}};

\pic[fill=red]   at (4,4) {piece={4}};

\pic[fill=red]   at (5,3) {piece={4}};

% white pieces

\pic[fill=white] at (7,1) {king={2}};

\pic[fill=white] at (8,5) {piece={2}};

\pic[fill=white] at (4,1) {piece={2}};

% numbers

\foreach\x in {1,...,8}

{\draw (\x - 0.5, -0.4) node {\x};

}

\foreach\y in {1,...,8}

{\draw (-0.4, \y - 0.6, -0.4) node {\y};

}

\end{tikzpicture}

\end{center}

\noindent

The reason for the checkmate is that the white king on field (7, 1) is

attacked by the red pawn on \mbox{(5, 3)}. There is nowhere for the

white king to go, and no white pawn can be moved into the way of this

red pawn and white can also not capture it. When determining a possible

move, you need to be careful with pieces that might be in the

way. Consider the following position:

\begin{equation}\label{moves}

\begin{tikzpicture}[scale=0.5,every node/.style={scale=0.5}]

% chessboard

\draw[very thick,gray] (0,0) rectangle (8,8);

\foreach\x in {0,...,7}\foreach\y in {7,...,0}

{

  \pgfmathsetmacro\blend{Mod(\x+\y,2)==0?75:25}

  \fill[gray!\blend] (\x,\y) rectangle ++ (1,1);

}

% redpieces

\fill[blue!50] (0,2) rectangle ++ (1,1);

\fill[blue!50] (1,1) rectangle ++ (1,1);

\fill[blue!50] (0,4) rectangle ++ (1,1);

\fill[blue!50] (1,5) rectangle ++ (1,1);

\fill[blue!50] (2,6) rectangle ++ (1,1);

%%\fill[blue!50] (3,7) rectangle ++ (1,1);

\fill[blue!50] (4,6) rectangle ++ (1,1);

\fill[blue!50] (5,5) rectangle ++ (1,1);

\fill[blue!50] (6,4) rectangle ++ (1,1);

\fill[blue!50] (6,2) rectangle ++ (1,1);

\fill[blue!50] (7,3) rectangle ++ (1,1);

\fill[blue!50] (4,0) rectangle ++ (1,1);

\fill[blue!50] (2,0) rectangle ++ (1,1);

\pic[fill=red]   at (4,4) {piece={4}};

\pic[fill=red]   at (4,8) {piece={4}};

\pic[fill=white] at (2,5) {piece={3}};

\pic[fill=white] at (4,3) {piece={2}};

\pic[fill=white] at (6,3) {piece={1}};

\pic[fill=white] at (8,4) {piece={1}};

% numbers

\foreach\x in {1,...,8}

{\draw (\x - 0.5, -0.4) node {\x};

}

\foreach\y in {1,...,8}

{\draw (-0.4, \y - 0.6, -0.4) node {\y};

}

\end{tikzpicture}

\end{equation}

\noindent

The red piece in the centre on field (4, 4) can move to all the blue fields.

In particular it can move to (2, 6), because it can move 2 fields up

and 2 fields to the left---it cannot reach this field by moving two

fields to the left and then two up, because jumping over the white

piece at (2, 5) is not allowed. Similarly, the field at (6, 2) is

unreachable for the red piece because of the two white pieces at (4,

3) and (6, 3) are in the way and no S-shape move is allowed in

Shogun. The red piece on (4, 4) cannot move to the field (4, 8) at the

top, because a red piece is already there; but it can move to (8, 4)

and capture the white piece there. The moral is we always have to

explore all possible ways in order to determine whether a piece can be

moved to a field or not: in general there might be several ways and some of

them might be blocked.

\subsection*{Hints}

Useful functions about pieces and boards are defined at the beginning

of the template file. The function \texttt{.map} applies a function to

each element of a list or set; \texttt{.flatMap} works like

\texttt{map} followed by a \texttt{.flatten}---this is useful if a

function returns a set of sets, which need to be ``unioned up''.  Sets

can be partitioned according to a predicate with the function

\texttt{.partition}.  For example

\begin{lstlisting}

val (even, odd) = Set(1,2,3,4,5).partition(_ % 2 == 0)

// --> even = Set(2,4)

//     odd  = Set(1,3,5)

\end{lstlisting}

\noindent

The function \texttt{.toList} transforms a set into a list. The function

\texttt{.count} counts elements according to a predicate. For example

\begin{lstlisting}

Set(1,2,3,4,5).count(_ % 2 == 0)

// --> 2

\end{lstlisting}

%% \newpage

\subsection*{Tasks}

You are asked to implement how pieces can move on a Shogun board.  Let

us first fix the basic datastructures for the implementation.  A

\emph{position} (or field) is a pair of integers, like $(3, 2)$. The

board's dimension is always 8 $\times$ 8.  A \emph{colour} is either

red (\texttt{Red}) or white (\texttt{Wht}).  A \emph{piece} is either

a pawn or a king, and has a position, a colour and an energy (an

integer).  In the template file there are functions \texttt{incx},

\texttt{decx}, \texttt{incy} and \texttt{decy} for incrementing and

decrementing the x- and y-coordinates of positions of pieces.

A \emph{board} consists of a set of pieces. We always assume that we

start with a consistent board and every move only generates another

consistent board. In this way we do not need to check, for example,

whether pieces are stacked on top of each other or located outside the

board, or have an energy outside the permitted range. There are

functions \texttt{-} and \texttt{+} for removing, respectively adding,

single pieces to a board.  The function \texttt{occupied} takes a

position and a board as arguments, and returns an \texttt{Option} of a

piece when this position is occupied, otherwise \texttt{None}. The

function \texttt{occupied\_by} returns the colour of a potential piece

on that position. The function \texttt{is\_occupied} returns a boolean

for whether a position is occupied or not; \texttt{print\_board} is a

rough function that prints out a board on the console. This function

is meant for testing purposes.

\begin{itemize}

\item[(1)] You need to calculate all possible moves for a piece on a Shogun board. In order to

  make sure no piece moves forwards and backwards at the same time,

  and also exclude all S-shape moves, the data-structure \texttt{Move}

  is introduced. A \texttt{Move} encodes all simple moves (up, down, left,

  right) and L-shape moves (first right, then up and so on). This is defined

  as follows:

{\small\begin{lstlisting}

abstract class Move

case object U extends Move    // up

case object D extends Move    // down

case object R extends Move    // right

case object L extends Move    // left

case object RU extends Move   // ...

case object LU extends Move

case object RD extends Move

case object LD extends Move

case object UR extends Move

case object UL extends Move

case object DR extends Move

case object DL extends Move

\end{lstlisting}}

You need to implement an \texttt{eval} function that takes a piece

\texttt{pc}, a move \texttt{m}, an energy \texttt{en} and a board

\texttt{b} as arguments. The idea is to recursively calculate all

fields that can be reached by the move \texttt{m} (there might be more than

one). The energy acts as a counter and decreases in each recursive

call until 0 is reached (the final field). The function \texttt{eval} for a piece \texttt{pc}

should behave as follows:

\begin{itemize}

\item If the position of a piece is outside the board, then no field can be reached (represented by

  the empty set \texttt{Set()}).

\item If the energy is 0 and the position of the piece is \textit{not} occupied, then the field can be reached

  and the set \texttt{Set(pc)} is returned whereby \texttt{pc} is the piece given as argument.

\item If the energy is 0 and the position of the piece \textit{is} occupied, but occupied by a piece

  of the opposite colour, then also the set \texttt{Set(pc)} is returned. Otherwise the empty set

    \texttt{Set()} is returned.

\item In case the energy is > 0 and the position of the piece

  \texttt{pc} is occupied, then this move is blocked and the set

  \texttt{Set()} is returned.

\item In all other cases we have to analyse the move

    \texttt{m}. First, the simple moves (that is \texttt{U}, \texttt{D},

    \texttt{L} and \texttt{R}) we only have to increment / decrement the

    x- or y-position of the piece, decrease the energy and call eval

    recursively with the updated arguments. For example for \texttt{U} (up)

    you need to increase the y-coordinate:

  \begin{center}

  \texttt{U} $\quad\Rightarrow\quad$ new arguments: \texttt{incy(pc)}, \texttt{U}, energy - 1, same board

  \end{center}

  The move \texttt{U} here acts like a ``mode'', meaning if you move

   up, you can only move up; the mode never changes for simple moves. Similarly for the other simple moves: if

   you move right, you can only move right and so on. In this way it is

   prevented to go first to the right, and then change direction in order to go

   left (same with up and down).

  For the L-shape moves (\texttt{RU}, \texttt{LU}, \texttt{RD} and so on) you need to calculate two

  sets of reachable fields. Say we analyse \texttt{RU}, then we first have to calculate all fields

  reachable by moving to the right; then we have to calculate all moves by changing the mode to \texttt{U}.

  That means there are two recursive calls to \texttt{eval}:

  \begin{center}

    \begin{tabular}{@{}lll@{}}

    \texttt{RU} & $\Rightarrow$ & new args for call 1: \texttt{incx(pc)}, \texttt{RU}, energy - 1, same board\\

                &               & new args for call 2: \texttt{pc}, \texttt{U}, same energy, same board

    \end{tabular}

    \end{center}

  In each case we receive some new piece(s) on reachable fields and therefore we return the set

  containing all these fields. Similarly in the other cases.

\end{itemize}

For example in the left board below, \texttt{eval} is called with the white

piece in the centre and the move \texttt{RU} generates then a set of

new pieces corresponding to the blue fields. The difference with the

right board is that \texttt{eval} is called with a red piece and therefore the

field (4, 8) is not reachable anymore because it is already occupied by

another red piece. But (7, 5) becomes reachable because it is occupied

by a piece of the opposite colour.

\begin{center}

\begin{tabular}{cc}

\begin{tikzpicture}[scale=0.45,every node/.style={scale=0.45}]

% chessboard

\draw[very thick,gray] (0,0) rectangle (8,8);

\foreach\x in {0,...,7}\foreach\y in {7,...,0}

{

  \pgfmathsetmacro\blend{Mod(\x+\y,2)==0?75:25}

  \fill[gray!\blend] (\x,\y) rectangle ++ (1,1);

}

\fill[blue!50] (5,5) rectangle ++ (1,1);

\fill[blue!50] (3,7) rectangle ++ (1,1);

\fill[blue!50] (4,6) rectangle ++ (1,1);

%\fill[blue!50] (6,4) rectangle ++ (1,1);

\fill[blue!50] (7,3) rectangle ++ (1,1);

% black pieces

\foreach\x/\y/\e in {2/1/3,3/1/2,4/1/3,6/1/3,7/1/1,7/5/2}

  \pic[fill=white] at (\x,\y) {piece={\e}};

% white pieces

\foreach\x/\y/\e in {1/8/4,2/8/2,3/8/4,5/8/4,6/8/2,7/8/3,8/8/1}

  \pic[fill=red] at (\x,\y)     {piece={\e}};

\pic[fill=white] at (5.0,1.0) {king={1}};

\pic[fill=red]   at (4.0,8.0) {king={2}};

\pic[fill=white] at (4,4) {piece={4}};

% numbers

\foreach\x in {1,...,8}

{\draw (\x - 0.5, -0.4) node {\x};

}

\foreach\y in {1,...,8}

{\draw (-0.4, \y - 0.6, -0.4) node {\y};

}

\end{tikzpicture}

&

\begin{tikzpicture}[scale=0.45,every node/.style={scale=0.45}]

% chessboard

\draw[very thick,gray] (0,0) rectangle (8,8);

\foreach\x in {0,...,7}\foreach\y in {7,...,0}

{

  \pgfmathsetmacro\blend{Mod(\x+\y,2)==0?75:25}

  \fill[gray!\blend] (\x,\y) rectangle ++ (1,1);

}

\fill[blue!50] (5,5) rectangle ++ (1,1);

\fill[blue!50] (4,6) rectangle ++ (1,1);

\fill[blue!50] (6,4) rectangle ++ (1,1);

\fill[blue!50] (7,3) rectangle ++ (1,1);

% black pieces

\foreach\x/\y/\e in {1/1/1,2/1/3,3/1/2,4/1/3,6/1/3,7/1/1,7/5/2}

  \pic[fill=white] at (\x,\y) {piece={\e}};

% white pieces

\foreach\x/\y/\e in {1/8/4,2/8/2,3/8/4,5/8/4,6/8/2,7/8/3}

  \pic[fill=red] at (\x,\y)     {piece={\e}};

\pic[fill=white] at (5.0,1.0) {king={1}};

\pic[fill=red]   at (4.0,8.0) {king={2}};

\pic[fill=red] at (4,4) {piece={4}};

% numbers

\foreach\x in {1,...,8}

{\draw (\x - 0.5, -0.4) node {\x};

}

\foreach\y in {1,...,8}

{\draw (-0.4, \y - 0.6, -0.4) node {\y};

}

\end{tikzpicture}

\\[-5mm]

\end{tabular}

\end{center}\hfill[3 Marks]

\item[(2)] Implement an \texttt{all\_moves} function that calculates for a

  piece and a board, \textit{all} possible onward positions. For this

  you have to call \texttt{eval} for all possible moves \texttt{m} (that is \texttt{U},

  \texttt{D}, \ldots, \texttt{DL}). An example for all moves for the red piece on (4, 4) is

  shown in \eqref{moves} on page \pageref{moves}. Be careful about possible modifications

  you need to apply to the board  before you call the \texttt{eval} function.

  Also for this task, ignore the fact that a king cannot move onto an attacked field.\\

  \mbox{}\hfill[1 Mark]

\item[(3)] Implement a function \texttt{attacked} that takes a colour and a board

  and calculates all pieces of the opposite side that are attacked. For example

  below in the left board are all the attacked pieces by red, and on the right all for white:

\begin{center}

\begin{tabular}{cc}

\begin{tikzpicture}[scale=0.45,every node/.style={scale=0.45}]

% chessboard

\draw[very thick,gray] (0,0) rectangle (8,8);

\foreach\x in {0,...,7}\foreach\y in {7,...,0}

{

  \pgfmathsetmacro\blend{Mod(\x+\y,2)==0?75:25}

  \fill[gray!\blend] (\x,\y) rectangle ++ (1,1);

}

\fill[blue!50] (7,3) rectangle ++ (1,1);

\fill[blue!50] (6,0) rectangle ++ (1,1);

% red pieces

\foreach\x/\y/\e in {6/1/3,4/4/4,5/3/4,6/5/3}

  \pic[fill=red] at (\x,\y) {piece={\e}};

% white pieces

\foreach\x/\y/\e in {8/4/1,4/1/2,8/7/3,6/7/2}

  \pic[fill=white] at (\x,\y)     {piece={\e}};

\pic[fill=red] at (4,2) {king={2}};

\pic[fill=white] at (7,1) {king={2}};

% numbers

\foreach\x in {1,...,8}

{\draw (\x - 0.5, -0.4) node {\x};

}

\foreach\y in {1,...,8}

{\draw (-0.4, \y - 0.6, -0.4) node {\y};

}

\end{tikzpicture}

&

\begin{tikzpicture}[scale=0.45,every node/.style={scale=0.45}]

% chessboard

\draw[very thick,gray] (0,0) rectangle (8,8);

\foreach\x in {0,...,7}\foreach\y in {7,...,0}

{

  \pgfmathsetmacro\blend{Mod(\x+\y,2)==0?75:25}

  \fill[gray!\blend] (\x,\y) rectangle ++ (1,1);

}

\fill[blue!50] (5,0) rectangle ++ (1,1);

\fill[blue!50] (5,4) rectangle ++ (1,1);

% red pieces

\foreach\x/\y/\e in {6/1/3,4/4/4,5/3/4,6/5/3}

  \pic[fill=red] at (\x,\y) {piece={\e}};

% white pieces

\foreach\x/\y/\e in {8/4/1,4/1/2,8/7/3,6/7/2}

  \pic[fill=white] at (\x,\y)     {piece={\e}};

\pic[fill=red] at (4,2) {king={2}};

\pic[fill=white] at (7,1) {king={2}};

% numbers