Utente:Darkice01/B*

In Informatica, B* (si pronuncia "B star" in inglese) è un algoritmo di ricerca best-first su grafi che trova il percorso che ha costo minore dato un nodo iniziale ed un qualsiasi nodo obiettivo. Pubblicato per la prima volta da Hans Berliner nel 1979, è legato all'algoritmo di ricerca A*.

Sommario

Per i nodi dell'albero l'algoritmo memorizza intervalli di valori stimati, invece che singoli valori. Inoltre i nodi foglia dell'albero possono essere inclusi nella ricerca finché uno dei valori di livello superiore non contiene un intervallo nettamente "migliore".

Dettagli

Intervalli invece di Singoli Valori

I nodi foglia di un albero B* rappresentano intervalli invece che singoli valori. Si suppone che l'intervallo contenga il vero valore del nodo. Se tutti gli intervalli associati ad un nodo soddisfano questa proprietà, allora B* identificherà un percorso ottimale verso il nodo obiettivo.

Processo di Risalita

Per far risalire gli intervalli all'interno dell'albero, l'estremo superiore del nodo padre è pari al massimo estremo superiore dei figli. L'estremo inferiore del nodo padre è ugualmente settato al massimo degli estremi inferiori dei figli. Nota che un padre può avere più figli.

Terminazione della ricerca

B* systematically expands nodes in order to create "separation," which occurs when the lower bound of a direct child of the root is at least as large as the upper bound of any other direct child of the root. A tree that creates separation at the root contains a proof that the best child is at least as good as any other child.

In practice, complex searches might not terminate within practical resource limits. So the algorithm is normally augmented with artificial termination criteria such as time or memory limits. When an artificial limit is hit, then you must make a heuristic judgment about which move to select. Normally, the tree would supply you with extensive evidence, like the intervals of root nodes.

Expansion

B* is a best-first process, which means that the whole tree is kept in memory, and repeatedly descended to find a leaf to expand. This section describes how to choose the node to expand.

At the root of the tree, the algorithm applies one of two strategies, called Prove-Best and Disprove-Rest.

Prove-Best

In the Prove-Best strategy, the algorithm selects the node associated with the highest upper bound. The hope is that expanding that node will raise its lower bound higher than any other node's upper bound.

Disprove-Rest

The Disprove-Rest strategy selects the child of the root that has the second-highest upper bound. The hope is that by expanding that node you might be able to reduce the upper bound to less than the lower bound of the best child.

Strategy Selection

Note that applying the Disprove-Rest strategy is pointless until the lower bound of the child node that has the highest upper bound is the highest among all lower bounds.

The original algorithm description did not give any further guidance on which strategy to select. There are several reasonable alternatives, such as expanding the choice that has the smaller tree.

The Maven (Scrabble) program contains an innovative strategy. Maven chooses Prove-Best as long as the lower bound of the node having the highest upper bound is not the highest lower bound. Then Maven alternates between Prove-Best and Disprove-Rest. This policy completes the proof in at most twice the minimal number of expansions, and seems to work well in practice.

Strategy Selection at Non-Root Nodes

Once a child of the root has been selected (using Prove-Best or Disprove-Rest) then the algorithm descends to a leaf node by repeatedly selecting the child that has the highest upper bound.

When a leaf node is reached, the algorithm generates all successor nodes and assigns intervals to them using the evaluation function. Then the intervals of all nodes have to be backed up using the the backup operation.

When transpositions are possible, then the back-up operation might need to alter the values of nodes that did not lie on the selection path. In this case, the algorithm needs pointers from children to all parents so that changes can be propagated. Note that propagation can cease when a backup operation does not change the interval assocated with a node.

Robustness

If intervals are incorrect (in the sense that the game-theoretic value of the node is not contained within the interval), then B* might not be able to identify the correct path. However, the algorithm is fairly robust to errors in practice.

The Maven (Scrabble) program has an innovation that improves the robustness of B* when evaluation errors are possible. If a search terminates due to separation then Maven restarts the search after widening all of the evaluation intervals by a small amount. This policy progressively widens the tree, eventually erasing all errors.

Extension to Two-Player Games

The B* algorithm applies to two-player deterministic zero-sum games. In fact, the only change is to interpret "best" with respect to the side moving in that node. So you would take the maximum if your side is moving, and the minimum if the opponent is moving. Equivalently, you can represent all intervals from the perspective of the side to move, and then negate the values during the back-up operation.

Applications

Andrew Palay applied B* to chess. Endpoint evaluations were assigned by performing null-move searches. There is no report of how well this system performed compared to alpha-beta pruning search engines running on the same hardware.

The Maven (Scrabble) program applied B* search to endgames. Endpoint evaluations were assigned using a heuristic planning system. This program succeeded splendidly, establishing the gold standard for endgame analysis.

The B* search algorithm has been used to compute optimal strategy in a sum game of a set of combinatorial games.

References

• Hans Berliner, [http://dx.doi.org/10.1016/0004-3702(79)90003-1 The B* Tree Search Algorithm. A Best-First Proof Procedure.], in Artificial Intelligence, vol. 12, n. 1, 1979, pp. 23–40, DOI:10.1016/0004-3702(79)90003-1.
• S. J. Russell, Norvig, P., Artificial Intelligence: A Modern Approach, Upper Saddle River, N.J., Prentice Hall, 2003, pp. 188, ISBN 0-13-790395-2.
• Brian Sheppard, [http://dx.doi.org/10.1016/S0004-3702(01)00166-7 World-championship-caliber Scrabble.], in Artificial Intelligence, vol. 134, n. 1-2, 2002, pp. 241–275, DOI:10.1016/S0004-3702(01)00166-7.

See also

• B*-tree