Time limited computation

What is the most efficient way to ensure this?

Use the required optimal algorithm.

All competitions are about figuring out the representation of the problem and implementing that. If you choose the correct one, then solution will complete within required time, regardless of language or other details.

If not, then you simply didn't find the correct solution.

In almost all cases it looks like this: correct solution takes 1.4ms in C and 1.8ms in Python and 3.4ms in Ruby. Incorrect algorithm takes: 48 days in C, 2.8 years in Python and 55.8 years in Ruby. Timers don't matter.

What's the value in returning if you don't have the answer? Is not having an answer worse than having a wrong one?

Sorry, I guess I wasn't clear enough. I was referring to AI competitions in particular. Unless you can exactly solve the entire game, then being able to spend more time is always beneficial, but you have to cut it off at some point. Furthermore, you generally have an answer that is iteratively improved.

For example, in a chess game with iterative deepening, you search to a certain depth, then to a deeper depth, and so on until you run out of time. But you always have an answer, just not an optimal one.

What's the value in returning if you don't have the answer? Is not having an answer worse than having a wrong one?

Being disqualified and instantly losing is generally worse than not doing anything.

Sorry, I guess I wasn't clear enough. I was referring to AI competitions in particular.

AI competitions are about score. Time is rarely a factor, since contests take weeks or months and what matters is best score, not how long it took to obtain it, as long as best results are sent in by a certain date.


Or maybe there is one particular contest you have in mind that has certain set of rules, in which case it might be helpful to know which, so that individual rules may be examined.

Here's the only I'm currently attempting to do.
http://aichallenge.org/index.php

Running environment for this problem is hard real time, so for "proper" solution, same rules must be obeyed. All operations must be deterministic and all operations must be constant time. Java would need to avoid GC at all costs due to non-determinism, for example.


While ad-hoc timing via aborts might work, it does not guarantee any kind of improvement over deterministic fixed-size search space. You either know that each particular step will conclude in given time, or you might time out locally and end without a solution or at least better one.


So for each step you need to know the worst case time for one step of simulation/improvement. Since there are constraints on input, these can be accurately determined. Then you know precisely how long each step takes (such as pathfinding, visibility test, etc...). Perform enough to stay within time limit. This will be the best result attainable. If there is still time left, run the improvement step. If normal step takes 200ms in worst case, run 4 of them. If first few improvements take 20, 20, 30, 20, 20, 40, 20 (170), then you can reliably run 4 more, then repeat the estimation. It becomes a discrete problem.

Ideally, algorithms should be bound by discrete parameters, not wall time. So when searching, let each ant examine up to 10 steps (or similar). Time and space complexity can then be accurately determined.

While at first it may seem that unbounded search with local timeout would produce a potentially better result, it would not. Either unbounded search exhausts same resources as bounded, or it times out in some non-deterministic state, which will, given same algorithm, be no better than bounded one.

But unless you're running on bare metal, it's impossible to ensure real time performance. Even if you're deterministic, the OS isn't, and that's not even considering the impact of cache usage, paging, etc. And there's no feasible way to do profiling on their server anyway.

Of course you can profile. You just have to profile on the fly, while you're running your algorithm. This is mostly an issue of algorithm design, as Antheus has pointed out.

Here's one possible approach: divide your process into iterative refinement steps. Determine how long step N+1 will take in relation to step N. Then, every time you compute some step Q on the actual server, use your theoretically sound relation between T(N+1) and T(N) to compute T(Q+1). If that time overflows your remaining time limit, then stop computing.

Another advice is: never use recursion.

Simple example:int compute(...) {
for (every i in input) {
add(compute(i));
}
return best();
};Simple, clean, elegant. And absolute disaster, especially when doing heuristics. What is the complexity of the above?

Instead, compare this version:
int level0[MAX];
int level1[MAX*MAX];
int level2[MAX*MAX*MAX];

void compute0to1() {} //
void compute1to2() {} // all same for loop
void compute2to3() {} //

Something becomes painfully obvious: MAX*MAX*MAX*...., or n^m

The latter style of algorithms is vastly preferred, especially given that input sizes are well defined. Since it's fully deterministic, it's also easy to profile - just use running time of one step. If it's enough, it'll always be enough and you can try increasing by one more level.

And there's no feasible way to do profiling on their server anyway.[/quote]

It doesn't matter.

Develop your algorithm.
Write it.
Run it.

If it's fast enough, it will work. If it's not, the algorithm is too complex and not suitable for the constraints of the competition.

It's not about microoptimizations. It's about quicksort vs. bubblesort.

If it's fast enough, it will work. If it's not, the algorithm is too complex and not suitable for the constraints of the competition.

I disagree.


Part of the challenge of this particular competition is that a best algorithm for solving the problem is not necessarily known. For most programming competitions, the answer is well-understood (to make judging easier) and either you get the right algorithmic approach or you don't - in those situations, you would be correct.

But for the Google AI Challenge, a good portion of the difficulty stems from the fact that there isn't necessarily a practical, optimal, known algorithm for solving the problem in the first place. The point is to encourage people to explore the problem space, not to see who can hammer out a well-understood algorithm fastest.

I'd approach this with threads.

I'd create a main thread who's job it is to:

1. Receive input.
2. Hand out the 'find the best move' task to a worker thread.
3. Produce a trivial fall back answer, just in case the thread doesn't produce any output in time.
4. Wait until you're close to the time limit and submit the best answer calculated so far, and set a flag to tell the thread to stop working.
5. Repeat from step 1.

The worker thread:

1. Waits for input.
2. Iteratively processes the input and stores off a best move (in chess this could be and iterative deepening search for example).
3. Check for the stop flag every so often. When it's set clear it and go back to step 1. Otherwise back to step 2.

This lets you do as much as possible within the time limit.

Obviously you can have more than one worker thread if that's helpful. Each thread could have a different strategy for finding the best move for example, or each one could search a different subset of the search space.

The problem is that that approach appears to be forbidden by the rules.

For chess, the number of nodes per second that you can search doesn't vary wildly, so you can do something simple like check the time every 10,000 nodes and abort the search if you are getting close to the time limit. This type of low-tech solution can probably be used in most cases.

I think using recursion is just fine. Some algorithms, like alpha-beta, are hard to express iteratively. The check to abort the search is not expensive (it's a branch that is perfectly predicted except for the time when time is up) and if it were, there are fast ways to get out of a deep recursion. When I was writing a checkers program 20 years ago, I found that checking the out-of-time flag was expensive, so I got out of the recursion with longjmp, which worked beautifully. You can use exceptions for the same purpose, if your language supports them.

Update:

I went ahead and decided to just check the time at the beginning of every iteration, and return early when there's only 20ms left. Most of the time it works pretty well. However, it will sometimes randomly timeout anyway for no discernible reason.

The only thing I can think of is that the OS is making my process go to sleep for more than 20ms. Is this likely? What can I do to prevent it?

Are you sure you break all iterations immediately?
If your code like this,


void iterateAI()
{
if(time out) return;
for(millions of iterations) {
iterateAI();
}
}


Then if the deepest iteration time out, the loop will still continue a lot of times.

Here's pseudocode. As you can see, the time check is in the innermost loop, so it will always be reached quickly. If the recursive call returns early, then the time check on the next iteration of the while loop will fail, so the next level also returns after a negligible amount of time.



def solveRecursive(score, ref cutoff)
node = getMostConstrained

if node = end #solution found
if best solution is empty or score > cutoff
update solution and cutoff
else
while node has moves
if timeisup
return
move = node.getBestMove
apply(move)

if moveWasConsistant
solveRecursive(score + scoreDiff, cutoff)
unapply(move)

remove move from node.allowedmoves
update score
restore node allowed moves


The obvious answer is that your getMostConstrained or apply(move) calls are chewing up more time than you expect. Of course, this doesn't necessarily mean that's the correct explanation, but certainly I doubt the server is starving you of time for durations as long as 20ms.

I return to my earlier suggestion of building some kind of profiling into the algorithm implementation, so you can actually pinpoint where your time is going. Surely there is a mechanism by which you can pull this off?

Those rules don't disallow SIGALARM - that will let you get a callback just before time runs out.

The obvious answer is that your getMostConstrained or apply(move) calls are chewing up more time than you expect. Of course, this doesn't necessarily mean that's the correct explanation, but certainly I doubt the server is starving you of time for durations as long as 20ms.

I return to my earlier suggestion of building some kind of profiling into the algorithm implementation, so you can actually pinpoint where your time is going. Surely there is a mechanism by which you can pull this off?

I doubt that getMostConstrained or apply(move) are taking much time, because when I return early, the time reported after everything done is around 383-384/400ms, meaning that everything my bot did after the first break put together took less than five milliseconds. So it doesn't seem likely that it would suddenly jump to 20 without ever being anything in between.

Also, the timeouts are taking place on my own computer during local testing. I haven't played enough games on the server to see if it ever timesout on the actual server.

Anyway, how can I profile it? I'm not very experienced with profiling.


Edit: I put a statement to print the current time out inside the inner while loop. It prints out on average 13 times per ms, and then at 30ms to go, it just stops. So now it appears that the Gremlin is stealing even more time than before.