Dan Hagen

From this thread.

In a typical AI routine, the computer looks at the current state of the game, and considers all the possible next steps that could happen, over some period of time (or moves, if it’s turn-based). This is sometimes called “state space search”. By considering all permutations it can decide what the best next move should be (i.e., the one that results in the best possible outcome given the opponent’s possible moves).

Some algorithms use a pruning technique to make the problem space easier (e.g., only considering some alternatives). But the process is still the same.

The issue is that you need to search as deeply as possible into the future, but there’s a fan effect in which the possible permutations increases nonlinearly over time. That kind of sucks if the human opponent is sitting there waiting for the computer’s next move.

So the computer budgets a certain amount of time to decide what to do next. A fast processor can look deeper into the problem space (set of possible outcomes) before that time runs out.

—–

It’s quite a simple explanation. If AI makes decisions in real-time, meaning that time constraints are factored in the decision-making process, then having a faster CPU will result in better decisions made by the AI.

As an analogy, consider the lightbulb testing problem, where you are to test how durable a lightbulb is by dropping it out of various stories of an n story building. You want to find out the lowest story (LS) at which the lightbulb breaks, and the measure of how well you perform this task is by how many lightbulbs you break in the course of finding this story LS. So, if the LS is 50, and you drop the lightbulb at 49, that is not considered a broken lightbulb, and every story dropped above 50 results in a broken lightbulb. The ideal broken lightbulb count is therefore 1.

There are many ways to approach this problem. The most obvious one is to start on the first story, and work your way up one story at a time, until the lightbulb breaks; then you have found LS. But, say each lightbulb drop incurs a time penalty, because it takes time to travel to a floor, as well as to drop the lightbulb. If you are constrained by time, you might not be able to use this algorithm, because you might have to try all n stories to discover an LS of n.

So, we can already see how increased processing speed will improve an AI’s performance. If an AI were to solve this problem under time constraints, it can choose which method of finding the LS to minimize the number of broken lightbulbs based on how much time it is given, and its processing speed.

Note that the fastest way to discover LS is by binary search, that is, try n/2, and if it breaks, try n/4, and if it breaks, try n/8 etc., more colloquially known as divide and conquer. This results in “poor performance” (many broken lightbulbs), but is bounded by log2(n), i.e. it will find LS in at most log2(n) attempts.

Alternate “algorithms” exist which trade-off time and performance in different ways. You can bound performance to two broken lightbulbs by starting at story sqrt(n), and going to 2sqrt(n), 3sqrt(n) etc. until the first lightbulb is broken, and then trying the sqrt(n) stories in between the last and second-last attempts one by one until LS is found. This guarantees a performance metric of 2 and a time metric of 2sqrt(n)-1 attempts. An AI which decides what algorithm to use based on time constraints might use a variation of this algorithm to discover LS given an amount of time.

I already answered this before but I’ll say it again, you’ve got to be kidding me. I’ve been further even more decided to use even go need to do look more as anyone can. Can you really be far even as decided half as much to use go wish for that? My guess is that when one really been far even as decided once to use even go want, it is then that he has really been far even as decided to use even go want to do look more like. It’s just common sense.

I decided to use even go want to do look more like before it was cool to use even go want to do look more like. I have even really been far even as decided to use even go want to do look more like, that I stopped doing look more like a long time ago, and now I just use even go want to do look more like with scissors, a box set of Kenan & Kel on DVD, a 4 gigabyte SD card, and a frayed ethernet cable.

I hope this is really been far to do more answers for you to even go want.