Abstract
Tzaar is an abstract strategy two-player game, which has recently gained popularity in the gaming community and has won several awards. There are some properties, most notably the high branching factor, that make Tzaar hard for computers.
We developed Waltz, a strong Tzaar-playing program, using enhanced variants of Alpha-beta and Proof-number Search based algorithms. After many tests with computer opponents and a year of deployment on a popular board-gaming portal, we conclude that Waltz can defeat all available computer programs and even strong human players.
In this paper we describe Waltz, its performance and an enhancement of Proof-number Search developed for Waltz that can be also used in other domains than Tzaar.