in Game Tree Search

Interactive (human + computer) game play has achieved
impressive successes in the last few decades. In
most
"teams" the computers are used to generate sets of
candidate
moves and to present them in such a way that
the human
boss finds it easy to select his or her
favorite move.

Several good screen layouts have been realized.
See the
examples below: first a series for Monte-Carlo
game tree
searches in Go, Hex, and Havannah; in the second part
some k-best visualisations
for alpha-beta search with
iterative deepening.

Concerning territory, green means ownership for White and blue for Black. Red circles of different sizes indicate the number of visits. The radii of circles are proportional to the ratio logarithm(visits) / logarithm(max-visits). Persson first used visits/max-visits but then only the moves searched a lot became visible. In the example, the largest circle is 1578 visits and the smallest is 9 visits. The medium sized are about 150-700 visits. In the position, Black is to move.

Persson did not include

This picture belongs to a

The red pie slices are positive (winning) estimates and the blue pie slices are negative (losing) estimates, hence the algorithm is very confident that all but the four red moves are almost certainly losing moves. If the algorithm searched for longer on the cells with the three small red pie slices, the red slices would shrink then become blue as their true negative value is realised.

Circle radius is based on the number of times that each node (move) has been visited. This is an

The Havannah board is hexagonal, size 6 in this example. Black and White are stones, already placed by the two players. In the diagram Black is to move.

Candidate moves are shown by blobs with different colors (between green and red) and different sizes. The color of a blob is the move value (green = good, red = bad), and the size of a blob indicates the number of visits (large = many). Colors are normalized (the best value is always pure green, no matter how bad it actually is), and visit counts are logarithmic.

When Johannes Waldmann presented this solution in the Havannah/Hex forum of www.littlegolem.net, he gave a promise:

The program shows a variable number of "popular" moves. The numbers in the board indicate the candidate moves. The values are the Monte Carlo scores for these moves, rounded to full percent. In the lower left part of the window the principal variation for the best move (k5 in the example) is shown. Typically, only the first 3-5 moves of this line can be "interpreted" seriously.

Fuego has a routine that does not show values of moves but how often a square will finally end in the territory of Black and White, respectively. The size of the white and dark grey squares represents the percentage of playouts that ended up with that point being territory for that color. For example, a large white square means that white almost always owned this point, while a small grey square means that black owned it only slightly more often than white. The exact values are scaled from -1 (always white) to +1 (always black).

Solutions from before the ages of Monte Carlo game tree search

**********

K-best search in game trees gives the user not only the single best move, but a list with the k best move candidates. Here "best" is always meant with respect to the evaluation function of the program in use. From the mid 1990's on, several good screen layouts for k-best game tree search have been realized. See the seven examples below.

Program for game

Program

A report on the k-best-visualisations was published in the

p.182 p.183 p.184 p.185 p.186 p.187 p.188 p.189

Keep in mind that this report was written before the upcoming of Monte Carlo game tree search.

Feel free to contact Ingo Althöfer when you know about other nice realizations of k-best game tree search.

Back to the main site of Ingo Althöfer