# Bounding function for branch-and-bound in game tree search

The scenario is a game where each round you can buy or sell farms that make a set profit each round. I thought about applying branch-and-bound to a game tree, where each node represents the game state after each round, after buying/selling. The heuristic function I imagined is an estimate of how much money can be made "doing nothing from now" and in my case is an increasing function of depth. To my understanding, the branch-and-bound algorithm is, after initializing the queue with the initial game state, repeatedly pop a node off and branch if the bounded node heuristic value is better than an established lower bound (for a maximization problem).

From reading an overview of branch-and-bound, the bound is supposed to be a provable upper bound, but how can this actually be proved for a complex game? Instead, are the following simple bound methods I came up reasonable?

• Compute the bound as the heuristic value discounted by a fixed fraction, say 0.8, to encourage exploring locally suboptimal branches. If the bound is simply set to the heuristic value at the node, is this simply a greedy search?
• Instead of a fixed bounding function, consider best-first and limit the queue size to prevent considering too many nodes. But the runtime seems difficult to calculate to me as it's highly dependent on the structure of the tree and the order in which nodes are considered.

Also, if best-first is used with an increasing heuristic function, will this act like a depth-first search, since the first path chosen is increasing?

• Normally the bound is found by solving a linear relaxation of your mixed integer model. The solution to the linear relaxation usually won't be feasible under the integer constraints (if it is, you can skip branching altogether), but its optimal cost will be at least as good as any feasible integer solution. Sep 16, 2022 at 19:55
• @BenVoigt the bound is not necessarily computed by a linear relaxation. For example, for a graph coloring problem, a bound can be obtained by finding a clique Sep 17, 2022 at 7:14
• @fontanf: Sure, convex or other relaxations can also be used. But the linear relaxation is the most common, especially for one being introduced to the topic. Sep 19, 2022 at 14:45