Minimum Proof Graphs and Fastest-Cut-First Search Heuristics

1 Introduction

Alpha-Beta [Knuth and Moore, 1975] search is the classic heuristic search algorithm for two-player games with perfect information. In past decades AI researchers have found numerous enhancements that, for instance, enable today's chess programs to defeat human World-champions at chess running on ordinary computers. Alpha-Beta improvements usually aim at decreasing the search effort given a fixed task such as searching up to a certain depth, or shaping the search tree to reduce heuristic evaluation errors. In this paper we focus on the Minimum Proof Graph problem that asks, given a DAG G corresponding to the states in a 2-player zero-sum game, a player labeling for each state denoting which player is to act, and a score function for each terminal state, what is the minimum number of vertices needed in a subgraph H ⊆ G in order to prove one of the following properties:

• (i) Can the first player achieve a score of at least t, for some integer t? This assumes that the first player only seeks
• to achieve a score ≥ t, and the second player tries to prevent this.
• (ii) What is the minimax value of the game? This assumes both players seek to maximize their numerical score.

[Knuth and Moore, 1975] answered question (ii) above in the context of homogeneous trees with constant branching factor b and depth d: searching b⌈d/2⌉ + b⌊d/2⌋ - 1 leaves is necessary and sufficient for establishing the minimax value of such trees. But as [Plaat et al., 1996a] note, trees are rarely homogeneous in practice, and in fact, inputs usually are not even trees, but DAGs. For the purpose of judging how close programs for popular games - such as chess, checkers, and Othello - come to searching minimum proof graphs, they introduce the concepts of Left-First-, Real-, and ApproximateReal-Minimal-Graphs, and estimate upper bounds on minimal proof graphs from game data.

In this paper we approach the problem more formally by first proving some fundamental properties of proof graphs. We then proceed to show that computing minimum proof graphs for DAGs is NP-hard and minimum proof trees for trees can be constructed in linear time. In the second half of the paper we will describe fastest-cut-first search heuristics which we evaluate using a novel synthetic game tree model.

2 Proof Graph Definitions

We shall assume throughout that G = (V, E) is a DAG with vertex set V = {v0, v1, . . . , vn-1} corresponding to states in the original game, and directed edge set E corresponding to legal moves from each state. Let p define the player function which maps vertices in V to {white,black}, and let f be the score function which maps terminal vertices to an integer.

Corresponding to the two properties being proven, we define two classes of decision problems. The first class is a tuple 〈G, p, f, s, t〉 which asks whether a proof graph exists using at most s nodes to prove that the first player can achieve a score of at least t. The second class is a tuple 〈G, p, f, s〉 which asks whether a proof graph exists using at most s nodes to prove the minimax value of the game. To clarify which type of proof graph we are referring to, we shall use the terms target proof graph and minimax proof graph respectively.

In both cases we require that accepted instances of the decision problems satisfy the condition that only one vertex of G, which we shall call the root, has in-degree 0. Without loss of generality we shall assume that v0 is the root and that p(v0) = white, such that white is the first player, and that the player to move alternates.

For convenience we introduce the indicator function

We also denote the children of a vertex using c(vi) = {vj : (vi, vj) ∈ E}.

Note that the minimax value may be computed recursively in time linear in the size of G. As such, we extend f to be defined over all vertices, rather than only the leaves, where f is now the negamax value of a vertex. Due to the zero-sum nature of the problem we may simplify our analysis by using a negamax perspective (where score is given w.r.t. the player to move) rather than minimax. Specifically, if c(vi) ̸= ∅ then f(vi) = max vj∈c(vi) I(vi, vj) · f(vj). For brevity we will use fu(v) := I(u, v) · f(v) to refer to the value of a vertex v with respect to some other vertex u, usually v's parent.

2.1 Target Proof Graphs

A subgraph H ⊆ G is a valid target proof graph if and only if all the following hold:

• v0 ∈ H
• (vi ∈ H and p(vi) = p(v0) and c(vi) ̸= ∅) ⇒ ∃vj ∈ c(vi) such that vj ∈ H
• (vi ∈ H and p(vi) ̸= p(v0)) ⇒ c(vi) ⊂ H

For a given target proof graph H, let

This function corresponds to the proven value of each vertex.

Definition 1. MinProofGraph-1 is a set of succinct encodings of 〈G, p, f, s, t〉 where there exists a subgraph H ⊆ G corresponding to a valid target proof graph such that f (H) (v0) ≥ t, and such that |H| ≤ s.

2.2 Minimax Proof Graphs

The evaluation of a minimax proof graph is slightly more involved than for a target proof graph as it depends on the concept of Alpha-Beta pruning. Specifically, the order in which a vertex's children are evaluated can affect the size of their proof graphs. This is due to more effective search cutoffs as the range of potential values for a node (and thus its ancestors) is reduced. It should be noted that verifying a minimax proof graph can be done in polynomial time even without explicitly giving the order in which to evaluate a node's children. This follows from results which will be presented in Sec. 3, specifically that an optimal traversal will only examine vertices using one of three possible α-β pairs.

For concreteness we will now define an indicator function to specify whether, for a vertex in a given minimax proof graph, the proof is accepted. First, for a vertex sequence σ of children, let αj be the highest possible alpha bound resulting from examining the first j nodes in σ, given the (potential) proof graph H ⊆ G. Now let μ(H) (α,β) (vi) = true iff:

• (i) vi ∈ H is a leaf, or
• (ii) ∃σ, a permutation of c(vi), such that ∀ 1≤j≤|c(vi)| either:

These conditions correspond to having an ordering to explore a node's children such that the α-β bounds at any point are sufficient to prove the next child's minimax value using the vertices in H, or for the bounds to short-circuit further child evaluations by causing a cutoff, which occurs when beta ≤ alpha indicating that the values of a parent's remaining children will provably not affect the game's minimax value. A subgraph H ⊆ G is a valid minimax proof graph if and only if v0 ∈ H and μ(H) (-∞,∞) (v0) = true.

Definition 2. MinProofGraph-2 is a set of succinct encodings of 〈G, p, f, s〉 where there exists a subgraph H ⊆ G corresponding to a valid minimax proof graph such that |H| ≤ s.

3 Minimum Proof Graph Properties

We will now proceed to make some observations which will simplify the computation of a minimax proof graph, assuming that we know the true values of each vertex.

Theorem 3.1. For an Alpha-Beta examination of a vertex v with α < β ≤ f(v) or f(v) ≤ α′ < β′ , the size of the minimum proof tree rooted at v is independent of α and β′ .

Proof. We proceed by induction on the height of v, the maximum path length starting from v. Clearly the observation holds for a height of 0, where v is a leaf and has no children. Now assume the observation holds for all heights less than or equal to some n, and that v has height n+1 (clearly all of v's children have height ≤ n).

First consider the case where α < β ≤ f(v). The examination of v must end with a cutoff where a child is proven to have a value of at least β. Call such a child cutting. Note that examining a child with value < β (so as to improve the alpha bound) cannot reduce the effort required to prove a cutting child w. To see this observe that α < β ≤ fv(w) ≤ f(v) and so w will be examined with f(w) ≤ -β < - ˜α, where ˜α is some (potentially) improved alpha bound.

By the induction hypothesis, in neither case does the minimum proof graph size for w depend on α. As such, the minimum proof graph for v will consist of examining only one cutting node, and therefore also does not depend on α.

Now consider the case where f(v) ≤ α < β. Since no child can have a value greater than f(v), the alpha bound can never be improved, and all children must be examined. The argument that the induction property holds for n + 1 is the same as in the first case, except now ˜α = α.

Thus, by induction, the observation holds for all n.

Theorem 3.2. For an Alpha-Beta examination of a vertex v the following properties hold:

• (i) α ≤ f(v) < β ⇒ the MPG size does not depend on β.
• (ii) α < f(v) ≤ β ⇒ the MPG size does not depend on α.

(iii) α ≤ f(v) ≤ β, α < β ⇒ ∃ w ∈ c(v) to examine first which minimizes the proof graph size and fv(w) = f (v).

Proof. We again proceed by induction on the height of v, for which the listed properties clearly hold for a height of 0 i.e., v being a leaf. Now assume the properties holds for all heights less than or equal to some n, and that v has height n + 1.

Property (i): Since f(v) < β all children of v must be examined. Note that α can never become larger than f(v) so the initial constraint that α ≤ f(v) < β holds at each step. For any child w ∈ c(v) we have that fv(w) ≤ f(v). Now, either fv(w) ≤ α < β or α < fv(w) < β. In the first case the MPG size is independent of β by Theorem 3.1. In the second case the induction hypothesis gives the desired result, using either (i) or (ii) depending on if p(v) = p(w).

Property (ii): If we can show that the MPG size to examine any child w with fv(w) = f (v) does not depend on the initial value of α (as long as α < f(v)) then we are done, since all other nodes can be examined afterwards, and the tighter bound can only decrease the size of those nodes' MPG. Let w ∈ c(v) be such that fv(w) = f(v) and α < f(v), which implies α < fv(w) ≤ β. By the induction hypothesis (part (i) or (ii), depending on ownership) the MPG size of w does not depend on α.

Property (iii): The preconditions of property (iii) match those of (i) or (ii) (or both). In the case of (i), as noted in its proof, the child ordering does not affect the MPG size, so simply take w to have fv(w) = f(v), as at least one such w exists. In the case of (ii) it is never suboptimal to examine such a w first, and as at least one child must minimize the proof graph, take w to be that one. Hence (iii) holds. Thus, by induction, the properties hold for all n.

Based on Theorem 3.2 we may assume that the initial path from the root to a leaf follows an optimal line of play, the principle variation (PV), such that all nodes w along the path have value fv0 (w) = f(v0). Clearly this initial path will be explored using bounds 〈α, β〉 = 〈∞,-∞〉. There may be many optimal lines of play, but for clarity we shall assume that the PV refers to some fixed initial path in an MPG.

Theorem 3.3. For an Alpha-Beta examination of a DAG G that minimizes the proof graph size, it will be the case that for each v ∈ G not on the PV, with initial bounds α and β:

• (i) 〈α, β〉 ∈ {〈±f(v0),∞〉, 〈-∞,±f(v0)〉}

(ii) 〈α, β〉 = 〈-∞, f(v0)〉 ⇒ f(v) ≥ f(v0) (iii) 〈α, β〉 = 〈-∞,-f(v0)〉 ⇒ f(v) ≥ -f(v0) (iv) 〈α, β〉 = 〈 f(v0), ∞〉 ⇒ f(v) ≤ f(v0) (v) 〈α, β〉 = 〈-f(v0), ∞〉 ⇒ f(v) ≤ -f(v0)

The proof is omitted for space, but is a straight-forward casebased analysis which proceeds by induction on the maximum distance, n, from the principle variation that a vertex may be.

4 NP-Completeness Results

In this section we show that determining the inclusion of an element in MinSetCover, which is NP-complete, can be reduced to determining the inclusion of an element in MinProofGraph-1 or to determining the inclusion of an element in MinProofGraph-2.

Sahni has shown that computing a minimum proof for an AND/OR tree (which is equivalent to MinProofGraph-1) is NP-Complete[Sahni, 1974]. To help illustrate the source of the complexity we present a slightly different reduction.

To see that MinProofGraph-1 is in NP, observe that a valid proof graph H ⊆ G is a sufficient certificate. H is clearly polynomial in the size of the original input, and all constraints listed in Section 2 corresponding to H being valid are easily checked in polynomial time along with computing f (H) (v0). By a similar argument MinProofGraph-2 is in NP.

In preparation for proving that all problems in NP can be polynomial-time reduced to MinProofGraph-1 and MinProofGraph-2 we introduce the following definition for the Minimum Set Cover problem:

Definition 3. MinSetCover is a set of succinct encodings of 〈X, S, k〉 where X is a finite set, and S is a collection of subsets of X such that there exists S ′ ⊆ S where |S ′ | ≤ k and X = ∪ T ∈S′T .

Theorem 4.1. MinSetCover ≤p MinProofGraph-1 and MinSetCover ≤p MinProofGraph-2.

Corollary 4.2. MinProofGraph-1 and MinProofGraph-2 are NP-complete.

Proof. We describe a function F that maps arbitrary code words w into the encoding of an associated MinProofGraph-1 instance with the following properties:

• (i) If w encodes a MinSetCover tuple 〈X, S, k〉, then 〈X, S, k〉 ∈ MinSetCover if and only if F(w) ∈ MinProofGraph-1.
• (ii) Otherwise, F(w) encodes a fixed tuple not in MinProofGraph-1.
• (iii) There exists a Turing machine F and a polynomial p such that for all w, F started on input w computes F(w) in at most p(|w|) steps.

Given an element of Minimum Set Cover 〈X, S, k〉 consisting of X = {x0, . . . , xn-1} and sets S = {S0, . . . , Sm-1}, let F(〈X, S, k〉) = 〈G, p, f, s, t〉. F constructs a graph with four levels corresponding to the root node t, a dummy node u, the elements of X (v0, . . . , vn-1), and the elements of S (w0, . . . , wm-1), as in Figure 1. Let the edge set be {(t, u), (u, vi) : 0 ≤ i < n} ∪ {(vi,wj) : xi ∈ Sj}. Let p(t) = p(vi) = white and p(u) = p(wi) = black, with white nodes having value 1 and black nodes having value -1. Finally, let t = 1 and s = 2 + n + k.

We now show that 〈G, p, f, s, t〉 is accepted if and only if 〈X, S, k〉 is accepted. Any solution to the MinProofGraph-1 instance will include the first three levels and some fourth level nodes. By definition the minimum number of fourth level nodes will be included, and as each third level vi node has at least one associated fourth level wj node, the fourth level nodes chosen correspond to a subset of S which forms a minimum set cover of X.

The proof for MinProofGraph-2 being NP-complete is almost identical, except that two new vertices are required as shown in Figure 1. In the minimax case at least one third level node must have all its children examined, but after that, due to the given node values, all other third level nodes need only examine any one of their children to produce a cut. As the new vertices must necessarily be included in any proof subgraph, we can assume that they are examined before the other vertices on their levels.

5 Minimum Proof Graphs for Trees

Intuitively, the computational complexity of finding minimum proof graphs in the presence of nodes with in-degree ≥ 2 arises from deciding whether to choose the proof graph rooted at a "larger" child over the proof graph rooted at a smaller child, such that the proof for the larger child may be reused in a different portion of the graph, resulting in a smaller overall proof graph. As we will see in this section, for trees the minimum proof graph is itself a tree which can be computed bottom-up in linear time. We distinguish between computing target and minimax proof trees.

5.1 Computing Target Proof Trees

For a MinProofGraph-1 instance 〈G, p, f, s, t〉 we may restrict the vertices of G that need to be considered by removing all white vertices vi such that f(vi) < t and then removing components disconnected from the root as a preprocessing step in O(|V | + |E|) time. If f(v0) < t then the instance is rejected.

To compute the minimum target proof graph size one need only recursively determine this value for the subgraph rooted at each vertex. For first player nodes this is the minimum over the sizes of the child proof graphs plus 1. For second player nodes this is the sum of the sizes of the child proof graphs plus 1. Extracting an associated minimum target proof graph is clearly trivial.

5.2 ComputingMinimax Proof Trees

The Alpha-Beta algorithm has been well studied in the case of trees [Knuth and Moore, 1975], and it has been stated that the best-case move ordering is to examine children in

Function MPT size(v, α, β) Data: subtree root vertex v ∈ V (G), and α-β bounds. Result: Min. proof tree size for subtree rooted at v, given α, β. begin if α ≥ β then return 0 if c(v) = ∅ then return 1 // leaf node alias Tw[a, b] := MPT size(w, -b, -a) Assume MPT size values are memoized across calls. if f(v) ≤ α then return 1+ P w∈c(v)Tw[α, β] if f(v) ≥ β then return 1 + min w∈c(v) fv(w)≥βTw[α, β] t ← P x∈c(v)Tx[f (v), β] // compute total return 1 + min w∈c(v) fv (w)=f (v) "Tw[α, β] + t - Tw[f (v), β]" end

order of decreasing score. This does not, however, necessarily minimize the total proof tree size in the case of multiple best moves, where "best" refers to either absolute numerical score or ability to generate a cut. Using Theorem 3.3 we can see that there are at most three possible incoming bounds with which a given vertex can be explored in a minimal proof tree (MPT). We may thus compute, bottom-up, a table containing the MPT size for each vertex given the incoming α-β bounds. This process therefore runs in linear time and space in the graph size. Moreover, the table entries need only be computed as needed, and the set of potential best moves is easily constrained using the observations from Theorem 3.2's proof. The algorithm is listed in Figure 2, and the size of the minimum minimax proof tree is the result of MPT size(v0,-∞,∞). The runtime and space requirement is linear in the input graph size and adjusting the algorithm to actually contruct an MPT is straight-forward.

6 Fastest-Cut-First Heuristics

In this section we develop a move sorting heuristic for AlphaBeta search based on the results on minimum proof graphs we have presented. In real-world game applications, usually none of the quantities used in MPT size are known at the time when the decision about the next move to be searched is to be made. One therefore has to resort to move ordering heuristics. In addition, search is often performed in DAGs, which complicates the computation of minimum proof graphs. Even so, if estimates for values and sizes are available, we could base move decisions on those, and hope to approximate minimum proof graphs sufficiently well. This idea is not new. Plaat et al. [1996], for instance, suggest to use enhanced transposition table look-ups and bias moves towards those with small subtrees, to exploit properties of inhomogeneous DAGs, such as varying out-degrees and leaf depths. Closer in terms of using both value and size estimates comes what is known since the mid-1990s as

"fastest-first" search in the Othello programming community. The idea is to search moves first that have a considerable chance to produce a cutoff, and among those to prefer moves with small sub-DAGs. Employing such heuristics has improved Othello endgame solvers considerably (http: //radagast.se/othello).

Because both move values and DAG sizes are taken into account we prefer to call heuristics of this type "fastest-cutfirst" heuristics. Implementations we have used successfully in the past include sorting moves according to (Vi - C · Si/ maxj Sj ), where Vi and Si are the estimated move values and sub-DAG sizes, and C > 0 is a constant. Alternatively, moves can be restricted to those with Vi ≥ β - C and from this set a move with minimal size estimate is selected.

Here, we propose a new fastest-cut-first heuristic which is motivated by the following theorem:

Theorem6.1. Consider a naive version of Alpha-Beta search that does not adjust α based on returned values and searches a game tree starting at cut-node v with successors v1, . . . , vn. Let Si be the expected size of the subtree rooted at vi, and Pi the probability of move i leading to a β-cut. Then, visiting vi in ascending order of Si/Pi minimizes the expected number of visited nodes starting at v.

Proof. For move ordering (1, . . . , n) the expected number of visited nodes is

for π := k-1 ∏ j=1 (1 - Pj ) and suitable A > 0 and C ≥ 0.

Switching move k and k + 1 leads to expected search effort

Thus, if π > 0 searching move k + 1 before k while keeping the other moves' ordering constant is not detrimental iff

where we define c/0 := ∞ for c > 0 to cover the cases Pk = 0 and/or Pk+1 = 0. If π = 0, switching moves k and k + 1 does not change the expected search effort. This shows that when starting with an arbitrary move ordering we can continue switching moves k and k+1 for which (1) holds and not increase the expected search effort. Therefore, the expected number of searched nodes is minimized when visiting nodes vi in ascending order of Si/Pi.

Picking the move with the lowest Si/Pi ratio first accomplishes the goal of producing a cut with high probability, while keeping the node count low, in a principled way, unlike the ad-hoc fastest-cut-first heuristics presented earlier. The expected number of searched nodes established in the theorem is an upper bound on the actual number of nodes the true Alpha-Beta algorithm would visit, because with rising

α values, the expected tree sizes Si do not increase. So, by minimizing this number we can hope to decrease the AlphaBeta search effort - also when searching DAGs. We will present experimental results on the performance of the novel fastest-cut-first heuristic in Section 8.

7 Prefix Value Game Trees

In this section we present a synthetic game tree model that we will use to gauge the performance of the fastest-first heuristic we proposed in the previous section.

Search algorithm improvements are often driven by specific applications. A classic example is the development of forward pruning and parallelization in computer chess. When working in particular search domains, state space properties - such as the average branching factor, the density of terminal nodes, state value distributions and correlations - are fixed. To gain insight into how such properties generally affect search algorithms, several synthetic game tree models have been proposed in the literature, e.g., [Fuller et al., 1973; Newborn, 1977; Nau, 1982; Pearl, 1983; Kaindl and Scheucher, 1992; Scheucher and Kaindl, 1998], with emphasis on studying pathology in alpha-beta search.

In [Fuller et al., 1973] Fuller et al. describe a game tree model in which node value correlations are introduced by assigning values from {1, . . . ,N} to edges and assigning a value p(v) to leaves by summing up edge values along the unique path from the root node. One drawback of this socalled incremental game tree model is that values increase with depth and therefore don't have the usual interpretation as representing the expected payoff. In [Scheucher and Kaindl, 1998] this bias is offset first by considering move values from {-N, . . . ,N}, and then in a second step by realizing that playing a move can never increase a position's value, i.e.,

where p(x) denotes the accumulated value along the unique path when reaching node x in view of the player to move, vi is the i-th successor of v, and -D ≤ di(v) ≤ 0 is the bounded damage self-inflicted by playing move i in v. Figure 3 shows an example. To evaluate search performance it is useful to know exact values of intermediate states. However, in the above incremental model - when di is chosen randomly from [-D, 0] - searching entire subtrees is required to compute the true negamax value of interior nodes, which can be very costly in terms of space and time requirements. With a simple yet effective refinement of the incremental tree model, we are able to determine exact node values on the fly while generating trees. Being able to leak true state evaluations in interior nodes at no additional cost greatly helps analyzing search algorithms in general settings because no time has to be spent on engineering domain dependent heuristics. For instance, noise can be added when testing heuristics that depend on heuristic state evaluations of interior nodes, such as ProbCut [Buro, 1995], e.g., ˆ fC(v) = f(v) + C · e, where f(v) denotes the true negamax value of v and e is N(0, 1) normally distributed. In addition, move preferences can be leaked probabilistically by means of the parameterized softmax function

which spans the range from uniform random (C = 0) to perfectly informed choices (C → ∞) and can be used to design synthetic move sorting routines for alpha-beta search or playout policies for UCT [Kocsis and Szepesvari, 2006].

Before we formulate the observation our model refinement is based on, we define the prefix negamax value of a node and show how to compute it. W.l.o.g., we assume that moves are alternated from now on.

Definition 4. In the incremental game tree model the prefix negamax value p(v) of node v is defined recursively based on (2): If v is the root r of the tree, then p(v) = f(r). Otherwise, p(v) = -p(v′ )-di(v′ ), where v′ is the predecessor of v on the path to the root, v = v′i , and di(v′ ) ≤ 0.

Lemma 7.1. For the incremental game tree model described above

holds, where r is the root of the tree and u0, . . . , un is the unique path from r to v, i.e., u0 = r, un = v, and uk+1 is the ik-th successor of uk.

Proof. (Induction on depth n of v). For n = 0, we have v = r, so the statement trivially holds. Assuming (3) holds for nodes with depth n, consider the value of a node v′ at depth n + 1 with predecessor v and v′ = uin . Then:

Our refinement of the incremental game tree model is based on the following observation:

Theorem7.1. If for all interior nodes v in trees generated by the incremental model there exists a move i with di(v) = 0, then for all v, f(v) = p(v).

Proof. (Induction on node height h(v)). If h(v) = 0, then v is a leaf and f(v) = p(v) holds by definition. Now consider a node v with height n + 1 and suppose f(v′ ) = p(v′ ) holds for all v′ with h(v′ ) ≤ n. W.l.o.g., we assume d1(v) = 0. Among the p(vi) values, p(v1) is one of the smallest, because p(vi) = -p(v) - di ≥ -p(v) = p(v1) + d1(v) = p(v1). By the induction hypothesis we also know f(vi) = p(vi) for all i. Therefore, f(v) = maxi(-f(vi)) = maxi(-p(vi)) = -p(v1) = p(v) + d1 = p(v).

With this result, evaluating nodes while generating trees is trivial because (3) can be maintained incrementally. This property in invaluable for analysing search performance in large trees based on true node values. We call our refined model the "Prefix Value Game Tree Model". As usual, the number of successors and move values can either be fixed or sampled from distributions to better model real-world games. We will use prefix value trees to compare the performance of alpha-beta and fastest-first search in the next section.

8 Experiments

To investigate the effect on search effort resulting from the FCF heuristics, we constructed synthetic trees using various branching factors, edge value ranges, and heuristic evaluation errors. For each set of parameters we generated 500 trees and performed an iterative deepening (ID) search up to depth 10 using plain Alpha-Beta, NegaScout, and MTD(f) [Plaat et al., 1996b]. The expanded tree nodes were annotated with search information, such as estimated value and treesize, which was used for ordering the next ID iteration.

Our move ordering function is a weighted combination of the estimated node value, the Si/Pi value, and Si. For a given node we took Si to be its out-degree. Looking deeper in the node's subtree was actually slightly detrimental since, ideally, large portions of that tree will never actually be expanded during search. Moreover the out-degree is 'free' to compute, given that we have expanded the node anyway. The value of Pi is initially a hard threshold based on whether the node value (from the last ID pass) is ≥ beta. Computing Pi empirically by "training" on trees from the same generating family produced a slight (∼3%) improvement. The ordering of child nodes which have not yet been expanded is random.

In addition to synthetic trees we used FCF heuristics in solving open-handed cardplay for the trick-taking German card game Skat described in [Buro et al., 2009]. Our search implementation sorts moves by way of a linear combination of features corresponding to the current value of a trick and the ability of teammates to contribute points. Our search also employs various pruning techniques and a transposition table - no iterative deepening is performed. Our lack of a forward-looking state evaluation function for Skat precluded an easy way to measure expected value or Pi. As such, we include an FCF term in our linear combination by subtracting Si := the branching factor for each move, times C, a weighting term optimized independently. Results are shown in Table 1, with X being the portion of the move evaluation which does not consider tree size. Results are computed from 4000 initial cardplay positions from human games.

Performance results were consistent across the tree generation parameters, although the weights for combining heuristic components needed to be tuned. We made a best effort to determine the optimal weights in each case. In all cases, even when the node evaluation functions were given perfect accuracy, we observed a significant reduction in nodes expanded, compared to only using the estimated node value. Representative results are presented in Figure 4, which shows the cumulative number of search nodes expanded, including previous ID passes, relative to the MPG size. Values are averaged over 500 trees. The results shown are produced by trees with branching factor uniformly drawn from [4..12] at each node, evaluations errors drawn from [-4..4], and edge values drawn from [-6..0]. There was no significant difference in performance between using Si/Pi and Si as the FCF weighting term, with node reductions of 35% and 39% for NegaScout and MTD(f) respectively at depth 10. Note that the baseline MPG size grows exponentially with depth.

9 Conclusions and Future Work

In this paper we have presented properties of minimum proof graphs, NP-completeness results, and a linear-time algorithm for computing minimum proof graphs for trees. We also introduced the class of fastest-cut-first heuristics which sort moves dependent on sub-DAG size and value estimates. Our experimental results using a novel synthetic game tree model indicate that standard Alpha-Beta search algorithm gain exponentially when using fastest-cut-first heuristics for move ordering, but an exponential gap between the minimum proof tree size and the size of the trees visited by Alpha-Beta search remains. In future work we plan to investigate how to combine fastest-cut-first heuristics with other enhancements such as information stored in transposition tables.

Acknowledgments

Financial support was provided by NSERC.