Techniques used in dno?

Hi,

I didn't submit a contest entry as I was so lazy to do any heuristics. I did however code a basic algorithm to do area filling and collapsing.

I wasn't able to get to the times you reported. How did you do it?

I had a two dimensional array for the board. According to my tests it was as fast if not faster than one dimensional array with pos=y*width+x.

For collapsing I used just array_splice. To make it even faster I collapse to lower left corner instead of the down right corner. This way I didn't have to use array_unshift to pad the beginning with zeroes. I read the board upside down to be able to do this and follow the rules. I ofcourse had to draw it the right way up.

For area checking I used an iterative flood fill with a stack.

Instead of marking the area in the board and then collapsing the marked areas I just returned the area coordinates in an array so I could collapse it just by array_splice():ing the coordinates.

I optimized my routine to be just 100 lines of code (with display), still achieving around 750000 points in the 50_50_3-board. But you guys approached 1 mil so...

Could you share some of your ideas here?

Regards,
Samuli Karevaara

Ok, here is how I proceeded.

First, the board is stored as an array of strings.
If you have a 8*8 grid, there are 10 strings of 10 characters. The first string and the last string only contain "0000000000".
The first and last characters of every line is "0".
The board is stored mirrored horizontally.
When I remove tiles, I mark columns to collapse, with the value of the lowest remove tile.
I first collapse vertically, then I collapse horizontally by doing a simple str_replace("0",""). Then I pad the string to get the correct number of characters.

My program has 3 passes:
1) the fast solver: used to get a first result (takes less than 1 Mattsecond to solve any 50x50). It simply removes the tiles of the rarest color from bottom to top.
2) the heuristic solver:
- If the number of colors is less than 4, the program tries to reduce the number of blocks of tiles (you can compare that to 2D defragmentation). To achieve that, it performs an advanced pattern matching. Example:
aba
bab
aba
in this case the program remove the central a (I also check if the up b and the right b are of different blocks).
3 cases are implemented: removal of a single tile, removal of 2 same adjacent vertical tiles, and removal of 2 same adjacent horizontal tiles.
Also, it removes the largest block possible if this block contains more than 90% of the tiles of this color (for example, if 10 red tiles remain and a block of 9 red tiles is detected, this block is removed).
The priority of the removals are: unique tiles, then largest block then 2 tiles.

- If the number of colors is more than 3, the program starts by removing the largest block of the rarest color starting from upper left. If the largest block is 1 tile, it removes rightest bottom tile.

3) the exhaustive solver
It simply removes the rarest colors from top left to bottom right with at least one block.
Otherwise, it removes the bottom rightest unique block. Also, when the most common color forms a block, it removes this color.

I think I forgot some features, but that's how my program works.

JC

It was quite obvious from the start that speed was to be of utmost importance to be able to implement at least some form of heuristics. Therefor the common functions - selecting of a block and the collapsing - had to be fast.
I also use a multi-dimensional array to store the grid. The filling routine is an iterative floodfill, and the collapsing; well - you can look at the code of my core implementation with comments here: http://therealcrisp.xs4all.nl/upload/dno_core.php

I'll explain later about the heuristics I have been using. It is absolutely different from JC's

I posted my source code here:

http://euler.free.fr/DNO/DNOFinal.ZIP

I guess it will be available in a few hours on the CodeWalkers FTP.

JC

For some algorithms I use a bonus-penalty system to determine which block to play. Take a look at the following example:

12323
32313
12122
22232
12212

If we seperate each set of adjecent blocks and calculate the sum of scores for each block (without collapsing) we get a total value of 97 for this board.

Now I calculate the next board value for each block that we can play after collapsing: let's assume we play the upperleft block; that would give us a score of 1 point and leave us with the following board that has a value of 96:
(0 is empty spot)

02323
32313
12122
22232
12212

now I also calculate a penalty for playing the block. We started with 6 1's on the board that could give us a maximum of 36 points. If we play one that would leave us with 5 with a maximum value of 25 points. The penalty for playing this block is the difference, being 9 points.

We now give this move a value calculated as follows:

2 x score - penalty + next board value = 2 x 1 - 9 + 96 = 89

If we would have played the set of 8 adjecent 2's that would give us the following board after collapsing:

00023
00113
03322
01332
01112

board value: 57
score: 64
penalty: (169 - 25) = 144

total value: 2 x 64 - 144 + 57 = 41

now if we play the 1 that is located at (y,x) (4,3) we get the following board after collapsing:

01233
32323
12112
22222
12232

board value: 142
score: 1
penalty: (36 - 25) = 9

total value: 2 x 1 - 9 + 142 = 135

After determining the value for each move we simply play the one that gave us the highest value

This bonus-penalty system is used in various ways; my submission uses a total of 6 algorithms based upon the board's complexity and number of blocks left on the board.

You can find the zip with my submission here: http://therealcrisp.xs4all.nl/contest/dno/dno.zip

the dno.php is heavily commented, so it should be quite clear what it does

Documentation and backstory very much appreciated.

My code is a little messy

I put a few evenings in it the first few days the content started. And then had to much other things on mij hands.

Tried to clean it up a little march 31 and just submitted.

http://projects.emenems.net/codewalkers/dno.zip

Just a few test on the codes posted above tell me I will be one of the losers again. But who cares ;) (not me..... at least not to much)

The fast routine is just counting the different colors in the grid and starts removing the color with the smallest count then second smallest count enz...

this way the biggest block will be left in the end

second routine tries every block and puts that score with the best block it can find after that. the highest score will be removed.

marcel: your code uses some methods that will not work in a windows environment; I've got the script to work except for the display part but had to make some changes.
Also I receive a notice on line 11 (with error_reporting set to E_ALL - which is my default).
Just thought you should know.
Speed is ok, and scores are as expected according to the method you described

JC: I'm impressed; your heuristic absolutely performs very well. I have got some boards that do very badly in my scripts, where yours does much better.
For example the 50_50_8_08 and 50_50_8_19 where your score is around 30,000 points higher than mine!

Crisp, I'm quite surprise that your fill routine seems as fast as mine. Here is mine:



I'm pretty sure my routine is faster on large sets, it's an optimized floodfill I wrote 20 years ago.

BTW, I hope that all Matt's grids will be as 50_50_8_08 and 50_50_8_19
(the heuristic has been finetuned in C, with a lot of runs to get the best AVERAGE score)

JC

sorry crisp... :uhoh:

I have put the :uhoh:wrong:uhoh: zip online. This one was from half way trough cleaning up my code and combining the boardimage part into dno.php
replaced it now and should be a little better

so again source here
http://projects.emenems.net/codewalkers/dno.zip

sample output here
http://projects.emenems.net/codewalkers/dno.htm

I dont know about this not running on windows part. I don't know any reason to run a webserver on windows and I know a lot of reasons why not to.....

JC: I do see some simularities between your floodfill and mine, although I haven't completely figured out yours yet (it's late). Note that I also keep some pointers for the collapsing in my floodfill.
Playing a 50x50 board in display mode however is very slow in your script when a large block is selected, but that could also be because of the many images that have to be changed - I solved that in a complety other way which takes some time initializing but is always fast after that.

As for the scores: I hope you're not dissappointed when I say that only in 3 boards out of the first 20 50_50_8_xx you get higher scores than I do. Also my average is 8,000 points higher on 50x50x8.
My real strength however is in boards with less colors since most of my heuristics only work when 3 or 2 colors are left... ;)

marcel: here's the notices that I get when I try to run your script:

Notice: Use of undefined constant source - assumed 'source' in f:wwwrootcontestmarceldno.php on line 11

Notice: Undefined index: source in f:wwwrootcontestmarceldno.php on line 11

Notice: Use of undefined constant board - assumed 'board' in f:wwwrootcontestmarceldno.php on line 47

Notice: Undefined index: board in f:wwwrootcontestmarceldno.php on line 47

Let's look at line 11:


offcourse this should be something like:


notice the quotes around 'source' and the use of isset()
I would advice you to set the error_reporting to E_ALL whenever you test your scripts ;)

Furthermore the script won't run on windows because of the use of getrusage(); which simply doesn't work on a windows platform.
I still couldn;t get the method=display to work, but I will have a look at that later.

I don't see any reason why I shouldn't run a webserver on a windows platform, fact is that I do and it suits me fine ;)

Point taken

Did not know that $array[key] in stead of $array['key'] was such a difference.

Does anyone know what platform Matt runs...... (am i toast???)