Programming Contest Nieuwe Stijl: Contest 4 *Score-update*

Nee het is die versie idd.

Ik heb een nieuwe jewel gemaakt: omgekeerde driehoek in het blauw:



edit en nog een roze 5 hoekje (voor verbetering vatbaar eigenlijk):


edit2: en nog een gele ster:


klik om te downloaden, kan hier op 't werk enkel uppen naar rapidshare ipv ftp.

Fastman wijzigde dit bericht 31-10-2008 14:42 (57%)

Een kruisje, die hadden we idd nog niet

Rapidshare link, kan je gewoon downloaden

Ik heb gister ook het begin geklust, hij leest het veld in

Extra testset:

speelveld.txt
code:

0000000000
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000
1000000000
1000110010
1001110010
1011110111
1111111111

kolommen.txt
code:

524577184162756554255252362524
876145765575583365836732136654
186565274575472521216633634414
764538457461112411261583558887
751744341625365615818472865341
175824231657572161765661413475
574558453442124418527868456815
336343667834435844213823553714
822621853526632325776184523344
214685564851278853464215267827

Grappige contest. Heb maar ook een beginnetje gemaakt in Java As far leest het de beide invoerbestanden in incl robuuste validatie. Matches en moves moeten nog gemaakt worden. De AI zal in beginsel gewoon 'dom' in een loopje de eerste de beste match vinden. Ik ben alleen niet 100% tevreden over de intuitieve OO opzet van de matrix die ik zonder na te denken heb neergecodeerd, ik moet nog eens kijken of ik dat netter kan doen. Ohja, ik heb ook de RML tabel layout gejat van oisyn Best wel handig achteraf.

Oh trouwens, is het bezwaarlijk als de volledige code en commentaar in het Engels is?

BalusC wijzigde dit bericht 31-10-2008 14:45 (9%)

Nice one, best complex
Mijn AI doet:

.
0
1
2
3
4
5
6
7
8
9
0
5
6
1
1
5
3
2
3
4
8
1
5
3
4
2
7
1
5
3
8
7
2
2
3
4
1
5
1
8
4
1
1
3
6
8
2
2
3
7
4
5
6
2
4
4
5
5
8
4
7
3
3
2
4
5
6
5
2
7
8
2
1
5
6
8
6
1
1
4
7
3
6
8
1
3
5
7
7
6
5
8
5
7
5
8
6
8
8
6
1
2
6
1
1
3
3
2
5
9
3
8
7
5
6
7
7
4
1
6
10
2
8
1
7
2
1
2
3
7
5
11
2
7
5
8
1
6
5
6
1
8
12
x
6
2
3
3
7
5
3
8
4
13
x
1
8
7
x
x
4
4
x
1
14
x
7
1
x
x
x
7
6
x
2
15
x
8
x
x
x
x
5
x
x
x
16
x
x
x
x
x
x
x
x
x
x
Score....................: 17050 points
Total moves..............: 172
Succesful moves..........: 172
Bad moves................: 0
Average score per move...: 99 points
Move with highest score..: #56 (400 points)

quote:

BalusC schreef op vrijdag 31 oktober 2008 @ 14:41:
Oh trouwens, is het bezwaarlijk als de volledige code en commentaar in het Engels is?

Nee, juist niet IMHO. * RobIII hartgrondige afkeer heeft van NL commentaar

quote:

.oisyn schreef op vrijdag 31 oktober 2008 @ 12:30:
En een nieuwe run van mijn AI: http://oisyn.nl/gc/uitvoer3.zip

Lukt me niet op te downen; vanuit thuis noch vanuit de zaak niet (Chello/Speedlinq-iets-ofzo)

RobIII wijzigde dit bericht 31-10-2008 14:49 (43%)

quote:

RobIII schreef op vrijdag 31 oktober 2008 @ 14:47:
[...]

Nee, juist niet IMHO. * RobIII hartgrondige afkeer heeft van NL commentaar

Same here, maar voor deze contest maakt het niet zoveel uit of het Engels, Nederlands (of voor mijn part Duits) is.

Note to self: alle niet NL en EN talige entries doorsturen naar -NMe-

quote:

BalusC schreef op vrijdag 31 oktober 2008 @ 14:41:
Ohja, ik heb ook de RML tabel layout gejat van oisyn

Ach die heb ik ook weer afgeleid uit enkele voorbeelden aan het begin van deze topic . Ik heb trouwens phsmit's kolom en rij-nummers inmiddels ook geïntegreerd in de tabel layout . Dit is mijn kleurschema trouwens, wellicht handig als we allemaal dezelfde gebruiken (voor 1 t/m 6 is dat bij phsmit wel het geval, maar 0, 7, 8 en 9 kwamen niet in het voorbeeld voor dus waarschijnlijk zijn die anders)

Ik gebruik nu:
C++:

1 2 3 4 5 6 7 8 9 10 11 12 13

static const char * colors[] =     {         "#00f",         "#0f0",         "#0ff",         "#f00",         "#f0f",         "#ff0",         "#aaa",         "#aa0",         "#0aa",         "#a00"     };

quote:

RobIII schreef op vrijdag 31 oktober 2008 @ 14:47:
Lukt me niet op te downen; vanuit thuis noch vanuit de zaak niet (Chello/Speedlinq-iets-ofzo)

Ik kon daarnet ook even niet inloggen op m'n ftp, waarschijnlijk zijn ze met de server bezig. Hier werkt het iig nu wel, probeer 't nog 'ns?

.oisyn wijzigde dit bericht 31-10-2008 15:09 (18%)

Tellen de punten die je krijgt bij het "binnenvallen" van het initiele veld eigenlijk ook mee met je score? Of tellen alleen punten mee die het resultaat zijn van een zet die je zelf gedaan hebt?

Ik heb de icoontjes in een zip gestopt, misschien kunnen die gebruikt worden (dan heeft iedereen gelijkaardige oplossingen voor zij die icoontjes gebruiken).

De 11 (10 + 1 voor 'rots'-velden) download je hier

quote:

rwb schreef op vrijdag 31 oktober 2008 @ 15:11:
Tellen de punten die je krijgt bij het "binnenvallen" van het initiele veld eigenlijk ook mee met je score? Of tellen alleen punten mee die het resultaat zijn van een zet die je zelf gedaan hebt?

Goed punt inderdaad. Die tellen gewoon mee. Bij 100.000 zetten zijn er dus 100.001 momenten waarop je score toegekend krijgt.

quote:

.oisyn schreef op vrijdag 31 oktober 2008 @ 15:07:
Ach die heb ik ook weer afgeleid uit enkele voorbeelden aan het begin van deze topic .

Jatters zijn jullie!

@era.zer: ziet er goed uit, alleen jewel9.gif is een beetje gekrompen in de was

quote:

JMfx schreef op vrijdag 31 oktober 2008 @ 12:22:
[...]
Om het nog even samen te vatten zodat ik het begrijp. Als je iets van één soort (zeg de 0) wil verzilveren, dan moet je alles verzilveren wat er aan vast zit, gegeven dat het een lengte heeft van drie of meer.
code:

1 2 3 0 3 2 1
0 0 0 0 0 0 0

Je verzilvert de onderste 7 nullen: 250 punten.
code:

0 3 2 1
0 0 0 0

Je verzilvert de onderste 4 nullen: 100 punten.
code:

1 2 3 0 3 2 1
0 0 0 0 0 0 0
0 0 0 0 0 0 0

Je verzilvert alle 15 nullen: 250 punten.

Het laatste voorbeeld is inderdaad één figuur dankzij de 0 in de bovenste veldrij.
De definitie

quote:

Een figuur wordt gedefiniëerd als een object waarvan elk los blokje deel uitmaakt van een rij van minimaal 3 dezelfde blokjes. Losstaande rijen naast of onder elkaar zijn alleen onderdeel van dezelfde figuur als er overdwars ook sprake is van een rij. Zie hier voor een aantal voorbeelden die allen "slechts" 250 punten opleveren.

klopt hier dus ook volledig.

quote:

-NMe- schreef op vrijdag 31 oktober 2008 @ 15:23:
[...]

Goed punt inderdaad. Die tellen gewoon mee. Bij 100.000 zetten zijn er dus 100.001 momenten waarop je score toegekend krijgt.

't Maakt in feite weinig uit voor de einduitslag, 't is alleen wel handig dat iedereen tot die tijd hier in de topic dezelfde methode hanteert

@pedorus: tot zover gaan mijn gfx skills ongeveer
beter mag altijd geupt worden!

Heeft iemand plannen om een PHP validator te maken? Dan zouden we de tests en uitslagen online kunnen zetten en verifiëren.

quote:

.oisyn schreef op vrijdag 31 oktober 2008 @ 15:32:
[...]

't Maakt in feite weinig uit voor de einduitslag, 't is alleen wel handig dat iedereen tot die tijd hier in de topic dezelfde methode hanteert

Uiteraard.

quote:

era.zer schreef op vrijdag 31 oktober 2008 @ 15:38:
Heeft iemand plannen om een PHP validator te maken? Dan zouden we de tests en uitslagen online kunnen zetten en verifiëren.

Ik ben zelf van plan om een PHP-inzending te doen; het maken van een validator daarbij is dan natuurlijk niet zoveel werk. Ik zal eens kijken wat ik kan doen. Mocht ik overigens echt een validator schrijven, dan is dat niet de officiële validator die we gaan gebruiken bij het checken van jullie scores; die heeft RobIII al geschreven, en die blijft zoals al in de startpost vermeld is intern tot na de deadline. Eerlijkheidshalve zal ik Rob's validator niet downloaden tot na diezelfde deadline.

quote:

.oisyn schreef op vrijdag 31 oktober 2008 @ 15:07:
Ik kon daarnet ook even niet inloggen op m'n ftp, waarschijnlijk zijn ze met de server bezig. Hier werkt het iig nu wel, probeer 't nog 'ns?

Ik heb als eindveld:
code:

4642143122145631563166413
2565363531434526212325422
X42645254152614512446213X
X535415446141525315121XXX
X613621134625646163565XXX
XX42542315416315421145XXX
XX342364465156345X344XXXX
XX51613411425522XXXXXXXXX
XX4245531363314XXXXXXXXXX
XX332526351XX5XXXXXXXXXXX
XXX5131625XXXXXXXXXXXXXXX
XXXXXXX31XXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXX

Even een quote van mezelf zodat ik kan vergelijken...

quote:

.oisyn schreef op vrijdag 31 oktober 2008 @ 12:30:

.	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24
0	4	6	4	2	1	4	3	1	2	2	1	4	5	6	3	1	5	6	3	1	6	6	4	1	3
1	2	5	6	5	3	6	3	5	3	1	4	3	4	5	2	6	2	1	2	3	2	5	4	2	2
2	x	4	2	6	4	5	2	5	4	1	5	2	6	1	4	5	1	2	4	4	6	2	1	3	x
3	x	5	3	5	4	1	5	4	4	6	1	4	1	5	2	5	3	1	5	1	2	1	x	x	x
4	x	6	1	3	6	2	1	1	3	4	6	2	5	6	4	6	1	6	3	5	6	5	x	x	x
5	x	x	4	2	5	4	2	3	1	5	4	1	6	3	1	5	4	2	1	1	4	5	x	x	x
6	x	x	3	4	2	3	6	4	4	6	5	1	5	6	3	4	5	x	3	4	4	x	x	x	x
7	x	x	5	1	6	1	3	4	1	1	4	2	5	5	2	2	x	x	x	x	x	x	x	x	x
8	x	x	4	2	4	5	5	3	1	3	6	3	3	1	4	x	x	x	x	x	x	x	x	x	x
9	x	x	3	3	2	5	2	6	3	5	1	x	x	5	x	x	x	x	x	x	x	x	x	x	x
10	x	x	x	5	1	3	1	6	2	5	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x
11	x	x	x	x	x	x	x	3	1	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x
12	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x
13	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x

Score....................: 24256450 points

.edit: ziet er op het eerste gezicht hetzelfde uit. Wat heb jij als score?

quote:

.oisyn schreef op vrijdag 31 oktober 2008 @ 17:11:
Wat heb jij als score?

Daar heb ik nog geen tijd voor gehad om te implementeren. Ik ben nu naar de verjaardag van mammie en heb komend weekend helaas weinig tot geen compilers tot m'n beschikking dus ik vrees dat dat pas na 't weekend komt.

Even een RML output test:

.
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
0
4
6
4
2
1
4
3
1
2
2
1
4
5
6
3
1
5
6
3
1
6
6
4
1
3
1
2
5
6
5
3
6
3
5
3
1
4
3
4
5
2
6
2
1
2
3
2
5
4
2
2
2
x
4
2
6
4
5
2
5
4
1
5
2
6
1
4
5
1
2
4
4
6
2
1
3
x
3
x
5
3
5
4
1
5
4
4
6
1
4
1
5
2
5
3
1
5
1
2
1
x
x
x
4
x
6
1
3
6
2
1
1
3
4
6
2
5
6
4
6
1
6
3
5
6
5
x
x
x
5
x
x
4
2
5
4
2
3
1
5
4
1
6
3
1
5
4
2
1
1
4
5
x
x
x
6
x
x
3
4
2
3
6
4
4
6
5
1
5
6
3
4
5
x
3
4
4
x
x
x
x
7
x
x
5
1
6
1
3
4
1
1
4
2
5
5
2
2
x
x
x
x
x
x
x
x
x
8
x
x
4
2
4
5
5
3
1
3
6
3
3
1
4
x
x
x
x
x
x
x
x
x
x
9
x
x
3
3
2
5
2
6
3
5
1
x
x
5
x
x
x
x
x
x
x
x
x
x
x
10
x
x
x
5
1
3
1
6
2
5
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
11
x
x
x
x
x
x
x
3
1
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
12
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
13
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
Score....................: ??? points
Total moves..............: 100000
Succesful moves..........: 100000
Bad moves................: 0
Total gems removed.......: 1179950
Average score per move...: ??? points
Move with highest score..: #??? (??? points)

Als het goed is is mijn RML redelijk conform wat hier reeds gehanteerd wordt.

RobIII wijzigde dit bericht 31-10-2008 17:38 (97%)

quote:

JMfx schreef op vrijdag 31 oktober 2008 @ 12:22:
code:

1 2 3 0 3 2 1
0 0 0 0 0 0 0
0 0 0 0 0 0 0

Je verzilvert alle 15 nullen: 250 punten.

Volgens mij: 2 rijen van 7 en 1 rij van 3, dus 550 punten?
Inderdaad, 250 punten. Ik lees nu een zin in de topicstart die ik nog niet eerder heb gezien.

Confusion wijzigde dit bericht 31-10-2008 17:33 (16%)

Hoera mijn punten telling + mijn blokjes vind algoritme ook werkt nu ook

Ik heb ook 1950 punten bij het eerste veld voor de zetten.

Ik heb ook even wat in elkaar geprogramuleerd, en ik kom idd ook op 1950. Bij een simpele speler komt mijn prog ieder geval helemaal overeen met die van .oisyn, qau score en eindstand.

Ik zal morgen ofzo ook even een validator bouwen die wat mooiere output geeft.

Woy wijzigde dit bericht 31-10-2008 19:39 (4%)

Je bedoelt waarbij je de zet kiest die de meeste score oplevert? Op zich grappig dat je dan exact dezelfde uitkomst krijgt, dat betekent dat je de kandidaten in dezelfde volgorde afgaat (je zou immers een andere zet kunnen doen als die andere zet net zoveel punten oplevert)

Zo, ik kijk even een paar dagen niet op Tweakers, en ik heb al weer heel wat gemist. Er is niet alleen een nieuwe Programming Contest aangekondigd, maar er zijn ook gelijk tien pagina's met reacties en mensen die al bijna klaar zijn met hun oplossing terwijl ik nog moet beginnen.

Maar ik doe deze keer weer mee, als ik tenminste genoeg tijd heb om iets te maken dat redelijk werkt. Net als bij de vorige Programming Contest zal mijn oplossing weer in C# zijn.

quote:

.oisyn schreef op vrijdag 31 oktober 2008 @ 19:47:
Je bedoelt waarbij je de zet kiest die de meeste score oplevert? Op zich grappig dat je dan exact dezelfde uitkomst krijgt, dat betekent dat je de kandidaten in dezelfde volgorde afgaat (je zou immers een andere zet kunnen doen als die andere zet net zoveel punten oplevert)

Ik neem aan dat hij doelde op je allereerste AI, die gewoon de eerste de beste zet die hij zag deed.

Dat maakt het alleen maar nog meer toevallig . Als je altijd de move met de meeste punten kiest is de kans groter dat je steeds dezelfde moves doet dan als je gewoon maar de eerste de beste move kiest.

Bovendien heb ik van die oude geen geldige output, wegens die bug in m'n framework, dus als rwb dezelfde uitvoer krijgt als mijn eerste AI dan heeft hij ook last van die bug

Nog tijd zat om te bugfixen

Nee ik bedoel dat als ik mijn output door jouw validator heen haal dat ik dezelde eindposities krijgen en dezelfde score.

Dus bij de zetten die ik doe, geeft jouw programma dezelfde output.

Het is overigens nog de versie die de eerste zet kiest, maar hij berekent al wel alle opties, dus het is één regel code veranderen om dat in de zet met de meeste punten te veranderen.

Woy wijzigde dit bericht 01-11-2008 01:25 (54%)

Zo, een heel stuk verder nu

met snelheid zit het wel goed, als ik steeds de eerste zet kies dan doet m'n prog 100000 zetten in 1.4sec

hierbij haalt ie maar een score van 8674850, dus nu wordt het tijd om deze wat op te krikken.

Ik heb de mijne net ook ietwat geoptimized. De AI die steeds de move kiest die het meeste punten oplevert (wat simpelweg betekent dat ie alle mogelijke kandidaten letterlijk probeert, en dan vanuit de state met de meeste punten verder gaat) dan deed ie ~30 seconden over de 100.000 moves, wat 3242.43 moves/s is.

Na m'n optimalisatie doet ie er echter nog maar 6.4s over (15610.3 moves/s). Met m'n oude AI, die ook gewoon de eerste de beste pakt, doet ie er 0.76s over (130900 moves/s)

Core 2 (Duo, maar gebruikt maar 1 thread) @ 3.2 GHz.

.edit: frappant, de 64 bits versie van m'n best-move-solver haalt maar ~13800 moves/s. Ik had verwacht dat het wel iets sneller zou zijn maar dat is dus duidelijk niet het geval . Zelfs met profile guided optimizations kom ik niet op het niveau van de 32 bits versie.

Dus, -NMe-, laat die Win XP x64 maar zitten

.edit2: Met profile guided optimizations haal ik met 32 bits wel 100.000 moves in 5.7s (17392.7 moves/s)
.edit3: Inmiddels ben ik terug naar 4.9s

.oisyn wijzigde dit bericht 01-11-2008 04:16 (35%)

quote:

.oisyn schreef op zaterdag 01 november 2008 @ 02:36:
Dus, -NMe-, laat die Win XP x64 maar zitten

\o/

quote:

.oisyn schreef op vrijdag 31 oktober 2008 @ 12:30:
[...]
En een nieuwe run van mijn AI: http://oisyn.nl/gc/uitvoer3.zip

.
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
0
4
6
4
2
1
4
3
1
2
2
1
4
5
6
3
1
5
6
3
1
6
6
4
1
3
1
2
5
6
5
3
6
3
5
3
1
4
3
4
5
2
6
2
1
2
3
2
5
4
2
2
2
x
4
2
6
4
5
2
5
4
1
5
2
6
1
4
5
1
2
4
4
6
2
1
3
x
3
x
5
3
5
4
1
5
4
4
6
1
4
1
5
2
5
3
1
5
1
2
1
x
x
x
4
x
6
1
3
6
2
1
1
3
4
6
2
5
6
4
6
1
6
3
5
6
5
x
x
x
5
x
x
4
2
5
4
2
3
1
5
4
1
6
3
1
5
4
2
1
1
4
5
x
x
x
6
x
x
3
4
2
3
6
4
4
6
5
1
5
6
3
4
5
x
3
4
4
x
x
x
x
7
x
x
5
1
6
1
3
4
1
1
4
2
5
5
2
2
x
x
x
x
x
x
x
x
x
8
x
x
4
2
4
5
5
3
1
3
6
3
3
1
4
x
x
x
x
x
x
x
x
x
x
9
x
x
3
3
2
5
2
6
3
5
1
x
x
5
x
x
x
x
x
x
x
x
x
x
x
10
x
x
x
5
1
3
1
6
2
5
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
11
x
x
x
x
x
x
x
3
1
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
12
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
13
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
Score....................: 24256450 points
Total moves..............: 100000
Succesful moves..........: 100000
Bad moves................: 0
Average score per move...: 242 points
Move with highest score..: #7218 (1750 points)

Mijn AI die elke keer de beste pakt heeft net een iets andere uitslag

.
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
0
4
6
4
5
4
4
5
6
4
1
4
4
5
6
1
5
3
4
4
6
4
2
1
6
3
1
4
2
5
6
5
2
6
5
3
1
5
2
4
5
6
1
4
5
2
5
6
6
5
2
3
2
x
5
6
4
3
3
5
4
1
4
5
3
2
5
3
6
5
6
4
1
1
2
1
1
x
3
x
6
1
3
2
5
2
4
2
6
6
2
6
1
2
5
1
3
6
2
3
5
x
x
x
4
x
6
6
5
6
6
3
6
4
5
6
5
3
6
4
4
6
3
5
3
4
3
x
x
x
5
x
x
5
3
2
1
1
2
2
4
1
5
4
1
2
3
1
6
5
1
1
3
x
x
x
6
x
x
3
6
5
4
1
4
5
5
2
1
6
4
4
3
5
x
4
5
6
x
x
x
x
7
x
x
6
2
4
4
5
2
1
4
6
2
1
3
3
2
x
x
x
x
x
x
x
x
x
8
x
x
1
3
5
3
6
4
1
3
3
2
4
5
6
x
x
x
x
x
x
x
x
x
x
9
x
x
6
5
6
5
1
3
6
2
5
x
x
2
x
x
x
x
x
x
x
x
x
x
x
10
x
x
x
3
1
4
5
6
4
3
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
11
x
x
x
x
x
x
x
5
2
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
12
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
13
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
Score....................: 24303350 points
Total moves..............: 100000
Succesful moves..........: 100000
Bad moves................: 0
Average score per move...: 243 points
Move with highest score..: #17330 (1550 points)

Uitvoer
Wel grappig om te zien dat jouw beste zet wel hoger is ( 1750 tegen 1550 ), maar dat de uitslag uiteindelijk wel lager is. Blijkbaar lopen we wel op een andere manier door de mogenlijkheden heen

Ook ik ben ondertussen zover dat mijn AI de beste zet kan pakken en uitvoeren. Scores van mijn programma komen mooi overeen met wat .oisyns en phsmits validators. Voor 100000 zetten op de testset kost dit nog wel 17 seconden (Core 2 Duo T7200 2 GHz), maar dit kan nog flink verbeteren.

Resultaat:
.oisyn's validator

.
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
0
1
2
4
5
4
6
2
1
5
3
5
1
2
1
3
2
6
2
4
3
1
6
3
3
2
1
3
5
4
3
6
1
5
3
6
2
1
3
4
6
2
4
4
5
2
2
1
3
4
6
3
2
x
1
5
1
6
5
6
2
1
4
6
2
4
5
3
3
1
5
3
6
4
2
5
1
x
3
x
5
1
2
5
6
5
1
6
2
6
4
3
5
4
5
2
6
5
5
3
3
x
x
x
4
x
6
1
1
6
5
2
4
4
5
4
2
6
3
5
6
3
4
2
6
4
1
x
x
x
5
x
x
6
4
4
6
1
6
3
4
5
1
4
3
6
5
2
6
5
1
3
5
x
x
x
6
x
x
4
1
1
4
6
5
5
6
4
2
1
5
3
6
3
x
4
6
2
x
x
x
x
7
x
x
3
1
6
4
3
4
4
1
1
3
4
3
2
5
x
x
x
x
x
x
x
x
x
8
x
x
5
4
3
6
1
5
1
2
1
1
5
3
4
x
x
x
x
x
x
x
x
x
x
9
x
x
1
6
1
2
5
4
5
4
5
x
x
1
x
x
x
x
x
x
x
x
x
x
x
10
x
x
x
6
4
4
1
1
2
6
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
11
x
x
x
x
x
x
x
5
4
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
12
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
13
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
Score....................: 23540950 points
Total moves..............: 100000
Succesful moves..........: 100000
Bad moves................: 0
Average score per move...: 235 points
Move with highest score..: #1525 (1500 points)

quote:

.oisyn schreef op zaterdag 01 november 2008 @ 02:36:

[...]

blabla.. mijn oplossing is frikkin snel.. blabla

[...]

hmm, dat lees ik met gemende gevoelens.. enerzijds ben ik een huge fan van Deus Ex, en krijg ik het gevoel dat het wel goed komt met die TR engine
anderzijds moet ik toch meer tijd in deze contest gaan steken dan aanvankelijk verwacht..

mooie resultaten

Het initiele speelveld ziet er bij mij als volgt uit:

.
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
13
5
5
5
5
4
1
3
1
3
6
5
6
3
6
6
4
1
2
5
5
6
5
6
6
6
12
1
5
5
3
6
2
2
3
1
1
3
5
3
5
1
6
6
5
4
4
6
4
6
5
6
11
X
6
6
4
6
6
6
2
2
6
5
1
6
6
5
5
4
4
6
6
4
6
5
4
X
10
X
1
4
1
5
5
5
5
5
4
4
4
6
5
6
3
1
2
1
5
2
5
X
X
X
9
X
4
4
2
6
6
3
1
6
6
3
3
5
4
1
6
2
1
2
6
6
6
X
X
X
8
X
X
5
5
4
4
1
5
5
5
2
2
3
4
4
4
6
4
4
4
4
4
X
X
X
7
X
X
5
6
5
2
2
5
4
4
4
4
4
5
4
5
3
X
6
6
2
X
X
X
X
6
X
X
6
6
3
3
5
6
6
5
6
3
4
3
3
3
X
X
X
X
X
X
X
X
X
5
X
X
1
5
1
1
6
4
5
6
4
2
2
2
4
X
X
X
X
X
X
X
X
X
X
4
X
X
1
3
2
4
5
5
6
5
5
X
X
4
X
X
X
X
X
X
X
X
X
X
X
3
X
X
X
1
2
2
3
6
5
4
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
2
X
X
X
X
X
X
X
1
6
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
1
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X

Hierin identificeer ik de combinaties
code:

[(0, 13), (1, 13), (2, 13), (3, 13)], 
[(4, 10), (5, 10), (6, 10), (7, 10), (8, 10)], 
[(4, 11), (5, 11), (6, 11)], 
[(7, 8), (8, 8), (9, 8)], 
[(8, 7), (9, 7), (10, 7), (11, 7), (12, 7)], 
[(9, 10), (10, 10), (11, 10)], 
[(11, 5), (12, 5), (13, 5)], 
[(13, 6), (14, 6), (15, 6)], 
[(13, 8), (14, 8), (15, 8)], 
[(17, 8), (18, 8), (19, 8), (20, 8), (21, 8)], 
[(19, 9), (20, 9), (21, 9)], 
[(22, 13), (23, 13), (24, 13)]

maar dat is samen maar 1250 punten. Die 1950 punten gelden pas zodra het veld stabiel is geworden? In dat geval heb ik een bug, want ik tel dan 2250 punten...

quote:

Confusion schreef op zaterdag 01 november 2008 @ 12:30:
Het initiele speelveld ziet er bij mij als volgt uit:

.
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
13
5
5
5
5
4
1
3
1
3
6
5
6
3
6
6
4
1
2
5
5
6
5
6
6
6
12
1
5
5
3
6
2
2
3
1
1
3
5
3
5
1
6
6
5
4
4
6
4
6
5
6
11
X
6
6
4
6
6
6
2
2
6
5
1
6
6
5
5
4
4
6
6
4
6
5
4
X
10
X
1
4
1
5
5
5
5
5
4
4
4
6
5
6
3
1
2
1
5
2
5
X
X
X
9
X
4
4
2
6
6
3
1
6
6
3
3
5
4
1
6
2
1
2
6
6
6
X
X
X
8
X
X
5
5
4
4
1
5
5
5
2
2
3
4
4
4
6
4
4
4
4
4
X
X
X
7
X
X
5
6
5
2
2
5
4
4
4
4
4
5
4
5
3
X
6
6
2
X
X
X
X
6
X
X
6
6
3
3
5
6
6
5
6
3
4
3
3
3
X
X
X
X
X
X
X
X
X
5
X
X
1
5
1
1
6
4
5
6
4
2
2
2
4
X
X
X
X
X
X
X
X
X
X
4
X
X
1
3
2
4
5
5
6
5
5
X
X
4
X
X
X
X
X
X
X
X
X
X
X
3
X
X
X
1
2
2
3
6
5
4
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
2
X
X
X
X
X
X
X
1
6
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
1
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X

Hierin identificeer ik de combinaties
code:

[(0, 13), (1, 13), (2, 13), (3, 13)], 
[(4, 10), (5, 10), (6, 10), (7, 10), (8, 10)], 
[(4, 11), (5, 11), (6, 11)], 
[(7, 8), (8, 8), (9, 8)], 
[(8, 7), (9, 7), (10, 7), (11, 7), (12, 7)], 
[(9, 10), (10, 10), (11, 10)], 
[(11, 5), (12, 5), (13, 5)], 
[(13, 6), (14, 6), (15, 6)], 
[(13, 8), (14, 8), (15, 8)], 
[(17, 8), (18, 8), (19, 8), (20, 8), (21, 8)], 
[(19, 9), (20, 9), (21, 9)], 
[(22, 13), (23, 13), (24, 13)]

maar dat is samen maar 1250 punten. Die 1950 punten gelden pas zodra het veld stabiel is geworden? In dat geval heb ik een bug, want ik tel dan 2250 punten...

euh... als je dit laat vallen, ontstaan er weer nieuwe rijen?

quote:

Confusion schreef op zaterdag 01 november 2008 @ 12:30:
Het initiele speelveld ziet er bij mij als volgt uit:

.
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
13
5
5
5
5
4
1
3
1
3
6
5
6
3
6
6
4
1
2
5
5
6
5
6
6
6
12
1
5
5
3
6
2
2
3
1
1
3
5
3
5
1
6
6
5
4
4
6
4
6
5
6
11
X
6
6
4
6
6
6
2
2
6
5
1
6
6
5
5
4
4
6
6
4
6
5
4
X
10
X
1
4
1
5
5
5
5
5
4
4
4
6
5
6
3
1
2
1
5
2
5
X
X
X
9
X
4
4
2
6
6
3
1
6
6
3
3
5
4
1
6
2
1
2
6
6
6
X
X
X
8
X
X
5
5
4
4
1
5
5
5
2
2
3
4
4
4
6
4
4
4
4
4
X
X
X
7
X
X
5
6
5
2
2
5
4
4
4
4
4
5
4
5
3
X
6
6
2
X
X
X
X
6
X
X
6
6
3
3
5
6
6
5
6
3
4
3
3
3
X
X
X
X
X
X
X
X
X
5
X
X
1
5
1
1
6
4
5
6
4
2
2
2
4
X
X
X
X
X
X
X
X
X
X
4
X
X
1
3
2
4
5
5
6
5
5
X
X
4
X
X
X
X
X
X
X
X
X
X
X
3
X
X
X
1
2
2
3
6
5
4
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
2
X
X
X
X
X
X
X
1
6
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
1
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X

Hierin identificeer ik de combinaties
code:

[(0, 13), (1, 13), (2, 13), (3, 13)], 
[(4, 10), (5, 10), (6, 10), (7, 10), (8, 10)], 
[(4, 11), (5, 11), (6, 11)], 
[(7, 8), (8, 8), (9, 8)], 
[(8, 7), (9, 7), (10, 7), (11, 7), (12, 7)], 
[(9, 10), (10, 10), (11, 10)], 
[(11, 5), (12, 5), (13, 5)], 
[(13, 6), (14, 6), (15, 6)], 
[(13, 8), (14, 8), (15, 8)], 
[(17, 8), (18, 8), (19, 8), (20, 8), (21, 8)], 
[(19, 9), (20, 9), (21, 9)], 
[(22, 13), (23, 13), (24, 13)]

maar dat is samen maar 1250 punten. Die 1950 punten gelden pas zodra het veld stabiel is geworden? In dat geval heb ik een bug, want ik tel dan 2250 punten...

Idd als het veld voor het eerst "stabiel" is dan zit je op 1950 punten, dus ik denk dat je een bug hebt.

quote:

rwb schreef op zaterdag 01 november 2008 @ 13:10:
Idd als het veld voor het eerst "stabiel" is dan zit je op 1950 punten, dus ik denk dat je een bug hebt.

Yup, found it. Als je bijvoorbeeld het veld van linksonder naar rechtsboven afloopt, waarbij je telkens eerst kolommen afmaakt, dan ontstaat er een asymmetrie: een combinatie kan nooit westwaarts uitlopen (want daar ben je al geweest met zoeken naar combinaties), maar wel zuidwaarts vanaf een oostelijk punt in de combinatie. Ik had die asymmetrie gemist, waardoor een kruis als twee losse rijen van drie gezien werd. (Daarmee zou ik lager uit moeten komen en er zat inderdaad nog een ander bugje in, maar die was te flauw om te noemen, terwijl deze nog wel nuttig voor anderen kan zijn).

Confusion wijzigde dit bericht 01-11-2008 16:43 (0%)
Reden: figuur == combinatie in mijn code

Het kán wel west gaan, theoretisch.

Als je van boven naar beneden zoekt, en van links naar rechts kan je deze combinatie tegenkomen:


Maar dan moet het wel heel erg bont gaan natuurlijk.

quote:

Megamind schreef op zaterdag 01 november 2008 @ 16:58:
Het kán wel west gaan, theoretisch.

Hmm, die had ik nog niet bedacht. Inderdaad, het kan niet alleen zuid, maar ook west.

Kortom, toeval dat ik eindelijk ook op 1950 uitkwam...

Confusion, even over de coordinaten, de TS meldt dat 0, 0 helemaal linksboven staat:

quote:

De linkerkolom en de bovenste rij hebben beiden het nummer 0, dus bovenstaand speelveld heeft coördinaten van 0 tot 24 op de x-as en van 0 tot 14 op de y-as.

quote:

rwb schreef op zaterdag 01 november 2008 @ 09:24:
[...]

Mijn AI die elke keer de beste pakt heeft net een iets andere uitslag

.
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
0
4
6
4
5
4
4
5
6
4
1
4
4
5
6
1
5
3
4
4
6
4
2
1
6
3
1
4
2
5
6
5
2
6
5
3
1
5
2
4
5
6
1
4
5
2
5
6
6
5
2
3
2
x
5
6
4
3
3
5
4
1
4
5
3
2
5
3
6
5
6
4
1
1
2
1
1
x
3
x
6
1
3
2
5
2
4
2
6
6
2
6
1
2
5
1
3
6
2
3
5
x
x
x
4
x
6
6
5
6
6
3
6
4
5
6
5
3
6
4
4
6
3
5
3
4
3
x
x
x
5
x
x
5
3
2
1
1
2
2
4
1
5
4
1
2
3
1
6
5
1
1
3
x
x
x
6
x
x
3
6
5
4
1
4
5
5
2
1
6
4
4
3
5
x
4
5
6
x
x
x
x
7
x
x
6
2
4
4
5
2
1
4
6
2
1
3
3
2
x
x
x
x
x
x
x
x
x
8
x
x
1
3
5
3
6
4
1
3
3
2
4
5
6
x
x
x
x
x
x
x
x
x
x
9
x
x
6
5
6
5
1
3
6
2
5
x
x
2
x
x
x
x
x
x
x
x
x
x
x
10
x
x
x
3
1
4
5
6
4
3
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
11
x
x
x
x
x
x
x
5
2
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
12
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
13
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
Score....................: 24303350 points
Total moves..............: 100000
Succesful moves..........: 100000
Bad moves................: 0
Average score per move...: 243 points
Move with highest score..: #17330 (1550 points)

Uitvoer
Wel grappig om te zien dat jouw beste zet wel hoger is ( 1750 tegen 1550 ), maar dat de uitslag uiteindelijk wel lager is. Blijkbaar lopen we wel op een andere manier door de mogenlijkheden heen

MIJN PUNTENTELLING KLOPT ZÉÉÉÉR WAARSCHIJNLIJK (NOG) NIET. Fixed
Die is namelijk tussen de soep en aardappelen door geschreven en ik heb nog met geen enkel resultaat dezelfde punten behaald als de deelnemer beweert; in dat geval is de kans dus erg groot dat ik er langs zit

.
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
0
4
6
4
5
4
4
5
6
4
1
4
4
5
6
1
5
3
4
4
6
4
2
1
6
3
1
4
2
5
6
5
2
6
5
3
1
5
2
4
5
6
1
4
5
2
5
6
6
5
2
3
2
x
5
6
4
3
3
5
4
1
4
5
3
2
5
3
6
5
6
4
1
1
2
1
1
x
3
x
6
1
3
2
5
2
4
2
6
6
2
6
1
2
5
1
3
6
2
3
5
x
x
x
4
x
6
6
5
6
6
3
6
4
5
6
5
3
6
4
4
6
3
5
3
4
3
x
x
x
5
x
x
5
3
2
1
1
2
2
4
1
5
4
1
2
3
1
6
5
1
1
3
x
x
x
6
x
x
3
6
5
4
1
4
5
5
2
1
6
4
4
3
5
x
4
5
6
x
x
x
x
7
x
x
6
2
4
4
5
2
1
4
6
2
1
3
3
2
x
x
x
x
x
x
x
x
x
8
x
x
1
3
5
3
6
4
1
3
3
2
4
5
6
x
x
x
x
x
x
x
x
x
x
9
x
x
6
5
6
5
1
3
6
2
5
x
x
2
x
x
x
x
x
x
x
x
x
x
x
10
x
x
x
3
1
4
5
6
4
3
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
11
x
x
x
x
x
x
x
5
2
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
12
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
13
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
Score....................: 24303350 points
Total moves..............: 100000
Succesful moves..........: 100000
Bad moves................: 0
Total gems removed.......: 1253659
Average score per move...: 243,03 points
Move with highest score..: #17330 (1550 points)

RobIII wijzigde dit bericht 03-11-2008 02:19 (200%)
Reden: 1 bug minder.... 1 to go :P

quote:

BalusC schreef op zaterdag 01 november 2008 @ 17:54:
Confusion, even over de coordinaten, de TS meldt dat 0, 0 helemaal linksboven staat:

Klopt, maar omdat ik merk dat ik beter over het probleem na kan denken, en beter kan debuggen, als de coordinaten zo zijn, hanteer ik intern overal in mijn programma de coordinaten zoals ze in het plaatje staan. In de functie die ze 'exporteert' zet ik ze om naar de coordinaten die de spelleiding vereist. Het is een klein risico, maar van 'clockwise' assenstelsels krijg ik de kriebels.

quote:

RobIII schreef op zaterdag 01 november 2008 @ 19:03:
[...]

MIJN PUNTENTELLING KLOPT ZÉÉÉÉR WAARSCHIJNLIJK (NOG) NIET.
Die is namelijk tussen de soep en aardappelen door geschreven en ik heb nog met geen enkel resultaat dezelfde punten behaald als de deelnemer beweert; in dat geval is de kans dus erg groot dat ik er langs zit

.
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
0
4
6
4
5
4
4
5
6
4
1
4
4
5
6
1
5
3
4
4
6
4
2
1
6
3
1
4
2
5
6
5
2
6
5
3
1
5
2
4
5
6
1
4
5
2
5
6
6
5
2
3
2
x
5
6
4
3
3
5
4
1
4
5
3
2
5
3
6
5
6
4
1
1
2
1
1
x
3
x
6
1
3
2
5
2
4
2
6
6
2
6
1
2
5
1
3
6
2
3
5
x
x
x
4
x
6
6
5
6
6
3
6
4
5
6
5
3
6
4
4
6
3
5
3
4
3
x
x
x
5
x
x
5
3
2
1
1
2
2
4
1
5
4
1
2
3
1
6
5
1
1
3
x
x
x
6
x
x
3
6
5
4
1
4
5
5
2
1
6
4
4
3
5
x
4
5
6
x
x
x
x
7
x
x
6
2
4
4
5
2
1
4
6
2
1
3
3
2
x
x
x
x
x
x
x
x
x
8
x
x
1
3
5
3
6
4
1
3
3
2
4
5
6
x
x
x
x
x
x
x
x
x
x
9
x
x
6
5
6
5
1
3
6
2
5
x
x
2
x
x
x
x
x
x
x
x
x
x
x
10
x
x
x
3
1
4
5
6
4
3
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
11
x
x
x
x
x
x
x
5
2
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
12
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
13
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
Score....................: 25560800 points
Total moves..............: 100000
Succesful moves..........: 100000
Bad moves................: 0
Total gems removed.......: 1181033
Average score per move...: 255,61 points
Move with highest score..: #??? (??? points)

De punten die mijn programma geeft komen ieder geval overeen met de validator van .oisyn, dus dat lijkt te kloppen ( Of we hebben beide dezelfde fout erin zitten ).

quote:

Confusion schreef op zaterdag 01 november 2008 @ 20:52:
Het is een klein risico, maar van 'clockwise' assenstelsels krijg ik de kriebels.

Heh ja, bekend probleem. Vroeger althans. Inmiddels heb ik met zoveel verschillende assenstelsels moeten werken (+y up +z forward (d3d), +y up -z forward (opengl), +z up +y forward (max, maya, onze games), en dan nog de verschillen tussen left- en righthandedness, de verschillen tussen row vectoren en column vectoren, etc.) dat het me inmiddels echt geen drol meer uitmaakt en het gewoon even een kwestie van een schakel in m'n hoofd omzetten is

ik heb een klein verschil in score als ik kijk naar m'n eigen programma en .oisyn's validator.

   0 1 2 3 4 5 6 7 8 910 1 2 3 4 5 6 7 8 920 1 2 3 4
 0 2 5 6 5 1 2 1 4 5 6 6 1 3 5 6 3 1 4 5 2 2 3 6 1 4 
 1 1 2 1 4 6 3 2 6 4 1 5 2 6 3 1 4 2 4 1 5 5 3 5 6 2 
 2   5 6 1 5 1 5 5 6 5 1 3 5 2 3 5 3 5 2 6 6 2 4 2   
 3   6 4 2 4 4 6 3 3 6 4 2 4 1 2 5 4 1 2 5 6 1       
 4   1 3 5 3 1 5 1 2 1 1 3 1 6 3 1 4 5 5 4 2 5       
 5     2 5 2 4 2 4 5 1 5 6 4 5 4 1 1 2 4 6 5 4       
 6     4 2 6 1 5 3 6 3 4 3 6 3 5 4 2   1 2 4         
 7     1 3 4 2 2 1 5 4 1 1 2 2 1 2                   
 8     5 5 1 6 5 1 6 3 6 1 5 3 3                     
 9     6 6 5 3 3 2 4 2 6     4                       
10       2 2 1 3 4 6 2                               
 1               4 4                                 
score: 23943350, moves: 100000

real	0m37.167s
user	0m36.313s
sys	0m0.155s
MacBook-Pro-van-Arjan-Houben:debug arjan$ wine validator.exe -rml
.oisyn's validator

.
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
0
2
5
6
5
1
2
1
4
5
6
6
1
3
5
6
3
1
4
5
2
2
3
6
1
4
1
1
2
1
4
6
3
2
6
4
1
5
2
6
3
1
4
2
4
1
5
5
3
5
6
2
2
x
5
6
1
5
1
5
5
6
5
1
3
5
2
3
5
3
5
2
6
6
2
4
2
x
3
x
6
4
2
4
4
6
3
3
6
4
2
4
1
2
5
4
1
2
5
6
1
x
x
x
4
x
1
3
5
3
1
5
1
2
1
1
3
1
6
3
1
4
5
5
4
2
5
x
x
x
5
x
x
2
5
2
4
2
4
5
1
5
6
4
5
4
1
1
2
4
6
5
4
x
x
x
6
x
x
4
2
6
1
5
3
6
3
4
3
6
3
5
4
2
x
1
2
4
x
x
x
x
7
x
x
1
3
4
2
2
1
5
4
1
1
2
2
1
2
x
x
x
x
x
x
x
x
x
8
x
x
5
5
1
6
5
1
6
3
6
1
5
3
3
x
x
x
x
x
x
x
x
x
x
9
x
x
6
6
5
3
3
2
4
2
6
x
x
4
x
x
x
x
x
x
x
x
x
x
x
10
x
x
x
2
2
1
3
4
6
2
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
11
x
x
x
x
x
x
x
4
4
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
12
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
13
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
Score....................: 23941050 points
Total moves..............: 100000
Succesful moves..........: 100000
Bad moves................: 0
Average score per move...: 239 points
Move with highest score..: #70393 (1850 points)

is er enige manier om dit te debuggen met deze validator? (score per zet ofzo)

Gebruik -m #move om te stoppen na die move (hoewel de versie die online staat volgens mij wel 1 move te veel of te weinig doet, controleer dus even het aantal moves in de output ), en met -d #move om te kijken wat er gebeurt bij die move (hij geeft stapsgewijs de veranderingen aan het veld weer, druk op een willekeurige toets om naar de volgende stap te gaan - geen idee hoe goed dit werkt onder wine trouwens, phsmit had er eerder ook al problemen mee als ik me niet vergis).

Met -u geeft ie gewoon continu output na elke move, maar wel inclusief speelveld, dus bij 100.000 moves lijkt me dat wat onhandig .

Ik zou een handmatige binary search doen met de -m optie om vast te stellen waar het fout gaat (kost hooguit 17 pogingen )

.oisyn wijzigde dit bericht 02-11-2008 00:46 (63%)

Bah, m'n optimalisaties maken de boel wel moeilijk vergelijkbaar, omdat de volgorde van mogelijke kandidaat-zetten af en toe wijzigt waardoor er ineens een heel ander pad wordt gekozen. Ik moet de boel eens wat deterministischer maken (zo van, als twee kandidaten een gelijke score opleveren neem dan de meest linkse/bovenste oid)

.edit: voor degene die hun soortgelijke AI willen vergelijken, als ik de move kies met de hoogste punten en de laagste x, y en richting-waarde (in die volgorde, waarbij O < Z en N en W nooit gebruikt worden, oftewel 3 5 W => 2 5 O), dan kom ik op de volgende uitslag: http://oisyn.nl/gc/uitvoer4.zip

.
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
0
4
6
4
5
4
4
5
6
4
1
4
4
5
6
1
5
3
4
4
6
4
2
1
6
3
1
4
2
5
6
5
2
6
5
3
1
5
2
4
5
6
1
4
5
2
5
6
6
5
2
3
2
x
5
6
4
3
3
5
4
1
4
5
3
2
5
3
6
5
6
4
1
1
2
1
1
x
3
x
6
1
3
2
5
2
4
2
6
6
2
6
1
2
5
1
3
6
2
3
5
x
x
x
4
x
6
6
5
6
6
3
6
4
5
6
5
3
6
4
4
6
3
5
3
4
3
x
x
x
5
x
x
5
3
2
1
1
2
2
4
1
5
4
1
2
3
1
6
5
1
1
3
x
x
x
6
x
x
3
6
5
4
1
4
5
5
2
1
6
4
4
3
5
x
4
5
6
x
x
x
x
7
x
x
6
2
4
4
5
2
1
4
6
2
1
3
3
2
x
x
x
x
x
x
x
x
x
8
x
x
1
3
5
3
6
4
1
3
3
2
4
5
6
x
x
x
x
x
x
x
x
x
x
9
x
x
6
5
6
5
1
3
6
2
5
x
x
2
x
x
x
x
x
x
x
x
x
x
x
10
x
x
x
3
1
4
5
6
4
3
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
11
x
x
x
x
x
x
x
5
2
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
12
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
13
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
Score....................: 24303350 points
Total moves..............: 100000
Succesful moves..........: 100000
Bad moves................: 0
Average score per move...: 243 points
Move with highest score..: #17330 (1550 points)

(in 4.7s op een core 2 @ 3.2 GHz )

.edit2: heh, ik zie nu dat die output file exact identiek is aan degene die rwb heeft . Hoe snel was jij, rwb?

.oisyn wijzigde dit bericht 02-11-2008 04:49 (98%)

Ik doe ook voor eerste keer mee. (A)

En eerste keer dat ik er wat mee doe begint het al goed, vannacht om uurtje of 1 mee begonnen, even een klein beginnetje maken...

Hij kan nu de files inladen, veld opbouwen, blokjes erin gooien, de blokjes die weg mogen weghalen en de punten daarvan optellen. En daarna uiteraard weer nieuwe blokjes er in. Best nog wel grappige oplossing voor (in PHP) al zeg ik het zelf.

1950 bij "stabiel" was goed toch?

edit: grr, net werkte hij en nu zit hij opeens in een loopje...

GuidoH wijzigde dit bericht 02-11-2008 07:24 (8%)

Pff wat zijn sommige al ver zeg! Ik moet nog beginnen. Op zich moet het framework wel te bouwen zijn en draait de contest uiteindelijk natuurlijk om de AI.

Er is nogal wat discussie geweest omtrent de definitie van een 'set' stenen die weggespeeld kunnen worden. Dit is me nu helemaal duidelijk. Zoals al eerder opgemerkt werkt het flood fill algortime hierbij niet. Heeft iedereen zijn eigen implementatie hiervoor verzonnen? Of slechts een aanpassing van een bestaand algoritme? Dit is namelijk nog een van de punten die mij het lastigste lijkt in het framework.

quote:

.oisyn schreef op zondag 02 november 2008 @ 04:33:

.edit: voor degene die hun soortgelijke AI willen vergelijken, als ik de move kies met de hoogste punten en de laagste x, y en richting-waarde (in die volgorde, waarbij O < Z en N en W nooit gebruikt worden, oftewel 3 5 W => 2 5 O), dan kom ik op de volgende uitslag: http://oisyn.nl/gc/uitvoer4.zip
...snip uitslag ...

(in 4.7s op een core 2 @ 3.2 GHz )

Handig om zo te vergelijken, mijn AI kan levert exact dezelfde output (gegeven de bovenstaande voorwaarden), maar is nog een stuk langzamer. 17.2s op een core 2 @ 2.0 GHz

(Bij het vergelijken vond ik nog een fout in mijn move-generator, bepaalde mogelijkheden werden niet aangemerkt als mogelijke zet)

1250 punten na een eerste telling (na de eerste drop en voor de tweede) klopt dat?
dan zou m'n telling kloppen..

quote:

era.zer schreef op zondag 02 november 2008 @ 11:24:
1250 punten na een eerste telling (na de eerste drop en voor de tweede) klopt dat?
dan zou m'n telling kloppen..

Hier heb ik dat ook... Maar het zou ook kunnen dat we het allebei verkeerd hebben.

quote:

GuidoH schreef op zondag 02 november 2008 @ 11:53:
[...]

Hier heb ik dat ook... Maar het zou ook kunnen dat we het allebei verkeerd hebben.

hier ook. na een tweede drop (van 700) kom je op 1950.

oisyn had dat ook, dus het lijkt juist (tenzij we allemaal iets over het hoofd zien)

Dat zal wel niet. Dan ben ik blij, het heeft me wat tijd gekost om iets mooi en efficient te maken.
Die tweede drop kan ik nog niet doen, ik moet nog uitvissen hoe ik de te droppen-stenen moet vinden

Fastman wijzigde dit bericht 02-11-2008 12:04 (48%)

Draaien jullie deze keer wel de Java inzendingen in de server VM? Anders staan Java inzendingen al meteen op een achterstand door het niet goed kunnen gebruiken van multicore systemen

De sun jre mapt vziw alle Java threads op 1 native thread in de client vm, wanneer je met -server draait werkt het anders.

Hier een wat slimmere AI op een nog ietwat naïeve manier geïmplementeerd: http://oisyn.nl/gc/uitvoer5.zip

.
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
0
4
2
5
6
6
4
3
1
3
1
3
1
5
6
1
2
3
6
5
5
6
1
5
4
2
1
1
3
6
3
4
6
2
5
1
6
5
3
6
5
1
3
4
6
2
4
2
4
5
2
3
2
x
1
1
5
4
3
3
5
3
6
1
2
5
4
6
6
2
2
4
5
1
6
1
6
x
3
x
5
3
6
6
3
5
6
2
5
5
2
3
3
6
5
1
1
6
4
2
3
x
x
x
4
x
4
6
1
6
4
6
4
3
3
1
1
4
3
5
6
5
4
4
3
4
5
x
x
x
5
x
x
4
2
3
2
2
1
4
2
6
5
3
4
2
3
2
5
6
6
1
5
x
x
x
6
x
x
3
3
2
6
2
3
2
4
4
1
6
2
3
5
1
x
5
4
1
x
x
x
x
7
x
x
4
3
2
3
3
2
2
5
2
2
4
6
4
2
x
x
x
x
x
x
x
x
x
8
x
x
5
1
6
4
3
4
5
1
4
5
2
5
5
x
x
x
x
x
x
x
x
x
x
9
x
x
6
1
4
5
5
6
3
1
6
x
x
5
x
x
x
x
x
x
x
x
x
x
x
10
x
x
x
5
6
1
3
3
6
4
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
11
x
x
x
x
x
x
x
5
1
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
12
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
13
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
Score....................: 42337100 points
Total moves..............: 100000
Succesful moves..........: 100000
Bad moves................: 0
Average score per move...: 423 points
Move with highest score..: #5272 (3000 points)

Wel mooi om move 5272 in real time te zien, het blijft maar vallen
Overigens deed ie hier 3 kwartier over om te genereren, maar zoals ik al zei de implementatie was nog vrij naïef

quote:

Gerco schreef op zondag 02 november 2008 @ 12:41:
De sun jre mapt vziw alle Java threads op 1 native thread in de client vm, wanneer je met -server draait werkt het anders.

In de TS staat toch dat je voor alle dingen waar je afhankelijk van bent uitleg moet meesturen? Als je wil dat we een bepaalde schakeloptie meegeven aan het runnen van jouw Java-programma, dan zul je dat toch even moeten vermelden in je mail.

Vat ik het spelverloop zo goed samen?

1. Je begint met het vullen van het speelveld vanuit de kolommen.
2. Je maakt een zet.
3. Je speelt alle combinaties weg.
4. Je laat de blokjes afzakken naar beneden.
5. Je vult het speelveld aan vanuit de kolommen.
6. Herhaal stappen 3 t/m 5 tot je geen combinaties meer kan wegspelen.
7. Je maakt een nieuwe zet.
Het spel stopt na 100 000 zetten, 15 minuten óf als geen zetten meer mogelijk zijn.


Mijn voorlopige resultaat. Ik moet enkel nog combinaties identificeren en wegspelen en de volgorde van zetten bepalen.

quote:

JMfx schreef op zondag 02 november 2008 @ 14:37:
Vat ik het spelverloop zo goed samen?

1. Je begint met het vullen van het speelveld vanuit de kolommen.
2. Je maakt een zet.
3. Je speelt alle combinaties weg.
4. Je laat de blokjes afzakken naar beneden.
5. Je vult het speelveld aan vanuit de kolommen.
6. Herhaal stappen 3 t/m 5 tot je geen combinaties meer kan wegspelen.
7. Je maakt een nieuwe zet.
Het spel stopt na 100 000 zetten, 15 minuten óf als geen zetten meer mogelijk zijn.

je vergeet dat aan het begin ook alle combinaties weggaan, als het spel gevuld word.

Ik zag het niet helemaal meer zitten, duurt nogal lang en twijfelde of hij het wel goed deed, tot ik de code .oisyn gebruikte en die mooi het volgende gaf:
"#6885: 1 0 Z
Onjuiste zet."

Weet niet wát er precies fout gaat, het duurt tering lang om het zo ver te krijgen maar het begin is er zo te zien.

PHP is hier eigenlijk niet echt geschikt voor of zou het te doen moeten zijn?

GuidoH wijzigde dit bericht 02-11-2008 15:15 (12%)

Als je met "te doen" bedoelt dat je tot een redelijke oplossing kunt komen dan wel. Als je ermee bedoelt dat je kunt competen met de betere implementaties die ingeleverd gaan worden dan denk ik niet .

Natuurlijk hebben optimalisaties van algoritmische aard meer invloed op de performance dan op wat voor manier je code wordt uitgevoerd. Maar in een dergelijke contest als deze is het ook van belang hoe snel je alle mogelijkheden door kunt rekenen - meer mogelijkheden binnen een kwartier kunnen afhandelen betekent vrijwel zeker een hogere score. En dan heb je echt wel veel voordeel door van een snel platform gebruik te maken.

quote:

.oisyn schreef op zondag 02 november 2008 @ 04:33:
(in 4.7s op een core 2 @ 3.2 GHz )

.edit2: heh, ik zie nu dat die output file exact identiek is aan degene die rwb heeft . Hoe snel was jij, rwb?

Mijn oplossing deed er helaas nog +- een minuut over. Ik weet nog wel een simpele optimalisatie waar hij minstens 2 maal zo snel van moet worden. Verder zag ik in de profiler dat er veel tijd in de List<T> class verspild werd, dus daar valt ook nog veel te winnen, door die beter te initialiseren of te vervangen voor array's

Nou is mijn implementatie vooral netjes gebouwd en niet zozeer op de beste performance gelet. Daar kan ik nu wat meer naar gaan kijken.

Ik zit er ook nog over te denken om deze implementatie te porten naar C++, dan kan ik mooi het verschil zien tussen de performance van C# en C++

Woy wijzigde dit bericht 02-11-2008 15:43 (13%)

quote:

RoeAntSte schreef op zondag 02 november 2008 @ 14:45:
[...]


je vergeet dat aan het begin ook alle combinaties weggaan, als het spel gevuld word.

Inderdaad, vergeten. Bedankt.

hmmm ik kap er weer mee voor vandaag.... even een contrast met die <1 seconde algoritmes:

Hij is nu zo ver dat de eerste 10000 beste zetten in 1:46 berekend kunnen worden. En dat is nog niet eens met alle patroonherkenning erin...

toch maar eens gaan kijken hoe ik kan optimaliseren, want de aantallen exploderen wel als je zetten gaat doen. Dat had ik wel verwacht, maar ik had niet verwacht dat het zo heftig zou zijn.

Nevermind, mijn verwachting is gewoon onterecht: het maximaliserende algoritme speelt het spel inderdaad wel uit, maar er zat gewoon een bug in...
Wat mij verbaast is dat naieve algoritmes bij anderen het spel uitspelen. Ik heb tot nu toe drie naieve algoritmes: firstAvailableMove, randomAvailableMove, highestScoringAvailableMove en alledrie lopen ze na pakweg een paar duizend zetten 'vast' in velden waarin geen combinaties meer te maken zijn, zoals onderstaande. Dat was vantevoren ook eigenlijk mijn verwachting. Zijn jullie algoritmes toch niet zo naief of mis ik iets?

@.oisyn: ja sorry, nog niet toegekomen aan het omzetten van de rml output ennu... goed punt, ik moet mijn eigen comments beter lezen, want die heb ik inderdaad nog niet geimplementeerd...

13
6
5
4
3
3
4
6
2
3
4
5
2
3
4
1
3
6
4
2
4
6
5
3
1
4
12
3
6
4
1
4
2
5
1
1
5
4
2
3
4
5
6
1
1
5
3
1
4
3
5
2
11
X
2
3
2
6
2
3
5
6
2
5
1
6
5
6
5
3
3
4
6
4
6
1
4
X
10
X
3
6
4
5
1
5
4
5
1
4
3
6
3
1
6
4
6
4
2
5
6
X
X
X
9
X
5
6
4
3
5
3
5
2
6
5
2
2
3
4
5
6
3
6
3
4
4
X
X
X
8
X
X
3
2
5
3
2
1
6
1
4
5
1
6
4
6
1
2
5
6
3
5
X
X
X
7
X
X
2
1
6
5
2
6
5
5
3
3
4
2
3
5
4
X
6
5
4
X
X
X
X
6
X
X
6
2
4
6
5
3
6
5
4
5
1
6
1
4
X
X
X
X
X
X
X
X
X
5
X
X
3
3
5
1
6
5
3
2
6
1
3
5
5
X
X
X
X
X
X
X
X
X
X
4
X
X
5
2
1
2
3
4
6
1
5
X
X
5
X
X
X
X
X
X
X
X
X
X
X
3
X
X
X
4
6
3
2
6
4
5
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
2
X
X
X
X
X
X
X
4
6
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
1
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
0
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
.
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

Je mist iets, ik zie daar nog heel veel mogelijke moves. Toevallig ook allemaal moves die een blokje ergens tussen schuiven om een rij te maken, ipv blokjes die een eindpunt worden van de te vormen rij. Wellicht vergeet je die case te controleren?

En kun je je output echt niet omdraaien? Dit wordt heel lastig discussieren zo, als jouw velden de hele tijd een geflipte Y-as hebben

.oisyn wijzigde dit bericht 02-11-2008 16:32 (34%)

quote:

Confusion schreef op zondag 02 november 2008 @ 16:26:
Wat mij verbaast is dat naieve algoritmes bij anderen het spel uitspelen. Ik heb tot nu toe drie naieve algoritmes: firstAvailableMove, randomAvailableMove, highestScoringAvailableMove en alledrie lopen ze na pakweg een paar duizend zetten 'vast' in velden waarin geen combinaties meer te maken zijn, zoals onderstaande. Dat was vantevoren ook eigenlijk mijn verwachting. Zijn jullie algoritmes toch niet zo naief of mis ik iets?

13
6
5
4
3
3
4
6
2
3
4
5
2
3
4
1
3
6
4
2
4
6
5
3
1
4
12
3
6
4
1
4
2
5
1
1
5
4
2
3
4
5
6
1
1
5
3
1
4
3
5
2
11
X
2
3
2
6
2
3
5
6
2
5
1
6
5
6
5
3
3
4
6
4
6
1
4
X
10
X
3
6
4
5
1
5
4
5
1
4
3
6
3
1
6
4
6
4
2
5
6
X
X
X
9
X
5
6
4
3
5
3
5
2
6
5
2
2
3
4
5
6
3
6
3
4
4
X
X
X
8
X
X
3
2
5
3
2
1
6
1
4
5
1
6
4
6
1
2
5
6
3
5
X
X
X
7
X
X
2
1
6
5
2
6
5
5
3
3
4
2
3
5
4
X
6
5
4
X
X
X
X
6
X
X
6
2
4
6
5
3
6
5
4
5
1
6
1
4
X
X
X
X
X
X
X
X
X
5
X
X
3
3
5
1
6
5
3
2
6
1
3
5
5
X
X
X
X
X
X
X
X
X
X
4
X
X
5
2
1
2
3
4
6
1
5
X
X
5
X
X
X
X
X
X
X
X
X
X
X
3
X
X
X
4
6
3
2
6
4
5
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
2
X
X
X
X
X
X
X
4
6
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
1
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
0
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
.
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

In ieder geval is je verticale nummering verkeerd om.
In het veld dat je nu geeft is trouwens nog minstens 1 zet mogelijk. (1 9 O)

quote:

EdwinG schreef op zondag 02 november 2008 @ 16:34:
[...]


In ieder geval is je verticale nummering verkeerd om.
In het veld dat je nu geeft is trouwens nog minstens 1 zet mogelijk. (1 9 O)

De horizontale as is toch de x-as? Dan bedoel je denk ik (9 1 O).

domme vraag misschien, maar waarvoor staat rml eigenlijkt

offtopic:
Wellicht React Markup Language?

Hmmz, deze contest ziet er interessant uit, denk dat ik ook eens ga mee doen. Eerst nog wel eens door de regeltjes lezen aangezien ik in de eerste berichten al verwarring heb gezien, verder uiteraard eerst wat plannen voordat ik er code tegen ga smijten.

Ben van plan in C++ te werken en achteraf wat optimalisaties toe te brengen met een profiler (en eventueel ASM waar nodig, alhoewel ik op dit vlak nog weinig af weet), denk dat ik zowat alle tools ga maken die hier bij komen kijken. Dit zijnde het programma zelf, een validator/debugger, een random test set generator en een grafische weergave (uiteraard het minst belangrijke). De eerste twee lijken voor mij persoonlijk een vereiste, de twee andere lijken me een leuke extra voor de fun.

Hier komt veel bij kijken, het zal waarschijnlijk ook wel even duren voor er een toonbaar resultaat komt...

quote:

TomWij schreef op zondag 02 november 2008 @ 19:10:
Ben van plan in C++ te werken en achteraf wat optimalisaties toe te brengen met een profiler (en eventueel ASM waar nodig, alhoewel ik op dit vlak nog weinig af weet)

Waarom heb je de illusie dat je eventueel de compiler eruit programmeert met je naar eigen zeggen zeer beperkte asm kennis?

---

Mijn algoritme is trouwens aan de slag gegaan met de testset van Bolukan in "Programming Contest Nieuwe Stijl: Contest 4", en dit was de uitkomst na ~40 minuten (met een whopping 4.9 moves/s): http://oisyn.nl/gc/bolukan.zip

.
0
1
2
3
4
5
6
7
8
9
0
2
8
2
8
5
2
5
3
6
3
1
1
3
5
4
6
7
1
1
2
5
2
4
3
6
1
2
5
8
2
2
8
3
1
5
4
4
7
6
2
7
8
6
4
7
5
8
5
1
2
4
7
3
8
5
4
6
1
4
5
7
3
1
6
4
6
2
7
2
6
3
5
8
2
6
5
7
3
4
2
3
8
7
4
1
5
2
8
5
8
4
1
1
5
8
3
3
1
9
2
1
5
6
3
2
1
2
8
2
10
2
1
7
1
6
4
7
4
6
7
11
5
3
5
3
2
8
2
4
5
8
12
x
6
1
2
3
5
5
8
1
4
13
x
4
7
5
x
x
1
7
x
4
14
x
8
4
x
x
x
2
1
x
3
15
x
7
x
x
x
x
7
x
x
x
16
x
x
x
x
x
x
x
x
x
x
Score....................: 2361000 points
Total moves..............: 11470
Succesful moves..........: 11470
Bad moves................: 0
Average score per move...: 205 points
Move with highest score..: #6761 (1500 points)

Best een lastige set

.edit: de oplettende kijker was het waarschijnlijk al opgevallen dat er nog wel moves zijn, en dit klopt. M'n AI kijkt naar de toekomst en elke nu mogelijke zet zal in een aantal zetten leiden tot een vastloper, en dus stopt ie ermee. Ik moet natuurlijk nog wel even inbouwen dat ie op dat moment nog wel de laatste zetten gaat doen

Vanavond eerste resultaten van mijn eigen uitwerking op het beeldscherm gekregen, gebruikmakend van de standaard test-set. Wat ie doet is initialiseren, blokjes laten vallen, lijnen vinden, lijnen punten geven en vervolgens schrappen. Volgende stap is maar één keer 250 punten geven aan lijnen die samen een figuur vormen.

Voor de snelheid heb ik gekozen om het in VB Express van Visual Studio 2008 uit te voeren (ipv PHP of VBA), want C beheers ik onvoldoende om snel resultaat te zien. Snelheid van VB is prima: <0,1 seconde voor de eerste stap, zonder debug-output < 0,04 seconde.

Ik ben nog geen steek verder omdat ik verder nog geen tijd heb gehad om hiermee aan de slag te gaan

Ik heb echter wel eerder een dergelijke contest gedaan (en gewonnen), en heb misschien nog wel wat tips voor een AI:

- beperk je vooruit-berekeningen op basis van veld-grootte: bij grote velden is de kans dat je vastloopt klein, maar kost het vooruit-berekenen relatief veel meer tijd. Kies bij grote velden eerder voor een 'educated guess'.
- als er weinig mogelijke moves zijn en je niet vooruit wilt/kan berekenen kies dan voor een move zo laag mogelijk in het veld zodat het vallen van de stenen meer nieuwe moves kan opleveren.
- kies voor de 'underdog' - oftewel: als er weinig stenen van een bepaalde soort voorkomen, maar je kan er een combinatie meer maken, doe dat dan in plaats van een combinatie maken met stenen die overvloedig zijn in het veld.
- als je vooruit rekent probeer dan paden die een 'slechtere positie' dan de huidige opleveren zo snel mogelijk af te kappen.

Ik loop qua snelheid vooral tegen problemen aan met (de-)allocatie van geheugen.

kan iemand mij uitleggen waarom dit het verschil is tussen 20 en 35 sec. uitvoer tijd...

20s:
code:

Data bron;
Data bla;
while( ... ) {
    bla = bron;
    bla.calculate();
}

35s:
code:

Data bron;
while( ... ) {
    Data bla(bron);
    bla.calculate();
}

Is GCC nou gewoon retarded qua optimalisatie, of snap ik gewoon niet wat hier gebeurd
Ik heb geen custom assignment of copy operator.

In het eerste voorbeeld wordt er steeds een memcpy gedaan naar een bestaand object en in het tweede wordt steeds een object aangemaakt op basis van bron. Er zou dus geen verschil moeten zijn in de hoeveelheid data die gekopieerd wordt...

Gaaf wedstrijdje. Heb helaas geen tijd om mee te devven, maar vroeg me wel af of iemand hier al trouwens heeft overwogen om hun AI te parelleliseren om gebruik te maken van meerdere cores? Na de spelregels snel bekeken te hebben lijkt het me dat je het speelveld namelijk kan opdelen in meerdere rechthoeken die stenen bevatten welke je vervolgens parallel kan onderzoeken. De randen waarmee de rechthoeken zich met elkaar grenzen zijn hierbij dan de special cases waarbij nog even gecontroleerd moet worden of moves binnen een subrechthoek hebben geleid tot een "reductie" met respect tot de aangrenzende rechthoeken. Bij een speelveld die "groot genoeg is" kun je het meeste werk mbt het onderzoeken van deze subrechthoeken geheel parallel doen omdat ze niet afhankelijk van elkaar zijn op de randen na.

Weet niet of de concurrency overhead hier "het waard zal zijn" of juist in de weg zal liggen (kunnen we misschien pas echt zeggen bij een grote input set), maar je algo schaalt iig wel dan ongeveer volgens ahmdal's law vermoed ik

quote:

Arjan schreef op maandag 03 november 2008 @ 00:45:
Ik loop qua snelheid vooral tegen problemen aan met (de-)allocatie van geheugen.

kan iemand mij uitleggen waarom dit het verschil is tussen 20 en 35 sec. uitvoer tijd...

20s:
code:

Data bron;
Data bla;
while( ... ) {
    bla = bron;
    bla.calculate();
}

35s:
code:

Data bron;
while( ... ) {
    Data bla(bron);
    bla.calculate();
}

Is GCC nou gewoon retarded qua optimalisatie, of snap ik gewoon niet wat hier gebeurd
Ik heb geen custom assignment of copy operator.

Geen zinnig woord over te zeggen zonder de definitie van Data te kennen. Als daar bijv. een std::vector in staat dan is het gedrag vrij logisch, die wordt in het tweede geval steeds opnieuw aangemaakt dus moet ie z'n mem steeds opnieuw alloceren.

quote:

prototype schreef op maandag 03 november 2008 @ 00:46:
Gaaf wedstrijdje. Heb helaas geen tijd om mee te devven, maar vroeg me wel af of iemand hier al trouwens heeft overwogen om hun AI te parelleliseren om gebruik te maken van meerdere cores?

Uiteraard, maar niet op de manier hoe jij het voorstelt. Dat lijkt me te fine-grained wat lastiger te implementeren is en meer synchronisatie vereist, zonder dat daar een duidelijk voordeel tegenover staat. Ik zou persoonlijk de verschillende threads simpelweg verschillende takken in de zoekboom laten exploreren (om een indicatie te geven, de testset uit het voorbeeld begint al met 63 mogelijke zetten, dus genoeg te doen).

.oisyn wijzigde dit bericht 03-11-2008 01:14 (29%)

quote:

crisp schreef op maandag 03 november 2008 @ 00:00:
- beperk je vooruit-berekeningen op basis van veld-grootte: bij grote velden is de kans dat je vastloopt klein, maar kost het vooruit-berekenen relatief veel meer tijd. Kies bij grote velden eerder voor een 'educated guess'.

Veldgrootte is maar 1 van de parameters die bepaalt hoeveel berekeningen je kan doen. De andere twee zijn aantal beschikbare moves (belangrijker dan veldgrootte eigenlijk, een groot veld met steeds ~3 beschikbare moves is een stuk sneller door te rekenen dan een klein veld met steeds ~20 beschikbare moves - vooruitdenken is namelijk exponentieel in het aantal beschikbare moves, niet het aantal blokjes dat een veld opmaakt), en natuurlijk simpelweg de hardware waar je algoritme op draait.

Ik zou veldgrootte dan ook laten voor wat het is en het aantal berekeningen dat je per move spendeert puur beperken op basis van hoe lang je erover doet om een move af te ronden. Je hebt namelijk een gelimiteerde hoeveelheid moves die je mag doen (100.000) en een gelimiteerde tijd om dat te doen (15 minuten). Streef dus naar een gemiddelde snelheid van ~111 moves per seconde (en zorg natuurlijk dat je een buffertje hebt voor mindere tijden). Door dat te doen pas je je automatisch aan aan zowel de veldgrootte als de uiteindelijke hardware waar je algoritme op draait.

.oisyn wijzigde dit bericht 03-11-2008 01:41 (31%)

De officiële validator is klaar
Het is nog een insanely traag geval (~30 sec. voor een compleet spel ), maar hij voldoet nu wel. Nu nog een keer optimizen als ik zin/tijd heb. Wel best effectief in 450 LOC

RobIII wijzigde dit bericht 03-11-2008 01:49 (19%)

Zo, de AI die de eerste de beste match pakt is klaar. Next step: moves zoeken die een match opleveren.

Hieronder is het eindresultaat zonder dat enige move wordt uitgevoerd:

Bejeweled started at Sun Nov 02 20:25:40 BOT 2008
             111111111122222
   0123456789012345678901234
  ---------------------------
 0|4615122433523321443162541|
 1|1553236642423536625246656|
 2|#66414346133214545456554#|
 3|#141431646364654146464###|
 4|#442612361554166221646###|
 5|##55445156316613612525###|
 6|##565225662355163#662####|
 7|##66335665623445#########|
 8|##1511645643454##########|
 9|##132455655##4###########|
10|###1223654###############|
11|#######16################|
12|#########################|
13|#########################|
  ---------------------------

Score:    1900
Matches:  24
Moves:    0
Duration: 20ms
Bejeweled finished at Sun Nov 02 20:25:40 BOT 2008

	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24
0	4	6	1	5	1	2	2	4	3	3	5	2	3	3	2	1	4	4	3	1	6	2	5	4	1
1	1	5	5	3	2	3	6	6	4	2	4	2	3	5	3	6	6	2	5	2	4	6	6	5	6
2	#	6	6	4	1	4	3	4	6	1	3	3	2	1	4	5	4	5	4	5	6	5	5	4	#
3	#	1	4	1	4	3	1	6	4	6	3	6	4	6	5	4	1	4	6	4	6	4	#	#	#
4	#	4	4	2	6	1	2	3	6	1	5	5	4	1	6	6	2	2	1	6	4	6	#	#	#
5	#	#	5	5	4	4	5	1	5	6	3	1	6	6	1	3	6	1	2	5	2	5	#	#	#
6	#	#	5	6	5	2	2	5	6	6	2	3	5	5	1	6	3	#	6	6	2	#	#	#	#
7	#	#	6	6	3	3	5	6	6	5	6	2	3	4	4	5	#	#	#	#	#	#	#	#	#
8	#	#	1	5	1	1	6	4	5	6	4	3	4	5	4	#	#	#	#	#	#	#	#	#	#
9	#	#	1	3	2	4	5	5	6	5	5	#	#	4	#	#	#	#	#	#	#	#	#	#	#
10	#	#	#	1	2	2	3	6	5	4	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#
11	#	#	#	#	#	#	#	1	6	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#
12	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#
13	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#

Ben alleen nog niet helemaal tevreden over hoe ik de speelveld in OO heb neergezet. Dit kan hier en daar beter.

BalusC wijzigde dit bericht 03-11-2008 01:26 (0%)
Reden: Oeps, verkeerde resultaat gepost; had kolommen.txt aangepast voor test .. Is nu wel goed :)

Je score klopt niet, je mist 50 punten.
.edit: je speelveld klopt ook niet, dit zou het moeten zijn:

.
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
0
4
6
1
5
2
4
5
6
6
3
6
4
3
3
2
6
1
1
3
1
6
2
5
4
1
1
1
5
5
3
1
5
6
5
4
2
5
2
3
5
3
5
6
2
5
2
4
6
6
5
6
2
x
6
6
4
4
1
5
1
6
1
4
2
2
1
4
1
4
5
4
5
6
5
5
4
x
3
x
1
4
1
6
2
2
3
3
6
3
6
4
6
5
4
1
4
6
4
6
4
x
x
x
4
x
4
4
2
6
6
3
2
1
1
5
5
4
1
6
6
2
2
1
6
4
6
x
x
x
5
x
x
5
5
4
4
1
1
2
6
3
1
6
6
1
3
6
1
2
5
2
5
x
x
x
6
x
x
5
6
5
2
2
5
6
6
2
3
5
5
1
6
3
x
6
6
2
x
x
x
x
7
x
x
6
6
3
3
5
6
6
5
6
2
3
4
4
5
x
x
x
x
x
x
x
x
x
8
x
x
1
5
1
1
6
4
5
6
4
3
4
5
4
x
x
x
x
x
x
x
x
x
x
9
x
x
1
3
2
4
5
5
6
5
5
x
x
4
x
x
x
x
x
x
x
x
x
x
x
10
x
x
x
1
2
2
3
6
5
4
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
11
x
x
x
x
x
x
x
1
6
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
12
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
13
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
Score....................: 1950 points
Total moves..............: 0
Succesful moves..........: 0
Bad moves................: 0
Average score per move...: 0 points
Move with highest score..: #0 (0 points)

.oisyn wijzigde dit bericht 03-11-2008 01:33 (99%)

Dit waren de matches:

[5(1,0),5(2,0),5(0,0),5(3,0)]
[6(22,0),6(23,0),6(24,0)]
[6(5,2),6(4,2),6(6,2)]
[2(5,2),2(7,2),2(6,2),2(8,2)]
[3(6,0),3(6,1),3(6,2)]
[5(5,3),5(8,3),5(4,3),5(7,3),5(6,3)]
[4(9,3),4(10,3),4(11,3)]
[6(19,4),6(20,4),6(21,4)]
[5(7,5),5(9,5),5(8,5)]
[5(6,1),5(5,1),5(7,1)]
[4(13,5),4(14,5),4(15,5)]
[4(21,5),4(17,5),4(18,5),4(20,5),4(19,5)]
[1(15,0),1(17,0),1(16,0)]
[4(11,6),4(12,6),4(10,6),4(8,6),4(9,6)]
[3(12,2),3(12,0),3(12,1)]
[3(6,4),3(7,4),3(8,4)]
[1(7,5),1(6,5),1(8,5)]
[6(4,4),6(5,4),6(6,4)]
[5(6,1),5(8,1),5(7,1)]
[3(13,7),3(14,7),3(15,7)]
[2(11,8),2(12,8),2(13,8)]
[5(9,2),5(10,2),5(11,2)]
[5(15,4),5(13,4),5(14,4)]
[6(12,5),6(13,5),6(14,5)]

(sorry, coords zijn niet netjes in volgorde, ik gebruik hiervoor een HashSet ipv ArrayList/LinkedHashSet ofzo)

BalusC wijzigde dit bericht 03-11-2008 01:51 (11%)

Nu ik de output heb vergeleken, ik denk dat jouw AI eerst het hele veld scant voor horizontale matches en daarna opnieuw voor de verticale matches? Mijn AI scant bij elke jewel direct zowel de horizontale als verticale matches (zie bijv de 5e match met jewel id=3).

BalusC wijzigde dit bericht 03-11-2008 01:55 (14%)

quote:

RobIII schreef op maandag 03 november 2008 @ 01:21:
Het is nog een insanely traag geval (~30 sec. voor een compleet spel )

Hoppa; 1 optimization en terug van ~30 sec. naar ~5 sec. Ik vind 't wel welletjes (en dat terwijl er nog zat te halen valt)

RobIII wijzigde dit bericht 03-11-2008 01:56 (7%)

Je maakt de fout dat je na elke verwijdering blokjes laat vallen volgens mij. Zo zie ik [2(5,2),2(7,2),2(6,2),2(8,2)] na [6(5,2),6(4,2),6(6,2)], wat op zich klopt als je eerst die eerst weghaalt en dan wat blokjes laat vallen zodat de 4 cyaan-blokjes (nummer 2) op een lijn komen te liggen.

Dat doet de AI inderdaad. Ik wist niet dat alle mogelijke matches tegelijkertijd moeten worden verwijderd

Is dit behaviour wel geldig? Staat dit uberhaupt in de regels? * BalusC gaat maar nog even lezen.

edit:

Niet expliciet gevonden. Help, contestleiding, * BalusC wil bevestiging

BalusC wijzigde dit bericht 03-11-2008 02:03 (15%)

Volgens mij is het al een aantal keer aangehaald dat alle mogelijkheden eerst worden verwijderd voordat alles naar beneden valt.

AI is (tijdelijk?) aangepast zoals je het hebt gezegd:

Bejeweled started at Sun Nov 02 21:10:09 BOT 2008
             111111111122222
   0123456789012345678901234
  ---------------------------
 0|4615245663643326113162541|
 1|1553156542523535625246656|
 2|#66441516142214145456554#|
 3|#141622336364654146464###|
 4|#442663211554166221646###|
 5|##55441126316613612525###|
 6|##565225662355163#662####|
 7|##66335665623445#########|
 8|##1511645643454##########|
 9|##132455655##4###########|
10|###1223654###############|
11|#######16################|
12|#########################|
13|#########################|
  ---------------------------

Score:    2250
Matches:  2
Moves:    0
Duration: 14ms

	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24
0	4	6	1	5	2	4	5	6	6	3	6	4	3	3	2	6	1	1	3	1	6	2	5	4	1
1	1	5	5	3	1	5	6	5	4	2	5	2	3	5	3	5	6	2	5	2	4	6	6	5	6
2	#	6	6	4	4	1	5	1	6	1	4	2	2	1	4	1	4	5	4	5	6	5	5	4	#
3	#	1	4	1	6	2	2	3	3	6	3	6	4	6	5	4	1	4	6	4	6	4	#	#	#
4	#	4	4	2	6	6	3	2	1	1	5	5	4	1	6	6	2	2	1	6	4	6	#	#	#
5	#	#	5	5	4	4	1	1	2	6	3	1	6	6	1	3	6	1	2	5	2	5	#	#	#
6	#	#	5	6	5	2	2	5	6	6	2	3	5	5	1	6	3	#	6	6	2	#	#	#	#
7	#	#	6	6	3	3	5	6	6	5	6	2	3	4	4	5	#	#	#	#	#	#	#	#	#
8	#	#	1	5	1	1	6	4	5	6	4	3	4	5	4	#	#	#	#	#	#	#	#	#	#
9	#	#	1	3	2	4	5	5	6	5	5	#	#	4	#	#	#	#	#	#	#	#	#	#	#
10	#	#	#	1	2	2	3	6	5	4	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#
11	#	#	#	#	#	#	#	1	6	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#
12	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#
13	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#	#

Edit: aantal matches klopt natuurlijk niet Eindstand ziet identiek uit. Score is echter 300pt hoger..
Dit waren de 2 "matches":

             111111111122222
   0123456789012345678901234
  ---------------------------
 0|5555413136563664125565666|
 1|1553622311353516654464656|
 2|#66466622651665544664654#|
 3|#141555554446563121525###|
 4|#442663166335416212666###|
 5|##55441555223444644444###|
 6|##565225444445453#662####|
 7|##66335665634333#########|
 8|##1511645642224##########|
 9|##132455655##4###########|
10|###1223654###############|
11|#######16################|
12|#########################|
13|#########################|
  ---------------------------

[4(10,6),5(1,0),6(5,2),4(20,5),5(8,3),5(8,5),6(24,0),5(7,5),4(15,5),5(2,0),4(21,5),6(6,2),5(4,3),4(11,3),5(7,3),4(9,6),4(12,6),6(20,4),2(13,8),4(8,6),4(18,5),4(14,5),6(23,0),3(14,7),5(5,3),6(19,4),2(12,8),4(10,3),4(17,5),5(3,0),3(15,7),4(11,6),6(4,2),6(21,4),3(13,7),4(13,5),6(22,0),5(0,0),5(6,3),4(19,5),2(11,8),4(9,3),5(9,5)]

             111111111122222
   0123456789012345678901234
  ---------------------------
 0|4615253542424145113162541|
 1|1553133361333651625246656|
 2|#66441315555316445456554#|
 3|#141622336363616146464###|
 4|#442663211556555221646###|
 5|##55441126316663612525###|
 6|##565225662355163#662####|
 7|##66335665623445#########|
 8|##1511645643454##########|
 9|##132455655##4###########|
10|###1223654###############|
11|#######16################|
12|#########################|
13|#########################|
  ---------------------------

[3(7,1),5(14,4),6(12,5),6(14,5),5(15,4),3(12,3),3(12,2),3(5,1),3(12,1),5(10,2),3(6,0),3(6,1),3(10,1),5(13,4),5(8,2),6(13,5),3(6,2),5(11,2),5(9,2),3(11,1)]

             111111111122222
   0123456789012345678901234
  ---------------------------
 0|4615245663643326113162541|
 1|1553156542523535625246656|
 2|#66441516142214145456554#|
 3|#141622336364654146464###|
 4|#442663211554166221646###|
 5|##55441126316613612525###|
 6|##565225662355163#662####|
 7|##66335665623445#########|
 8|##1511645643454##########|
 9|##132455655##4###########|
10|###1223654###############|
11|#######16################|
12|#########################|
13|#########################|
  ---------------------------

Maar eens even de score debuggen

BalusC wijzigde dit bericht 03-11-2008 02:17 (13%)

Idd. Hoe weet je anders welke volgorde je moet hanteren?

Dit zijn de afzonderlijke stappen:

.	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24
0	x5	x5	x5	x5	4	1	3	1	3	6	5	6	3	6	6	4	1	2	5	5	6	5	x6	x6	x6
1	1	5	5	3	6	2	2	3	1	1	3	5	3	5	1	6	6	5	4	4	6	4	6	5	6
2	x	6	6	4	x6	x6	x6	2	2	6	5	1	6	6	5	5	4	4	6	6	4	6	5	4	x
3	x	1	4	1	x5	x5	x5	x5	x5	x4	x4	x4	6	5	6	3	1	2	1	5	2	5	x	x	x
4	x	4	4	2	6	6	3	1	6	6	3	3	5	4	1	6	2	1	2	x6	x6	x6	x	x	x
5	x	x	5	5	4	4	1	x5	x5	x5	2	2	3	x4	x4	x4	6	x4	x4	x4	x4	x4	x	x	x
6	x	x	5	6	5	2	2	5	x4	x4	x4	x4	x4	5	4	5	3	x	6	6	2	x	x	x	x
7	x	x	6	6	3	3	5	6	6	5	6	3	4	x3	x3	x3	x	x	x	x	x	x	x	x	x
8	x	x	1	5	1	1	6	4	5	6	4	x2	x2	x2	4	x	x	x	x	x	x	x	x	x	x
9	x	x	1	3	2	4	5	5	6	5	5	x	x	4	x	x	x	x	x	x	x	x	x	x	x
10	x	x	x	1	2	2	3	6	5	4	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x
11	x	x	x	x	x	x	x	1	6	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x
12	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x
13	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x

.	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24
0	4	6	1	5	2	5	x3	5	4	2	4	2	4	1	4	5	1	1	3	1	6	2	5	4	1
1	1	5	5	3	1	x3	x3	x3	6	1	x3	x3	x3	6	5	1	6	2	5	2	4	6	6	5	6
2	x	6	6	4	4	1	x3	1	x5	x5	x5	x5	x3	1	6	4	4	5	4	5	6	5	5	4	x
3	x	1	4	1	6	2	2	3	3	6	3	6	x3	6	1	6	1	4	6	4	6	4	x	x	x
4	x	4	4	2	6	6	3	2	1	1	5	5	6	x5	x5	x5	2	2	1	6	4	6	x	x	x
5	x	x	5	5	4	4	1	1	2	6	3	1	x6	x6	x6	3	6	1	2	5	2	5	x	x	x
6	x	x	5	6	5	2	2	5	6	6	2	3	5	5	1	6	3	x	6	6	2	x	x	x	x
7	x	x	6	6	3	3	5	6	6	5	6	2	3	4	4	5	x	x	x	x	x	x	x	x	x
8	x	x	1	5	1	1	6	4	5	6	4	3	4	5	4	x	x	x	x	x	x	x	x	x	x
9	x	x	1	3	2	4	5	5	6	5	5	x	x	4	x	x	x	x	x	x	x	x	x	x	x
10	x	x	x	1	2	2	3	6	5	4	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x
11	x	x	x	x	x	x	x	1	6	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x
12	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x
13	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x	x

Ik heb trouwens even een nieuwe validator online gezet die wat lichtere rml uitspuugt (niet elke cell width en height properties ): http://oisyn.nl/gc/validator.exe

.oisyn wijzigde dit bericht 03-11-2008 02:21 (195%)

Thanks

Bug in score is ook opgelost overigens. Het is idd 1950.

quote:

.oisyn schreef op maandag 03 november 2008 @ 02:12:
Ik heb trouwens even een nieuwe validator online gezet die wat lichtere rml uitspuugt (niet elke cell width en height properties ): http://oisyn.nl/gc/validator.exe

En waarom gaat 'ie dan van 85,6Kb naar 198Kb?

Hmz, blijkbaar werken post-build steps niet in visual studio als je op de "optimize" knop drukt bij profile guided optimizations. In m'n post-build step gooi ik UPX er namelijk overheen . F5 voor de kleinere versie.

Ik ben bang dat het me toch net even te ingewikkeld wordt. Op de beginscore (1250) kwam ik wel, het lijkt er op dat het inbrengen van de volgende steentjes ook nog wel lukt, maar dan... Wanneer ik in mijn kijk-of-er-met-dit-veld-zetten-mogelijk-zijn-functie die functie recursief maak (maar wel met de controle of er de vorige keer nog steentjes zijn verwijderd om de infinite loop te voorkomen), kom ik toch op een infinite loop uit.

Weet er iemand of in de beginsituatie (dus voor het doen van een zet), ook moeilijkere figuren voorkomen, zoals:
code:

0xxx0
0x000
0xxx0

?

De functie die controleert of er steentjes hetzelfde zijn gaat nu namelijk alleen nog maar uit van één punt in zowel beide x- als y-richtingen, maar niet of er ook nog weer een rij verdergaat (zoals in het voorbeeld: de bovenste xxx en de vertikale xxx herkent hij, de onderste nog niet). Als dat in de beginsituatie voorkomt zou het kunnen dat daar mijn fout zit.

quote:

ScottB schreef op maandag 03 november 2008 @ 04:54:
Wanneer ik in mijn kijk-of-er-met-dit-veld-zetten-mogelijk-zijn-functie die functie recursief maak (maar wel met de controle of er de vorige keer nog steentjes zijn verwijderd om de infinite loop te voorkomen), kom ik toch op een infinite loop uit.

Het hoeft natuurlijk helemaal niet recursief. In pseudocode heb ik het gewoon zo
pseudo:

DoMove();

do
{
    DropBlocks();
} while( RemoveShapes() );

quote:

ScottB schreef op maandag 03 november 2008 @ 04:54:
Weet er iemand of in de beginsituatie (dus voor het doen van een zet), ook moeilijkere figuren voorkomen, zoals:

.oisyn heeft hierboven de juiste zetten gezet die gedaan moeten worden voordat je de eerste zet kunt doen.

Woy wijzigde dit bericht 03-11-2008 09:09 (24%)

quote:

crisp schreef op maandag 03 november 2008 @ 00:00:
- als er weinig mogelijke moves zijn en je niet vooruit wilt/kan berekenen kies dan voor een move zo laag mogelijk in het veld zodat het vallen van de stenen meer nieuwe moves kan opleveren.

Vooral bij veel verschillende stenen wil je vaak juist zo hoog mogelijk in het veld iets doen. Als er hoog iets kan, en er daaronder iets verandert, dan kan de move hoog vaak niet meer. Andersom, als er hoog iets verandert, dan blijft de lage move ook nog mogelijk. Veel zo hoog mogelijke moves doen is een goede tactiek om redelijk ver te komen in het originele spel (link van Megamind is stiekem toch v1, maar met minder reclames). Sterker nog, het lijkt wel alsof dat spel nooit eindigt...