[Down-n-Out] Lowering grid's size

I think that you must reduce number of max grid size from 50x50. There is two ways:
1) If I will use simple algorithm, for example, selecting start position of each round by random generation, then I will keep within provided time.
2) In the other side, if I will use advanced, clever algorithm (where I think is goal of this contest - creating clever algorithm), for example, in each round I will analize all of possible turns and choose only those turns that can give me more points in this and in the NEXT turns (like in chess - program more powerfull when it can analize more future turns) - I think this is that most interesting in this game! But on large field it will can take more time and in result it will exceed provided time while other scripts with simple algorithms will not exceed it.

P.S. This is IMHO. I can be wrong.
P.P.S Sorry for my English. I hope you will understand me

Me too...

But after reading the other threads, I think the safest thing to do is write a back-up that will just select the best for this move...

My only concern is when to spend the time to use this back-up, because it seems it takes up to 17 seconds on the worst-case board (50*50*8)...

I will not be lowering the grid any further. You will know the size of the grid at the very start of your processing. You can place logic into your script so that if you feel the grid is too large for your clever algorithm, then you go to a dumber algorithm that will be able to do its job in time.

Remember, everyone is dealing with the same input. There won't be a case where you get a larger grid than someone else. The person who comes up with a complete solution that is the best will win. A complete solution may or may not be a single algorithm ;)

I have to say that I first thought that the rules were dumb, but in fact, the challenge is much more interesting that you may think !

The aim of the contest is not only to write efficient code (I get typically 17-19 seconds on 50*50 boards on my 2.4Ghz, with 800-900 'moves' per grid), but also to find a good heuristic.
The heuristic about removing the largest block of tiles is very dumb, since 50 out of 800 moves remove only ONE tile.

It's definitely impossible to explore the whole 50*50 exhaustively, and I hope Matt's final grids will be of different sizes, with a majority of small grids, but also some 50x50 grids.

Achieving good scores on large grids (especially with 8 tiles) is very difficult !

JC

Actualy the big grid's get you the biggest scores

Matt's sample grid 10x10x3 gives me a score of 2002 in 19 moves

a random grid of 30x30x3 gives me a score of 105316 in 156 moves

And a random grid of 50x50x3 gives me a score of 739640 in 478 moves

Then a random grid of 50x50x8 goes back to a score of 134306 in 1179 moves

Of course as the scripts get better scores could improve. But it does give away the score trends for the boards

So you can optimize all you want on small grids. The biggest battle will be in the big grid's. If you miss a big one. Youre Toast ;)

To me it would be nicer if the score was a little more even over all grids.

for example:

for a random grid scripts get the folowing scores

Script A: 4463
Script B: 6573
Script C: 3002

the script that gets the highest score gets 100 points
the rest gets floor(highscore / ownscore * 100) points

so

Script A: 4463/6573*100 = 67 points
Script B: 6573 = 100 points
Script C: 3002/6573*100 = 45 points

This forces you to make a script that does good on all boards. Not only the big one's

I get similar scores with marcel.

I am against lowering the grid below 50x50.

As I said before, I still haven't discarded the possibility of finding the optimal for a 20x20 grid.

However, I don't claim it cause I am still doing prelimirary stats.

But there is a bunch of very good coders around here...

Do you want a tie between 3 scripts with exactly the same score?

It is better to keep the difficulty high and let space for imagination and good heuristics.

I have a very dumb algorithm whose minimal score is greater than:
(ROWS*COLS/TILES)²
+(ROWS*COLS*(TILES-1)/TILES)
That is:
10x10x3 > 1,177
30x30x3 > 90,600
50x50x3 > 696,111
50x50x8 > 99,843

guess what?


I think so ;-)



That's interesting.

I just have tested script with simple algorithm. With 35x35 matrix and 8 tiles types it works 4+ seconds. It exceedes time limit or cause error in php.exe with matrix about 38x38 and more.
AMD Athlon XP 2000+, 512 mb, Windows XP, PHP 4.2.3

Finally got a reasonable score now on my 50x50x8 board

Found a score of 132674 in 1169 turns after 10.73 seconds

and on the inputs/input_50_50_8.txt found in the zip file of xs0 http://dist.doticni.net/dno/dnoinputs.zip

Found a score of 131156 in 1237 turns after 10.68 seconds

Matt's benchmark runs in 15.4545619488 seconds

So it seems to be possible ;)

only IE dies if i try to view all boards in one page with param &method=display (Virtual mem goes to 700 Meg for ie only )

Wow !
I'm now below 11s, but with a 2.4Ghz (10.40 seconds on the benchmark).
But I still have some optimizations left :-)))

JC

Oh, yeah, without any output it works OK.

I just saw this and i cant believe my eyes. You obviously stole my algorithm (kidding)! Here is the output i get for the same file, copy/pasted directly from the browser :

AFTER 1237 ROUNDS ... SCORE = 131156 points! (elapsed time : 11.655228972435 seconds)

It seems great minds work alike

(Darn IE!!! it got back and erased all the message when I press backspace)

Well, I now have it working at a decent speed.
I get about 120,000 points for 50x50x8 in less than 9 secs. Then about 770,000 for 50x50x3 in less than 4 secs.
These are means for random boards.
My laptop is a PIII/700, I think the times would be halved on Matt's machine.

I have two (probable) speed optimizations in mind, and one easy improvement for the first-try heuristic.
Then I'll go for the optimal (shall it be possible?)
:-
This time I could make the solutions-tree and explore it as in classic game theory. But you know, if classic theory had given good results in the past, mankind would have reached perfection...

Gatopeich, I was first schocked when I saw your last benchmarks, since I improved a lot my code, but my program runs in 10+ seconds (or 3 times slower on Matt's computer).
I decided to force all the moves to remove the bottom right tile (the program plays only this move to empty the board).
On the file dno/input_50_50_8_00.txt, I got
"Solved in 0.759353995323 seconds in 1835 turns with a score of 4460/783084"
(multiply by 3 to get the final speed)

Can you bench your program with this test ?

JC