---
title: "Leaf-Value Tables for Pruning Non-Zero-Sum Games"
authors:
  - "Nathan R. Sturtevant"
doi: ""
url: "https://ijcai.org/proceedings/2005/109"
pdf: "https://ijcai.org/proceedings/2005/0109.pdf"
venue: "Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence"
year: 2005
pages: "317-322"
track: ""
keywords:
---

# Leaf-Value Tables for Pruning Non-Zero-Sum Games

Nathan R. Sturtevant

*Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence*, pages 317-322.

## Abstract

Algorithms for pruning game trees generally rely on a game being zero-sum, in the case of alpha-beta pruning, or constant-sum, in the case of multi-player pruning algorithms such as speculative pruning. While existing algorithms can prune non-zero-sum games, pruning is much less effective than in constant-sum games. We introduce the idea of leaf-value tables, which store an enumeration of the possible leaf values in a game tree. Using these tables we are can make perfect decisions about whether or not it is possible to prune a given node in a tree. Leaf-value tables also make it easier to incorporate monotonic heuristics for increased pruning. In the 3-player perfect-information variant of Spades we are able to reduce node expansions by two orders of magnitude over the previous best zero-sum and non-zero-sum pruning techniques.