THOUGHT EXERCISES

How many Prisoner's Dilemma strategies with a memory of three games are there that are

behaviorally equivalent to TIT FOR TAT? What fraction is this of the total number of strategies with

a memory of three games?

Chapter $1$: Genetic Algorithms: An Overview

What is the total payoff after $10$ games of TIT FOR TAT playing against $($a$)$ a strategy that always

defects; $($b$)$ a strategy that always cooperates; $($c$)$ ANTI$-$TIT$-$FOR$-$TAT, a strategy that starts out by

defecting and always does the opposite of what its opponent did on the last move? $($d$)$ What is the

expected payoff of TIT FOR TAT against a strategy that makes random moves? $($e$)$ What are the total

payoffs of each of these strategies in playing $10$ games against TIT FOR TAT? $($For the random

strategy, what is its expected average payoff?$)$

How many possible sorting networks are there in the search space defined by Hillis's representation?

Prove that any string of length $l$ is an instance of $2^l$ different schemas.

Define the fitness $f$ of bit string $x$ with $l=4$ to be the integer represented by the binary number $x.$

$($e$.$g$.,f(0011)=3,f(1111)=15).$ What is the average fitness of the schema $1^{******}$ under $f?$ What is the

average fitness of the schema $0^{******}$ under $f?$

Define the fitness of bit string $x$ to be the number of ones in $x.$ Give a formula, in terms of $l($the string

length$)$ and $k,$ for the average fitness of a schema $H$ that has $k$ defined bits, all set to $1.$

When is the union of two schemas also a schema? For example, $\{0^{**}{\}}^{**}\{1^{**}\}$ is a schema ${(}^{****}),$ but

$\{01{\}}^{**}\{10\}$ is not. When is the intersection of two schemas also a schema? What about the difference

of two schemas?

Are there any cases in which a population of $nl-$bit strings contains exactly $n{2}^l$ different schemas?