search

jeffgerickson / algorithms

Bug-tracking for Jeff's algorithms book, notes, etc.
7.92k stars 1.02k forks source link

Game trees (chapter 2.2). Node states confusion. Typo? (page 73) #116

Closed DmitryMak closed 5 years ago

DmitryMak commented 5 years ago

0th edition (pre-publication draft) — December 29, 2018, page #73 says:

Equivalently, a non-leaf node in the game tree is good if it has at least one bad child, and a non-leaf node is bad if all its children are good.

Is this intentional, or should it be swapped?

erbenpeter commented 5 years ago

If it's about a two-player game, then I think it's correct, assuming the "good" and "bad" labels are given based on who is the next player.

Let's say it's my turn. I want to choose a child node. If all of the children of my node are "good", it means that my opponent will have a winning position, regardless of my choice. So I'm in a "bad" position.

DmitryMak commented 5 years ago

Makes sense, thanks for the explanation!