5-Adversarial-Search

[redblobgames]

Let's discuss what concepts are presented in this chapter, and what visualizations can show the concepts, problems, and algorithms.

[redblobgames]

One of the difficult things here will be that even small games like tic tac toe lead to a large game tree, so we wouldn't want to draw the entire tree. The book shows a part of the tree. One approach is to let the reader choose which tree nodes to expand.

For minimax, when the reader mouse-hovers over a possible move, you could how the AI looks several moves ahead of that. That way instead of showing the entire game tree you would be showing only the subtree that's a child of the move where the mouse position is.

Alpha beta pruning is a modification of minimax so it may be useful to present the same way as minimax, except highlighting which tree nodes are pruned and why.

Other concepts to figure out how to visualize (if it's better than what's in the book — sometimes a static diagram in the book is already the best way to visualize it, and then we don't need to implement an interactive version) — perfect information vs limited information, different evaluation functions, cutoff, information gained by exploring deeper (you might show a plot of number of nodes vs how good the estimate is).

[Ghost---Shadow]

Does it have to be Tic Tac Toe? It will have a tree depth of 9. Cant we use prisoner's dilemma or something similar yet contrived such that the entire tree fits in the screen.

[redblobgames]

Ch 5 was implemented in GSoC 2018