25 replies to this topic

[shurcool]

Is writing a quine just too easy for you? Then try your hand at the following simple programming challenge.

Write a short program that takes at least one hour of computational time (this can be a parameter if you want) to produce some interesting output. Pre-canned output is not interesting, nor does it take one hour to generate.

Edited by shurcool, 11 September 2012 - 01:34 AM.

[Bacterius]

On what hardware? Which languages are allowed? Define "interesting"? Otherwise, this Python program, complete with comments, will test the Collatz conjecture on every positive integer above and including the input, and print out the sequence obtained. If the conjecture is true, you'll never get into a cycle since the sequence function will always return. As Python has built-in arbitrary precision arithmetic, runtime is essentially infinite. I think the output is pretty damn interesting if you let it run long enough! Enjoy...

[source lang="python"]# Prints the Collatz sequence for pdef Collatz(p): # Print the initial number print(p) # Terminate when 1 is reached while p != 1: # If p is even, p -> p / 2 # Otherwise, p -> 3p + 1 if (p % 2 == 0): p = p // 2 else: p = 3 * p + 1 # Print the new number print(p)def ShurcoolChallenge(p): if (p < 1): print("Nice try.") return while True: print("### " + str(p) + " ###") Collatz(p) print("") p += 1[/source]

Sample output:

Spoiler

### 181 ###
181
544
272
136
68
34
17
52
26
13
40
20
10
5
16
8
4
2
1
### 182 ###
182
91
274
137
412
206
103
310
155
466
233
700
350
175
526
263
790
395
1186
593
1780
890
445
1336
668
334
167
502
251
754
377
1132
566
283
850
425
1276
638
319
958
479
1438
719
2158
1079
3238
1619
4858
2429
7288
3644
1822
911
2734
1367
4102
2051
6154
3077
9232
4616
2308
1154
577
1732
866
433
1300
650
325
976
488
244
122
61
184
92
46
23
70
35
106
53
160
80
40
20
10
5
16
8
4
2
1

Edited by Bacterius, 12 September 2012 - 03:05 AM.

[Erik Rufelt]

Test of randomness!

#include <ctime>
#include <cstdlib>
#include <iostream>
int main() {
  time_t startSeconds = time(0);
  time_t maxRunningTime = 3601;
  int maxValue = 7;
  int innerLoopCount = 1000000;

  srand(startSeconds);

  int lastRand = rand() % (maxValue + 1);
  int currentSeq = 1;
  int maxSeq = 1;
  long long iterationCount = 0;
  for(; time(0) < startSeconds + maxRunningTime; ) {
    for(int i = 0; i < innerLoopCount; ++i) {
	  int nextRand = rand() % (maxValue + 1);
	  if(nextRand == lastRand)
	    ++currentSeq;
	  else {
	    maxSeq = std::max(currentSeq, maxSeq);
	    lastRand = nextRand;
	    currentSeq = 1;
	  }
    }
    iterationCount += innerLoopCount;
  }

  std::cout << "Longest sequence of equals in " << iterationCount << " numbers in [0, " << maxValue << "]: " << maxSeq << std::endl;

  return 0;
}

Edited by Erik Rufelt, 12 September 2012 - 09:47 AM.

[Net Gnome]

simple cellular automata generator

using "babaabab" as the argument gives a nice pseudorandom output and you'll see triangle forms of 'b's appear in the chaos
"abbaabba" will also produce right-triangles, but with 'a's
"abbabbab" will produce clustered triangle 'b's

using System;
using System.Threading;
namespace TimedComp
{
class MainClass
{
  public static void Main (string[] args)
  {
   Foo foo = new Foo();
  
   foo.run(args);
  }
}

class Foo
{
  private static bool RUN = true;

  private string prev = "",cur = "";

  private int colLim = 80;

  private Timer timer;

  public void run(string[] args)
  {
   timer = new Timer(this.OnTick,null,1000*3600,0);
  
   prev = "aaaaaabaaaaaa";
   while(RUN)
   {
	for(int i = 0; i < prev.Length; i++)
	{
	 if(i+1 > prev.Length-1)
	 {
	  cur += prev[prev.Length-1];
	  break;
	 }
	
	 if(i > 0){
	
	  string str = "" + prev[i-1] + prev[i] + prev[i+1];
	
	  if(str == "aaa")
	   cur = cur.Insert(i,""+args[0][0]);
	
	  if(str == "aab")
	   cur = cur.Insert(i,""+args[0][1]);
	
	  if(str == "aba")
	   cur = cur.Insert(i,""+args[0][2]);
	
	  if(str == "abb")
	   cur = cur.Insert(i,""+args[0][3]);
	
	  if(str == "baa")
	   cur = cur.Insert(i,""+args[0][4]);
	
	  if(str == "bab")
	   cur = cur.Insert(i,""+args[0][5]);
	
	  if(str == "bba")
	   cur = cur.Insert(i,""+args[0][6]);
	
	  if(str == "bbb")
	   cur = cur.Insert(i,""+args[0][7]);
	 }
	 else
	 {
	  string str = "" + prev[i] + prev[i+1];
	
	  if(str == "aa")
	   cur = cur.Insert(i,""+args[0][0]);
	
	  if(str == "ab")
	   cur = cur.Insert(i,""+args[0][1]);
	
	  if(str == "ba")
	   cur = cur.Insert(i,""+args[0][2]);

	  if(str == "bb")
	   cur = cur.Insert(i,""+args[0][3]);
	 }
	}
	prev = cur.Substring(0, cur.Length > colLim ? colLim : cur.Length);
	Console.WriteLine(prev);
   }
  }

  private void OnTick(object obj)
  {
   RUN = false;
  }

}
}

here is some sample output of abbabbab with one triangle highlighted:

bbbbabbbbbbbababbbbbbbabababababbbbbbbbbbbabbbbbbabababbbbbbbabbbbbbababbbabaaba
abbababbbbbabbbabbbbbabbbbbbbbbabbbbbbbbbababbbbabbbbbabbbbbababbbbabbbababbbbbb
baabbbabbbababababbbababbbbbbbababbbbbbbabbbabbababbbababbbabbbabbabababbbabbbba
bbbababababbbbbbbababbbabbbbbabbbabbbbbabababaabbbababbbababababaabbbbbabababbab
ababbbbbbbabbbbbabbbabababbbababababbbabbbbbbbbababbbababbbbbbbbbbabbbabbbbbaabb
bbbabbbbbababbbabababbbbbababbbbbbbabababbbbbbabbbababbbabbbbbbbbababababbbabbaa
abababbbabbbababbbbbabbbabbbabbbbbabbbbbabbbbabababbbabababbbbbbabbbbbbbababaabb
bbbbbababababbbabbbababababababbbababbbababbabbbbbababbbbbabbbbababbbbbabbbbbbaa
abbbabbbbbbbababababbbbbbbbbbbababbbababbbaababbbabbbabbbababbabbbabbbababbbbabb
babababbbbbabbbbbbbabbbbbbbbbabbbababbbababbbbababababababbbaabababababbbabbabaa
bbbbbbabbbababbbbbababbbbbbbabababbbababbbabbabbbbbbbbbbbababbbbbbbbbbababaabbbb
abbbbabababbbabbbabbbabbbbbabbbbbababbbababaababbbbbbbbbabbbabbbbbbbbabbbbbbabbb
babbabbbbbabababababababbbababbbabbbababbbbbbbbabbbbbbbababababbbbbbababbbbababa
bbaababbbabbbbbbbbbbbbbababbbababababbbabbbbbbababbbbbabbbbbbbabbbbabbbabbabbbbb
aabbbbabababbbbbbbbbbbabbbababbbbbbbabababbbbabbbabbbababbbbbababbabababaababbbb
ababbabbbbbabbbbbbbbbabababbbabbbbbabbbbbabbabababababbbabbbabbbaabbbbbbbbbbabba
bbbaababbbababbbbbbbabbbbbabababbbababbbabaabbbbbbbbbababababababbabbbbbbbbabaaa
ababbbbababbbabbbbbababbbabbbbbababbbababbbbabbbbbbbabbbbbbbbbbbaababbbbbbabbbab
bbbabbabbbabababbbabbbabababbbabbbababbbabbababbbbbababbbbbbbbbabbbbabbbbabababa
ababaabababbbbbababababbbbbababababbbababaabbbabbbabbbabbbbbbbababbababbabbbbbbb
bbbbbbbbbbabbbabbbbbbbabbbabbbbbbbababbbbbbabababababababbbbbabbbaabbbaababbbbba
abbbbbbbbababababbbbbababababbbbbabbbabbbbabbbbbbbbbbbbbabbbabababbababbbbabbbab
babbbbbbabbbbbbbabbbabbbbbbbabbbababababbababbbbbbbbbbbabababbbbbaabbbabbabababa
bbabbbbababbbbbababababbbbbabababbbbbbbaabbbabbbbbbbbbabbbbbabbbabbababaabbbbbbb
aababbabbbabbbabbbbbbbabbbabbbbbabbbbbabbabababbbbbbbababbbabababaabbbbbbabbbbbb
abbbaababababababbbbbababababbbababbbabaabbbbbabbbbbabbbababbbbbbbbabbbbababbbba
bababbbbbbbbbbbbabbbabbbbbbbababbbababbbbabbbababbbabababbbabbbbbbababbabbbabbaa
bbbbabbbbbbbbbbababababbbbbabbbababbbabbabababbbababbbbbabababbbbabbbaabababaabb
abbababbbbbbbbabbbbbbbabbbabababbbababaabbbbbababbbabbbabbbbbabbabababbbbbbbbbab
baabbbabbbbbbababbbbbabababbbbbababbbbbbabbbabbbabababababbbabaabbbbbabbbbbbbaba
bbbabababbbbabbbabbbabbbbbabbbabbbabbbbabababababbbbbbbbbababbbbabbbababbbbbabbb
ababbbbbabbababababababbbababababababbabbbbbbbbbabbbbbbbabbbabbabababbbabbbababb
bbbabbbabaabbbbbbbbbbbababbbbbbbbbbbaababbbbbbbababbbbbabababaabbbbbababababbbaa
ababababbbbabbbbbbbbbabbbabbbbbbbbbabbbbabbbbbabbbabbbabbbbbbbbabbbabbbbbbbababb
bbbbbbbabbababbbbbbbababababbbbbbbababbababbbababababababbbbbbababababbbbbabbbaa
abbbbbabaabbbabbbbbabbbbbbbabbbbbabbbaabbbababbbbbbbbbbbabbbbabbbbbbbabbbabababb
babbbabbbbabababbbababbbbbababbbabababbababbbabbbbbbbbbababbababbbbbabababbbbbaa
bbabababbabbbbbababbbabbbabbbababbbbbaabbbabababbbbbbbabbbaabbbabbbabbbbbabbbabb
aabbbbbaababbbabbbababababababbbabbbabbababbbbbabbbbbabababbabababababbbabababab

sample output of abbaabba with one triangle highlighted:

bbabaaabbbbbbaaabbaabbababaaabaabaaabbbbbaabbaabbabbababbbababaaabababbbbbabbbab
abbbaabaaaaabaababababbbbbaabbabbaabaaaabababababbabbbbaabbbbbaabbbbbaaaabbaabbb
baababbaaaabbabbbbbbbaaaabababbababbaaabbbbbbbbbabbaaababaaaababaaaabaaabababaaa
babbbabaaababbaaaaaabaaabbbbbabbbbabaabaaaaaaaabbabaabbbbaaabbbbaaabbaabbbbbbaab
bbaabbbaabbbabaaaaabbaabaaaabbaaabbbabbaaaaaaababbbabaaabaabaaabaabababaaaaababb
ababaababaabbbaaaabababbaaababaabaabbabaaaaaabbbaabbbaabbabbaabbabbbbbbaaaabbbab
bbbbabbbbabaabaaabbbbbabaabbbbabbababbbaaaaabaababaabababbabababbaaaaabaaabaabba
aaabbaaabbbabbaabaaaabbbabaaabbabbbbaabaaaabbabbbbabbbbbabbbbbbabaaaabbaabbababb
aababaabaabbababbaaabaabbbaababbaaababbaaababbaaabbaaaabbaaaaabbbaaababababbbbaa
abbbbabbababbbbabaabbabaababbbabaabbbabaabbbabaababaaababaaaabaabaabbbbbbbaaabaa
baaabbabbbbaaabbbababbbabbbaabbbabaabbbabaabbbabbbbaabbbbaaabbabbabaaaaaabaabbaa
baababbaaabaabaabbbbaabbaababaabbbabaabbbabaabbaaababaaabaababbabbbaaaaabbababab
babbbabaabbabbabaaababababbbbabaabbbabaabbbababaabbbbaabbabbbabbaabaaaababbbbbbb
bbaabbbababbabbbaabbbbbbbaaabbbabaabbbabaabbbbbabaaabababbaabbababbaaabbbaaaaaab
ababaabbbbabbaababaaaaaabaabaabbbabaabbbabaaaabbbaabbbbbabababbbbabaabaabaaaaabb
bbbbabaaabbababbbbaaaaabbabbabaabbbabaabbbaaabaababaaaabbbbbbaaabbbabbabbaaaabaa
aaabbbaababbbbaaabaaaababbabbbabaabbbabaabaabbabbbbaaabaaaaabaabaabbabbabaaabbab
aabaababbbaaabaabbaaabbbabbaabbbabaabbbabbababbaaabaabbaaaabbabbababbabbbaababba
abbabbbaabaabbababaabaabbababaabbbabaabbabbbbabaabbababaaababbabbbbabbaababbbaba
babbaababbababbbbbabbababbbbbabaabbbababbaaabbbababbbbbaabbbabbaaabbababbbaabbba
bbababbbabbbbaaaabbabbbbaaaabbbabaabbbbabaabaabbbbaaaababaabbabaababbbbaababaabb
abbbbaabbaaabaaababbaaabaaabaabbbabaaabbbabbabaaabaaabbbbababbbabbbaaababbbbabab
baaabababaabbaabbbabaabbaabbabaabbbaabaabbabbbaabbaabaaabbbbaabbaabaabbbaaabbbba
baabbbbbbabababaabbbababababbbabaababbababbaababababbaabaaababababbabaabaabaaabb
babaaaaabbbbbbbabaabbbbbbbbaabbbabbbabbbbababbbbbbbababbaabbbbbbbabbbabbabbaabab
bbbaaaabaaaaaabbbabaaaaaaababaabbaabbaaabbbbaaaaaabbbbababaaaaaabbaabbabbababbbb
aabaaabbaaaaabaabbbaaaaaabbbbababababaabaaabaaaaabaaabbbbbaaaaababababbabbbbaaab
abbaababaaaabbabaabaaaaabaaabbbbbbbbbabbaabbaaaabbaabaaaabaaaabbbbbbbabbaaabaaba
bababbbbaaababbbabbaaaabbaabaaaaaaaabbabababaaabababbaaabbaaabaaaaaabbabaabbabba
bbbbaaabaabbbaabbabaaabababbaaaaaaababbbbbbbaabbbbbabaababaabbaaaaababbbababbabb
aaabaabbabaabababbbaabbbbbabaaaaaabbbaaaaaababaaaabbbabbbbababaaaabbbaabbbbabbab
aabbababbbabbbbbaababaaaabbbaaaaabaabaaaaabbbbaaabaabbaaabbbbbaaabaababaaabbabba
ababbbbaabbaaaababbbbaaabaabaaaabbabbaaaabaaabaabbababaabaaaabaabbabbbbaababbaba
bbbaaabababaaabbbaaabaabbabbaaababbabaaabbaabbababbbbbabbaaabbababbaaababbbabbba
aabaabbbbbbaabaabaabbababbabaabbbabbbaababababbbbaaaabbabaababbbbabaabbbaabbaabb
abbabaaaaababbabbababbbbabbbabaabbaababbbbbbbaaabaaababbbabbbaaabbbabaababababaa
babbbaaaabbbabbabbbbaaabbaabbbabababbbaaaaaabaabbaabbbaabbaabaabaabbbabbbbbbbbaa
bbaabaaabaabbabbaaabaabababaabbbbbbaabaaaaabbabababaababababbabbabaabbaaaaaaabab
ababbaabbababbabaabbabbbbbbabaaaaababbaaaababbbbbbbabbbbbbbabbabbbababaaaaaabbbb

Im not sure if mine meets the initial criteria 100% though, as my sample will start producing this output almost instantly, however the pseudorandomness of some of the rules you can give it will make the output fairly unique during each calculated row, so to get the output at the hour mark takes running it for an hour (assuming same number of rows were created).

Edited by Net Gnome, 12 September 2012 - 04:19 AM.

[shurcool]

On what hardware? Which languages are allowed? Define "interesting"?

A typical current Core i7 laptop.
Any language you like.
Interesting is something that, after the hour passes, you are excited to see the results.

It would help to post some sample output of your programs, if possible.

I'm still trying to come up my own entry to this challenge... But great stuff so far.

[shurcool]

Test of randomness!

I ran your program for an hour, and got this output:

Longest sequence of equals in 17736331274 numbers in [0, 1000000]: 2

I ran it again for 3 minutes, and got this ouput:

Longest sequence of equals in 862139850 numbers in [0, 1000000]: 2

Edited by shurcool, 12 September 2012 - 08:46 AM.

[Erik Rufelt]

My bad, way too high a number for the max value.
I edited it to 7 and added an inner loop to make it count faster.

The idea is to see how many times you get the same result in a row if you roll a dice an insane number of times.
So if you have 1/8 chance of rolling a 1, then you should have a 1/64 to roll two 1s in a row etc.

Running the new version for 30 sec, I get 1.4 billion numbers in 30 sec, and a longest sequence of equals of 6, which is the exact same result I get for the only 11 million numbers my computer counts in 1 second.

In other words, rand() % 8 is not all too good at actually being random for long sequences, as it seems the algorithm can never(?) get past a sequence of 6 equal rolls.

Edited by Erik Rufelt, 12 September 2012 - 09:53 AM.

[slicer4ever]

My bad, way too high a number for the max value.
I edited it to 7 and added an inner loop to make it count faster.

The idea is to see how many times you get the same result in a row if you roll a dice an insane number of times.
So if you have 1/8 chance of rolling a 1, then you should have a 1/64 to roll two 1s in a row etc.

Running the new version for 30 sec, I get 1.4 billion numbers in 30 sec, and a longest sequence of equals of 6, which is the exact same result I get for the only 11 million numbers my computer counts in 1 second.

In other words, rand() % 8 is not all too good at actually being random for long sequences, as it seems the algorithm can never(?) get past a sequence of 6 equal rolls.

you should try some other random systems, and even if possible, use intel's hardware RNG for near true randomness, it'd be interesting to compare the results between diffrent pseudo random number generator algo's, and hardware based random number generators.

Edited by slicer4ever, 12 September 2012 - 10:03 AM.

[Erik Rufelt]

you should try some other random systems, and even if possible, use intel's hardware RNG for near true randomness, it'd be interesting to compare the results between diffrent pseudo random number generator algo's, and hardware based random number generators.

Good idea! I tried it with Intel's RdRand, and got a longest sequence of 10 in 1 billion numbers in [0, 7]. It was also 10 after 6 billion numbers.. which shouldn't be all too unlikely for true randomness.. I'll try another time to run it through many more numbers. I'm not sure if cryptographically secure means truly random though.. the docs says it has true random seeds, but can yield up to 500 values or so in between seeds. For true randomness only using the seeds might be better.

I don't know enough statistics to say whether this test is fair or exactly what it means though..

One interesting test is to set a max value of 1, and just get random bits, a coin toss instead of a dice roll.
32 coin tosses can be done either by 32 rands and picking the last single bit from each, or by taking the 32 bits from one 32-bit random number. If it's actually 100% true randomness I guess they should yield the same probabilities.. and a 2 in 4 billion chance to hit the same value 32 times in a row..

I tested it for rand. Using only the last bit, I get a max sequence of 15 no matter how long I run it.
For me RAND_MAX is 32767, so 15 random bits per number. Using all the bits as 15 different numbers I get a total max sequence of 34 of the same bits when running it for 140 million numbers.. which obviously seems way unlikely.

Another thought.. rand() probably loops when it goes past some number of calls.. perhaps 2^32?

Edited by Erik Rufelt, 12 September 2012 - 05:32 PM.

[Bacterius]

I'm not sure if cryptographically secure means truly random though

It's about as close as it gets.

Another thought.. rand() probably loops when it goes past some number of calls.. perhaps 2^32?

I think 2^48 or 2^64 now... 2^32 would be far too small (but it doesn't matter, successive outputs are still strongly correlated since it's most likely an LCG).

[papalazaru]

Is writing a quine just too easy for you? Then try your hand at the following simple programming challenge.

Write a short program that takes at least one hour of computational time (this can be a parameter if you want) to produce some interesting output. Pre-canned output is not interesting, nor does it take one hour to generate.

like... a mandelbrot?

[slayemin]

Here's my submission in a powershell script...

write-host "Hello " -nonewline
timeout /t 3600 /nobreak
write-host "world."

It takes exactly one hour to complete and the term "interesting" is a subjectively defined term.

[slicer4ever]

Here's my submission in a powershell script...

write-host "Hello " -nonewline
timeout /t 3600 /nobreak
write-host "world."

It takes exactly one hour to complete and the term "interesting" is a subjectively defined term.

is their a particular reason you use write-host instead of echo?

[slayemin]

Here's my submission in a powershell script...

write-host "Hello " -nonewline
timeout /t 3600 /nobreak
write-host "world."

It takes exactly one hour to complete and the term "interesting" is a subjectively defined term.

is their a particular reason you use write-host instead of echo?

Yes, it lets me add extra parameters to control how the string is displayed, and thus is more robust and my prefered way of outputting text. Sure, I could use echo to output unformatted text, but if I found a need to start formatting it, then my code would contain a mixture of echos and write-hosts. So, I just choose to use write-host all across the board for the sake of consistency

#hello world with red text and green background without a terminating line break
write-host -foregroundcolor red -backgroundcolor green "hello world" -nonewline

[slayemin]

Speaking of Quines, I was playing around with a self-referencing program a few weeks ago. I could get it to output its source code via a simple print function, but if I copy/pasted the printed source code, it wouldn't result in the same program anymore because the next compiled generation wouldn't be able to print itself. It's a perplexing problem. It reminds me of looking into the world within two mirrors reflecting each other infinitely.

I'm currently thinking that the problem is that my language is compiled. If instead I wrote my program in binary, I could instruct the program to read its own binary code and output the results (which would pretty much be a way to clone/copy yourself). Then I'd be able to run the clone and repeat the command for as many generations as I'd like.

The other approach I was thinking of was adding the C++ compiler as an embedded resource within the compiled executable. Then, the app could just print its source code and run it through the compiler, and somehow splice in its source code into the source code again, thus being able to self-compile and run as many generations as desired. What an interesting problem to contemplate

[Shippou]

What constitutes a "programming language" ?
If what the OP wrote is they way I think it is, they want a "random" program of some kind ?
Just to go off the deep end, here is something "random" I came up with some time ago

[shurcool]

This challenge was partly inspired by the following realization...

You know the phrase "they say people only use 10% of their brain, imagine if they used it all"... Well, it's not true, every part of the brain is used.

On the other hand, "most games spend less than 10% of total CPU time on AI" is actually true. Imagine if AI used 90% of the total CPU time on a powerful quad-core i7... What would it be able to achieve?

[Bacterius]

On the other hand, "most games spend less than 10% of total CPU time on AI" is actually true. Imagine if AI used 90% of the total CPU time on a powerful quad-core i7... What would it be able to achieve?

I don't think AI "skill" scales linearly with processing power, my guess is it's more like an exponential complexity curve because of all the graph theory involved in artificial intelligence, so giving more processing power to the AI might not help that much. And of course there's the game logic and physics to run at the same time... but I agree that current AI is a bit stale, especially since it's pretty easy to exploit it once you understand how it works. And you can't unsee it either, once you've seen the AI break the immersion is gone forever.

I think the future is a system where you use your own brain as a computing extension to process AI (which would then become true intelligence) and challenge yourself, hopefully without cheating (perhaps you could isolate sections of the cortex to make sure the two different personalities don't interact, or you could replicate yourself for the duration of your gaming session). An interesting possibility is that you could connect your cat to the device and see if you can defeat him...

[slayemin]

There's an unrealized issue here: "Perfect" AI is not fun. Play Quake3 with Xero on nightmare difficulty on the last level. He's pretty much a near perfect aim bot with a rail gun who will one-shot you just about every time. It's only possible to beat him because he's not "perfect". If he was perfect, he'd be impossible to beat.
Consider the game of chess and the AI for it: Chess AI is pretty much a min-max tree with depth and breadth. The AI is limited by how many moves in advance it can think before running out of memory. If you had infinite memory and lots of available CPU, you could make a "perfect" chess AI, where the best result you could hope for is a stale mate. Make one false move, and you lose. Sound fun?
Consider that same level of difficulty for games like Civ 5 or Starcraft 2. The AI is so good it doesn't need to cheat. The computer has massive advantages over a human being. Imagine if the Starcraft2 AI had perfect micromanagement for every zergling, where it'd run away if it has 1 hp? It could calculate exactly when to run away, when to fight, etc. to maximize its damage dealt vs. damage received ratio. It would always play perfect games and you'd always lose simply because you don't have the ability to micro at the same level.

[slicer4ever]

On the other hand, "most games spend less than 10% of total CPU time on AI" is actually true. Imagine if AI used 90% of the total CPU time on a powerful quad-core i7... What would it be able to achieve?

It really depends on if the system needs more time to find the most optimal solution, so this wouldn't extend to every possible situation, and it also depends on the complexity of the AI, in such a manner that more time/processing = better results.