Errata for Algorithms for Computer Games
This list describes the known bugs and errors in the first printing of the first edition (2003) of the lecture notes. Typically, page and line numbers are given to localize the error. A negative line number indicates numbering from the bottom up. Actual text from the lecture notes is surrounded by (( )). Replacement text, where provided, is surrounded by || ||.
Page v, line 19
Change ((would allowed)) to ||would have allowed||.
Page v, line 20
Change ((notes several)) to ||notes in several||.
Page v, line 21
Change ((topics have been)) to ||topics has been||.
Page 2, line 6
Change ((participate the game)) to ||participate in the game||.
Page 5, line -9
Change ((should no be)) to ||should be no||.
Page 8, line -5
Change ((tend think)) to ||tend to think||.
Page 10, line -14
Change ((really feels that)) to ||really feel that||.
Page 17, line 3
Change (([Knu98, §3])) to ||[Knu98a, §3]||.
Page 17, line -1
Change (([Knu98, p. 6])) to ||[Knu98a, p. 6]||.
Page 18, line 1
Change ((random generator)) to ||random number generator||.
Page 21, Theorem 2.1, part (i)
Although not incorrect, it is better to change ((denominator)) to ||divisor||.
Page 21, line -12
Change (([Knu98, pp. 17-19])) to ||[Knu98a, pp. 17-19]||.
Page 21, lines -8 and -7
Change ((binary digits should not have a simple, regular pattern)) to ||binary representation should not have a simple, regular bit pattern||.
Page 22, line 11
Change (([Knu98, §3.3])) to ||[Knu98a, §3.3]||.
Page 23, lines -2 and -1
Change ((each permutation has)) to ||all permutations have||.
Page 24, footnote, line 3
Change ((it is has)) to ||it has||. Change (([Knu98,)) to ||[Knu98a,||.
Page 25, line 5
Change (([Knu98, p. 147])) to ||[Knu98a, p. 147]||.
Page 25, line 7
Change ((a spectator asks her)) to ||a spectator and asks her||.
Page 27, Algorithm 2.4, preamble
Change ((maximum width)) to ||maximum horizontal value|| and ((maximum height)) to ||maximum vertical value||.
Page 27, Algorithm 2.4, line 4
Equality must be allowed: Change ((< d)) to ||≤ d||.
Page 31, line -1
Change ((review minimax method)) to ||review the minimax method||.
Page 33, Figure 3.2
Change the assigned value ((-1)) to ||+1|| in the node "3-3-1-1".
Page 35, Algorithm 3.2, line 6
The return value of the function call should be negated. The correct statement is ||e ← max{e, -NEGAMAX(u)}||.
Page 36, lines 11-12
Change ((series losing)) to ||series of losing||.
Page 43, Figure 4.3
In the right, some of the tiles in the middle of the grid have been mistakingly coloured to be outside the waypoints. If the majority of the tile is inside the game world in the left, the corresponding tile in the right should be coloured white.
Page 47, line 4
Change ((set vertices))) to ||set of vertices||.
Page 48, line 11
Change ((we f(v))) to ||we let f(v)||.
Page 50, Algorithm 4.2, line 15
Only the expanded vertices can be omitted. In addition to the successors that have not been visited yet, we must consider also the (already visited) successors in the set S, given that they can be improved. Replace the statement with ||if π(u) = NIL or else (u ∈ S and g(s, v) + weight(v, u) < g(s, u)) then|| and change the comment to ||Not expanded?||.
Page 55, line 1
Change ((able make))) to ||able to make||.
Page 58, line 3
Change ((what do)) to ||what to do||.
Page 58, line -12
Change ((when acts)) to ||when it acts||.
Page 63, Algorithm 5.1, lines 20 and 21
To prevent the hunter from wasting arrows by shooting twice the same room, the influence map wumpus can be updated to have a zero if the room is shot at. Hence, insert between lines 20 and 21 the statement wumpus(u) ← 0.
Page 67, Algorithm 5.2, preamble
Change ((avoidance weight wa)) to ||avoidance weight wv||.
Page 67, Algorithm 5.2, line 15
To improve reactivity, move line 15 after line 19.
Page 71, line -6
Change ((tampering the network)) to ||tampering with the network||.
Page 71, line -3
Change ((in an online)) to ||in online||.
Page 72, Figure 6.1
Change ((tempering)) to ||tampering||.
Page 74, line 24
Change ((participating the game)) to ||participating in the game||.
Page 76, line 7
Change ((lead)) to ||led||.
Page 76, line 17
Change ((blocking exists, interfering fights)) to ||blocking exits, interfering with fights||.
Page 76, line 20
Change ((tampering the network)) to ||tampering with the network||.
Page 77, line 3
Change ((with sender's)) to ||with the sender's||.
Page 77, line -2
Change ((on peer-to-peer)) to ||on a peer-to-peer||.
Pages 78-80
Add definite articles in front of the terms "lockstep protocol", "pipelined lockstep protocol", and "adaptive pipeline protocol".
Page 79, line 2
Change ((or to lose)) to ||or lose||.
Page 80, Figure 6.3, caption
Change ((which hold)) to ||which holds||.
Page 81, line 6
Change ((time-space communication)) to ||time-space-communication||.
Page 87, Algorithm 7.1, function GET-BIT-SHIFTED, line 1
Change (((w >>> 1))) to ||(w >>> s)||.
Page 93, Algorithm 7.6, function SET-BITS
To avoid a name collision between parameter w and local variable w, change the former to v. Hence, change ((w)) to ||v|| in signature, in preamble sections in and out; in line 4 change ((w ← w)) to ||w ← v||, and in line 9 change ((u ← w)) to ||u ← v||.
Page 93, Algorithm 7.6, function SET-BITS, preamble
Change ((bits())) to ||bits(B)||.
Page 97, line 14
Change ((length Bn)) to ||length n||.
Page 105, Algorithm 7.12, function SET-INITIALIZED, line 4
Change ((Tcount())) to ||Tcount(Q)||.