\documentclass[12pt,a4paper]{article}
\usepackage{graphicx}
\pagestyle{empty}
\oddsidemargin 2.1mm
\textwidth 155mm
\topmargin -15mm
\textheight 240mm
\def\rgtfig#1{\hangafter-7\hangindent-50mm\noindent
\hbox to0pt{\vbox to1.5ex{\noindent\hbox to\textwidth{\hss
#1}\vss}\hss}\ignorespaces}
\begin{document}
%-----------------------------------------------------------------------
\noindent
{\bf Evolutionary Algorithms} \hfill Winter 2017/2018 \\
PD~Dr.-Ing.~habil.~Christian~Borgelt \hfill from 2018.01.18
%-----------------------------------------------------------------------
\vskip3ex
\centerline{\bf Exercise Sheet 6}
%-----------------------------------------------------------------------
\subsubsection*{Exercise 21 \quad\rm Iterated Prisoner's Dilemma}
\hangafter-5\hangindent-40mm\noindent
\hbox to0pt{\vbox to1.5ex{\noindent\hbox to\textwidth{\hss
\begin{tabular}{|r|c|c|}\hline
A$\backslash$B & C & D\rule{0pt}{2.4ex} \\ \hline
C & 3$\backslash$3 & 0$\backslash$5\rule{0pt}{2.4ex} \\ \hline
D & 5$\backslash$0 & 1$\backslash$1\rule{0pt}{2.4ex} \\ \hline
\end{tabular}}\vss}\hss}\noindent
The lecture discussed the iterated prisoner's dilemma, for which
it was tried to find a good strategy using a genetic algorithm.
The used payoff matrix is stated again on the right. Here C stands
for ``cooperate'', D for ``defect''. The fields of the matrix contain
the payoffs for the two players~A and B.
In order to better understand the properties of different possible
game strategies, we consider in this and the next exercise a few
special, simple strategies and try to determine their advantages and
disadvantages. We start by considering two players that choose their
action randomly, for example, by throwing a coin. Compute the expected
payoff for a player and the variance/standard deviation of this payoff!
%-----------------------------------------------------------------------
\subsubsection*{Exercise 22 \quad\rm Iterated Prisoner's Dilemma}
Other simple strategies for the iterated prisoner's dilemma are:
\begin{enumerate}\itemsep0pt
\item[(i)] Always play ``defect''.
\item[(ii)] Always play ``cooperate''.
\item[(iii)] Play ``Tit-for-Tat'', that is, in the first match play
``cooperate'', in all remaining matches play the move
the opponent made in the preceding match.
\end{enumerate}
Consider a tournament in which the three strategies play against each
other, in a round robin fashion, a 100-fold iterated prisoner's dilemma
(that is, each of the strategies plays 100 matches of the prisoner's
dilemma against every other strategy). Which average payoff is achieved
by the strategies? What changes if two or three players in the
tournament play ``Tit-for-Tat'' (so that there are, in total, four
or five player, respectively)? In these extended cases: what effect
do additional players have that always play ``defect''?
\medskip\noindent
Additional questions:
\begin{enumerate}\itemsep0pt
\item[a)] Up to now we always tried to optimize, with the help of an
evolutionary algorithm, the parameters of a function that
was defined independently of the evolutionary algorithm.
Is there, for the prisoner's dilemma, also an independent
function that is optimized? Justify your answer!
\item[b)] If not (only) an external function, what is actually
optimized if we use an evolutionary algorithm to search
for (good) strategies to play the prisoner's dilemma?
\end{enumerate}
%-----------------------------------------------------------------------
\newpage
\subsubsection*{Exercise 23 \quad\rm Blackjack}
Blackjack (in German also known as ``17 and 4'') is a card game, that
is played by a dealer and a player.\footnote{In casinos the game is also
played with multiple players at the same time, but moves only concern
the dealer and one player, so that we can confine our considerations to
one player.} The game strategy of the dealer is fixed by the rules of
the game. Only the player can make decisions. The objective of the player
is to get a hand of cards, the value of which does not exceed 21 and is
closer to 21 than the value of the hand of the dealer. The individual
cards have the following values: Ace --- 1 or 11, picture cards --- 10,
number cards 2 to 10 --- the number stated on them. The suits (clubs,
spades, hearts, diamonds) are irrelevant. The value of a hand is the
sum of the values of the individual cards contained in it. The ace has
a value of 1 or 11, whichever brings the value of the hand closer to 21
without exceeding 21.
At the beginning of the game the player makes a bet. Then the dealer
deals two cards each to the player and to him-/herself. In this exercise
we consider the variant in which the cards are placed laid out openly
for everyone to see (so called ``shoe game''). The player now can decide
whether he wants to receive more cards. If another card pushes the value
of his/her hand beyond 21, he/she loses the game and the bet. However,
if with a value of his/her hand of 21 or less he/she does not ask for
another card, the dealer completes his/her hand according to fixed
rules: The dealer has to take another card as long as the value of
his/her hand is below 17 and must not take another card as soon as
the value of his/her hand reaches or exceeds 17 (hence the German
name ``17 and 4''). In order to determine the value of his/her hand,
he/she must count an ace as 11, if this is possible without the value
of the hand exceeding 21. If the value of the hand of the dealer
exceeds 21 or the value of the hand of the player is closer to 21
than the value of the hand of the dealer, the player wins and receives
twice his bet. Otherwise the player loses his/her bet.\footnote{We
disregard here certain subleties that are to be considered when playing
in a casino, for example, a 50\% increase of the winnings if the game
is won with a blackjack (exactly 21 with thw first two cards) as well
as the split of two equal cards (differing only in their suits) etc.}
How can one find a good game strategy for blackjack with the help of
an evolutionary algorithm?
%-----------------------------------------------------------------------
\subsubsection*{Exercise 24 \quad\rm Genetic Programming: Crossover}
Design an algorithm that constructs from two given parent programs (for
example, in the form of parse trees or Lisp/Scheme expressions) a child
program using crossover! In case you know these languages, state the
algorithm in Lisp/Scheme. \\
(Hint: Split the problem into two subproblems:
\vspace{-0.7ex}
\begin{enumerate}\itemsep0pt
\item[a)] The random selection of an expression and
\item[b)] the insertion of an expression at a randomly chosen position\\
(replacing the expression at this position).
\end{enumerate}
\vskip-0.5ex
How can this function (or a part of it) be used at the same time to
implement a mutation operation?
%-----------------------------------------------------------------------
\subsubsection*{Additional Exercise \quad\rm Newcomb's Paradox}
Newcomb's Paradox (named after its inventor, the physicist William
Newcomb) has a structure that is closely related to the prisoner's
dilemma. Some creature, which we will call the ``prophet'', shows two
closed boxes, A and B, to you. You can choose whether you want to
(1) open only box B or (2) open both boxes. You may keep the content
of the boxes you choose to open. The prophet, who claims that he can
predict the actions of humans, filled the boxes as follows: Box~A
always contains 1000~Euro (independent of the prophet's prediction).
If the prophet predicted that you will open only box~B, the prophet
placed one million Euro into box~B. However, if the prophet predicted
that you will open both boxes, box~B is left empty. Furthermore, it is
known that many times in the past the prophet predicted the behavior
of humans in this situation and was never wrong. What do you do?
%-----------------------------------------------------------------------
\end{document}