Game Development Reference
In-Depth Information
you can see immediately who has won (player 1 or player 2). So what you
can do then, is to assign a cost or a reward value to each of the edges, for
example
10 for an
edge that leads to your opponent's victory, and 0 for an edge that leads to a
draw. Then, after the real player has made a choice, the computer can walk
through the tree and find the path that minimizes the loss for the worst case
(maximum loss) scenario (which also explains the name of the algorithm).
The Minimax algorithm is a classic AI algorithm that is used in many games
where the computer has to make a choice between a number of alternatives
and where there are discrete turns with a predetermined outcome. Many
board games are suitable for this, such as chess, checkers, and so on. This
algorithm is not always useful, since it means that you have to (partly) con-
struct the tree of possible decisions and their outcomes, which can get quite
complicated depending on the type of game. For example in chess, the num-
ber of different states is estimated at 10
43
+
10 for an edge that helps leading to your victory,
−
and the number of different nodes
in the game tree at 10
120
!
A.4 Exercises and Challenges for Part
IV
Exercises
1.
Lists
The
List<
string
>
class contains (among others) methods that have the following
headers:
public void
Reverse()
public int
LastIndexOf(
string
item)
public bool
Contains(
string
item)
Suppose that you are the author of the
List
class and these methods have not yet
been implemented. Implement these three methods. You may not use existing
methods carrying the same name, or other varieties of these methods with these
names, because we assume that these methods are not there yet. Apart from these
methods, you may use any other method in the
List
class, as well as your own
methods.
2.
Collections
Write a method
RemoveDuplicates
which receives as a parameter a
List
of
int
values. The method removes all of the duplicates of the numbers in the list
that is provided as a parameter. For example, the list containing the numbers
0, 1, 3, 2, 1, 5, 2
becomes
0, 1, 3, 2, 5
. Watch out: the return type of this method
should be
void
!