0

Context

I am writing an AI for a deterministic two player game in python. I wish to write a function which takes a timeout value as one of its parameters and returns a move shortly after the timeout. The function searches (negamax or similar) until the timeout is up and then returns the best move it can find.

Specification

  • The function should return a valid move no matter how or when it is caused to return.
  • The function may return a little after the timeout, so long as this is not noticeable to the user (~100ms).
  • The function should return if a custom AI_INTERRUPT event is placed on the pygame event queue. (This is so that impatient users can force the computer to play).

Proposed Implementation

I think I have an idea of how to implement this, but I have found a lot of conflicting advice online (and mostly for problems not quite the same as this one). I am also concerned that I am over-engineering things. I am therefore asking whether or not this implementation suggestion is a sensible one, or whether you recommend something else.

I am considering writing my AI algorithm as a generator that yields successively better moves. Time delays between yields could be long, but the first yield would be almost immediate.

I would then call this generator in a subprocess and have it feed yield values into a pipe.

The main process would then run in a loop of:

  • Poll the pipe. If a new value has been yielded it is stored.
  • Check the time. If the timeout has been exceeded, return the latest value.
  • Check for an AI_INTERRUPT event, returning the latest value if one is found.
  • Handle other pygame events as necessary

I am using Python 3 with pygame.

Paul Etherton
  • 391
  • 3
  • 11

3 Answers3

1

You could use a timed-out thread that wrappes your negamax method.

The method will update a shared data structure with the optimal solution so far. The shared data structure can simply be a list that you pass to your negamax method. When the timeout occurs, the caller will read the solution from the list.

Community
  • 1
  • 1
Adam Matan
  • 128,757
  • 147
  • 397
  • 562
  • Thanks, that's helpful. Which of the several methods of implementing a timed-out thread on that question do you recommend? There doesn't seem to be any kind of consensus. In what ways is this better than my multiprocessing based solution? – Paul Etherton Mar 10 '13 at 18:46
  • 1
    Invoking a process takes more time and consumes more system resources. Threads are lighter and quicker, share date more easily with the caller, but don't offer real multitasking (in Python). If you run a single calculation at any given time, use threads. I'd go for the accepted answer with the wrapper. – Adam Matan Mar 10 '13 at 19:36
0

If you are working on UNIX, you can use the signal lib to implement a timeout function : Timeout function if it takes too long to finish

Community
  • 1
  • 1
lucasg
  • 10,734
  • 4
  • 35
  • 57
0

Since you're already using pygame, use either:

def foo(duration):
    # time as MS
    start = pygame.time.get_ticks()
    while True:
        now = pygame.time.get_ticks()
        if now - start >= duration:
            return

        # do stuff

Or one of these two functions:

pygame.time.wait or pygame.time.delay

You could make a slightly more complicated version, that still lets your main loop continue. But if your display doesn't update in the short time, it might be overkill.

ninMonkey
  • 7,211
  • 8
  • 37
  • 66
  • My concern is that each run of "do stuff" could take too long. Although my idea is more complicated it would return closer to the end of the duration. I don't want to use wait or delay as the idea isn't just to waste time (which is what they do, for framerate control etc.) – Paul Etherton Mar 10 '13 at 18:42
  • If you're unable to break 'do stuff' into chunks, then you could use threading. ( That lets you use blocking functions, without breaking the main thread ) – ninMonkey Mar 11 '13 at 00:54