Since you don't get to make the decision about what the opponent's moves will be, the methods for searching AND-OR trees is very different from that of OR trees. While in OR trees, the goal was to search the tree and find a solution, or the best solution, or the shallowest solution, the goal in AND-OR trees rarely involves finding a solution. This is because the size of the tree is generally much larger than that of typical OR trees, so searching the whole tree isn't feasible.
Instead, searching an AND-OR tree typically consists of looking forward some fixed number of moves, evaluating the state of the game at each possible state at that depth, and then propagating those values back up the tree to decide what is the best move to do now. Writing an evaluation function to tell you how beneficial a particular state of the game is for you is often quite difficult, but there is a very simple algorithm (family of algorithms, actually) for propagating the values back up the tree. This is the minimax algorithm.
Let's consider the game tree for the 5 stone version of NIM. Here I'll be using [VAL] to represent a max node and (VAL) to represent a min node:
 ----/\---- / \ (4) (3) / \ / \ / \ / \     / \ / \ / \ | (2) (1) (1) (0) (1) (0) (0) / \ | | |      | (0)In this tree, if it's your move and the value is 0, then that node indicates a loss for you. Thus, if you're max, then you can label each of the terminal nodes as wins or losses:
 ----/\----- / \ (4) (3) / \ / \ / \ / \     / \ / \ / \ | (2) (1) (1) (0) W(1) (0)W (0)W / \ | | |  LLL L | (0)WTo propagate these values back up the list, there's only two simple rules to remember: