Bram Cohen recently started an interesting discussion about why computers are able to play chess well, and how chess could be made harder for them. One point that he and others tried to make is that the branching factor (number of possible moves at a given time) isn’t as important as conventional wisdom suggests. I’m sure that satisfies everyone’s desire to feel special by defying conventional wisdom, but it’s wrong for a reason that Bram himself hits on later:

an alpha-beta pruner is quite hopeless unless either its evaluation function is basically sound or the total number of possibilities is so small that it can exhaustively evaluate everything

In other words, the “branching factor doesn’t matter” argument is based on the idea that the branching factor is effectively lowered by the computer’s ability to ignore “uninteresting” moves…but Bram’s own observation shows how this might not necessarily be the case. What really matters is the number of positions the computer must evaluate, which is a function of both the branching factor and the usefulness of the evaluation function to facilitate pruning. This, I believe, is why some of the “anomalies” such as removing queens or allowing pawns to move backwards work the way they do. A change that increases the branching factor can still help the computer (apparently supporting the non-conformist view) if it also increases the effectiveness of pruning, and a change that decreases branching can hurt the computer if it makes pruning less effective. In fact, I’d reformulate Bram’s observation a little:

A pruner is quite hopeless any time the importance of a global evaluation function is reduced relative to separate goal-specific evaluations.

This is one of the things that makes Go hard – not just that the branching factor is so high to begin with, but that conventional pruning techniques don’t do much to reduce it. That’s why some of the most successful Go programs rely on evaluating several aspects of the game (e.g. tactical concerns, “shape” and connection/influence) separately. Generating several trees where pruning can be done effectively and then combining the results requires that fewer positions be evaluated than generating a single tree where pruning doesn’t work. This naturally points to a way to make games more difficult for computers to play: target the evaluation function. One of the reasons Arimaa might be more “computer-proof” than chess is that it has features that make global evaluation less useful, and there might be other ways to increase that effect. The downside, of course, is that any such game is only difficult for computers as they are currently programmed to play. When someone comes up with a good general way to deal with the problem of having to rely on several kinds of evaluation instead of just one, we’ll be back at square one (heh). The problem of how to make a game that’s permanently harder for computers to play is an entirely different one.