[appleeaters]Still slow...

Not sure if this is just my box, but I am running an 800x800 test map with 1827 apples and 4573 robots, and running the example robotavoider.php it only has time to play 6 turns (using the NEW robots lib).

If I run a 1000x1000 map (the abs. max size) with 19085 apples and 7839 robots, robotavoider only has time for 3 turns.

The computer I am running this on is an AMD Athlon 2000+ XP, 768mb DDR 2100 running SuSE linux 9.0 (not under heavy load either), so I dont think this is right.

If this simple bot cannot run for more than 6 turns under a large map, I dont think its right to expect ours to do so. I think that a more modest time limit would be something like 7 - 10 secconds per move. The way that I could see this working is by having robotslib, using microtime() (or whatever) will measure the time it takes from when its finished updating the map with robot moves, and the time it takes our algorithms to submit a move. In the event that we are over the limit, instead of just ending the program cold turkey with a 0 score, robotslib should calculate the score earned up to that point.

One more comment, because I realized the difficulty of what I proposed above, the way that it could work is by using the microtime() counter and waiting (no matter what) for a move. If the move comes, but is too late, then game over and score is tabulated. If the algorithm of the user is in an infinite loop or is taking WAAAY too much time, then you can use the microtime() method in conjunction with set_time_limit(20); so that if the users program takes more than 20 secconds for their move, the program quits and they get a 0 for the score.

Same problem here:
AMD Athlon 2600+, 512 Ram, Win2k3 Server. Not only does it kill me that we're limited to 32 Megs of ram, it kills me that it's so slow. PHP has never been known for its speed, and in this case, it's almost too slow to manage. I ported my script over to C just to check the speed difference, and I nearly cried. My C version can complete nearly five thousand turns in a minute (fairly complex algorithm..), and my PHP version can only do _ONE_ turn. I'm working on the speed issue, but damn, it's just upsetting.

I sure hope the judging computer is the Virginia Tech BigMac cluster ;).

Mine isnt *that* slow... and I think the 32mb limit is fine... Its just the process that the program goes through of looping through all robots and updating.

What I did to speed up my version (and this got it going MUCH faster) was to at the very beginning of my algorithm, dump the entire apples and robots array's into multidimensional arrays with the coordinates as indexes. Then, instead of looking through every single element when you want to find the closest robot or apple, I wrote a spiral algorithm that will check all points emination from the player and will keep going until it hits a robot/apple. This will cut down your processing ALOT, but it will still take a long time for each move to be performed while you are waiting for the robotslib to update the robots moves. (btw, I am the origional poster.. I just havent registered yet...)

I have a faster version at my web site (http://rumkin.com/reference/php_contest/ (which is still faster than the new one put out today). Test it out and let me know if you like it.

(this thread was started by me btw)

Even running your new updated version, robotavoider runs with the following stats:

Map: http://www.stellarcore.com/phpcontest/tooslow.txt
800x800
Apples: 160
Robots: 3841
Moves before Timeout: 9

But the really strange thing is that if I use set_time_limit(60); which is what I have at the top of the script. Also, I added echo time() . "n"; after every move just to see how acurate set_time_limit(); So basically, from what I counted from the timestamp outputs, the script actually ran for 244+ secconds (it sent in the last move and timed out while waiting for the robotslib to update).

Let me know if you have the same problems with the map.

robotavoider with that map on my comp (athlon 2500+) manages less than 2 seconds using the new library (worryingly, it manages 12 moves too!)

set_time_limit doesn't limit system functions. Try or something like that.

Edit: added php tags.

I was probably being really stupid that I didn't try this.. but it definitely sped things up for me. Thanks!

It's still interestingly slow.. since my algorithm is vectorized (very much like a raytracer/raycaster, I plot out moves in vectors, and then batch execute the moves all at once, but while batch executing I look in the surrounding 5x5 area to check for robots/apples).

I think my next move will be to try and remove all the divisions in the code I can, and then replace multiplications with bitshifts. I haven't tinkered enough with PHP to learn if bitshifting is actually faster, but it tends to be in most languages since most languages define common multiplications with bitshifts. If anyone knows anything about this it'd be a great help. Other than that, maybe by having robotlib run in it's own time, and let our scripts run for 60 seconds, I don't see much of a way of speeding things up. Probably I just need to rethink what I'm doing and try a simpler way. KISS and all..

I'll do some tests tonight with bitshifting if someone hasn't already and I'll see how much we can save on multiplications and divides, however I still feel that it's not going to help much. Also, if anyone has any web space, I'd like to share my copy of robotslib. It uses a small object for logging the input/output, so that it can be quickly dropped to a file. I think that the judging script should definitely use something like this, although it does use up a lot of memory.. I guess this is why I had a cow over 32 megs last night. I can rework it so that it writes directly to a file and not keep the output buffer variable around though and that should speed it up considerably.

(this is Cirox, working from my sister's laptop, so I can't log in).

Using "time php4 robotavoider.php" and the tooslow.txt file, I get 19 moves in .5 seconds. Machine: Pentium III, about 730 mhz, 1458 bogomips (for you Linux geeks).

If you need a file hosted, I can put it on my machine. Just email it to me and I'll put it on my page.

Yah, its strange.. I just uploaded my files to another server that I have access to and they run quite a bit faster than on my personal machine. I think part of the problem might be that I am using php5 on my machine.