Re: Searching strategies

[Peter Harrison <peter.harrison@helicron.net>]

That all makes sense. Clearly, option 1 would have searching stop in any case. As for option 2, I had not thought it through to that extent but you are right, up to a point.

At present, I do the search out and then test a couple of routes. If the proposed route from start to goal passes through only visited cells, the mouse will go to the start and get on with a speed run. Otherwise, it will try to visit the unknowns on the proposed route. One downside to this is that the calculated route from the mouse to the start, say, is not necessarily the same as the calculated route in the other direction. Visiting some of those missing cells can prove difficult as they may not even be accessible. Or they could be at the end of a useless region of the maze.

Also, the time cost of exploring after reaching the goal should be less because it will be possible to run through known cells rather than take them at explore speed.

However, that said, it will be well worthwhile, I think, doing some calculations in the mouse to see if there is any likely real benefit in trying to find a better route.

Again, Japan rules are different and it is probably worth taking a reasonable time exploring. Possibly, the mouse should incorporate a timer so that, after, say, 3 minutes, it just goes with what it has and returns to the start giving the handler time for the speed runs.

Peter Harrison




On 28 Aug 2010, at 18:47, David Hannaford wrote:

> Peter
> 
> Assuming that you are going to follow a strategy that searches from the start to the centre and also searches on the way back to the start, then when you get back to the start you have 2 scenarios:
> 
> 1 - You run the flood algorithm and find that you have visited all the cells on the flood route, in which case you have found the optimal route and it is not worth doing any more searching
> 2 - You run the flood algorithm and find that you havn't visited all the cells on the flood route yet, but you do know how many cells are on the route that you took back and you also know how many are on the possible flood route that you have just calculated. This last figure will be a best possible number of cells (which might not actually be achievable when you visit some cells and find extra walls).
> 
> If your best actual route so far is not too different from the best possible flood distance you have just calculated then there is definitely no point in further exploring.
> 
> So how much difference do we need before it is worth going out again to explore?
> Well, an explore run will typically require a run to the centre and back at explore speed. If we say this is likely to take 15 seconds each way then the full round trip will be 30 seconds which by UK rules means an extra second of penalty time.
> 
> Now with typical run times to the centre now being sub 10 seconds, then to save out extra second penalty time we need to find a new route that is more than 10 percent faster to break even.
> 
> So with a typical maze route of 70 cells to the centre you need to be sure of finding a route that is at least 7 cells shorter to break even.
> 
> So, given that the theoretically best route believed to exist at this time will not always be able to be achieved, I would be looking to probably get double the break even figure. I.e. the calulated best route must be 14 cells better than the currently known one  before it is worth going out to explore more.
> 
> Anyone else think this makes any sense?
> 
> Cheers
> David Hannaford
> 
> 

<<

Email has been scanned for viruses by Altman Technologies' email management service - www.altman.co.uk/emailsystems

 >>