1
$\begingroup$

I thought of the following algorithm for game AI, which is kind of a mashup of miniMax and Monte Carlo Tree Search. We assume that we have a heuristic function that assigns game states a value in the range $[0,1]$. (The heuristic is from the point of view of the player who just moved.)

The algorithm works as follows:

  1. Start with a tree whose only node is the root. Assign it a heuristic value.
  2. Traverse down the tree using UCT.
    • That is, when at a expanded node $n$, we select a child $c$ such that $\operatorname {value}(c) + E \sqrt{\frac{\ln d_n}{d_c}}$ is maximized, where $d_x$ is the total number of descendants of node $x$ (including itself). ($E$ is a tuneable constant corresponding to exploration.)
  3. When we reach a leaf node, we add each of its children in the game tree to this algorithm's tree. We assign each of the children a heuristic value, and forget the parent's heuristic value.
  4. Next, we assign each node in the tree its minimax value, according to the nodes currently in the tree and the heuristic values of the leaf nodes. Note that only the ancestors of the expanded leaf node should be affected, so this should be a quite update.
    • In particular, a node's value is equal to $\max_{c\in\text{children}}(1-\operatorname{value}(c))$, so it is kind of like negaMax.
  5. If time and space is left, go back to step 2. Otherwise, continue to step 6.
  6. Choose the child with the highest value, since this will give the moving player the best value.

The idea is that we are searching down the search tree progressively, using UCT to focus on good nodes that haven't been explored much yet. Unlike MCTS though, we use the minimax values instead of statistics to evaluate nodes.

Is there an algorithm similar to this already? I found SSS* which seems kinda similar, but I'm not sure, since I haven't found a good description of SSS*.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.