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

quote:

NMe schreef op vrijdag 19 december 2008 @ 15:57:
Windows XP of Vista.

Dat is wel jammer aangezien de performance van GCC met OpenMP en pthreads onder Windows toch signficant lager is dan onder Linux, en er voor zover ik weet geen andere gratis compilers voor Windows zijn die OpenMP ondersteunen. (Microsoft's compiler ondersteunt het wel op zich wel, maar de gratis editie juist weer niet.)

Soultaker wijzigde dit bericht 19-12-2008 16:57 (32%)

Hier m'n eerste officiele score met de nieuwe aanpak. Zelfde solver als voorheen, maar even wat parameters getweakt om binnen de tijd te blijven.
code:

Move   : 100000
Score  : 51016050
Score/m: 510.16
Time   : 884.77
Moves/s: 113.02

Mooie score.
Wat voor systeem test je op?

quote:

Soultaker schreef op vrijdag 19 december 2008 @ 16:56:
[...]
Dat is wel jammer aangezien de performance van GCC met OpenMP en pthreads onder Windows toch signficant lager is dan onder Linux, en er voor zover ik weet geen andere gratis compilers voor Windows zijn die OpenMP ondersteunen. (Microsoft's compiler ondersteunt het wel op zich wel, maar de gratis editie juist weer niet.)

Er schijnt wel een mannier te zijn om OpenMP in de gratis versie van Visual Studio te krijgen: OpenMP and Visual C++ the free way (sorta)

Of je kunt GCC voor windows gebruiken via Cygwin. Dat dit niet altijd langzamer hoeft te zijn dan GCC onder linux zie je hier.

quote:

Soultaker schreef op vrijdag 19 december 2008 @ 18:16:
Mooie score.
Wat voor systeem test je op?

Core 2 Duo E6750 @ 3 GHz, Win XP x64 (solver is 32 bits trouwens, in m'n eerdere tests was een 64 bits implementatie zowaar langzamer),

Misschien een beetje off-topic:ik ben bezig met een (alpha) implementatie van Bejeweled op een groot multitouch-scherm. Geen bots, wel multiplayer

Ziet er goed uit writser! Binnekort filmpje?

offtopic:
Hoe zit het eigenlijk juridisch, als je een kloon van Bejeweled zou maken ( Natuurlijk zonder de icon's e.d. en een andere naam ). Mag dat gewoon, of zit daar ook nog iets van rechten op?

Jewel Quest mocht het ook

.oisyn wijzigde dit bericht 23-12-2008 12:15 (3%)

Is Jewel Quest niet van dezelfde maker?
http://www.nl.zylom.com/game/300/jewel-quest.html
http://www.nl.zylom.com/game/335/bejeweled-2.html

Ieder geval beide bij Zylom te krijgen. Ik kan me namenlijk herinneren dat er omtrent Tetris destijds wel wat rechten kwesties speelden, maar ik weet er het fijne niet van.

Nope. Bejeweled is van PopCap, Jewel Quest van iWin

quote:

NMe schreef op vrijdag 07 november 2008 @ 16:15:
[...]

^^ wat hij zegt.

[...]

Nee hoor. We zouden best zo sneaky kunnen zijn om het veld in tweeën te splitsen zonder een muur te gebruiken door gewoon een kolom géén invulling te geven. Ik zeg niet dát het gebeurt, maar het zou zomaar kunnen. Neem dus niet zomaar wat aan.

Net even getest en .oisyn's validator (build 6) kan hier nog niet mee omgaan.

Ik zal ook eens tonen waar mijn AI toe in staat is :

.
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
5
5
3
3
1
4
6
2
6
5
3
1
5
3
4
4
3
1
4
5
4
2
6
5
2
1
3
6
1
4
2
4
5
1
5
6
3
5
4
4
3
5
5
4
5
2
4
5
2
6
1
2
x
1
5
2
4
2
3
4
6
3
4
1
4
5
4
5
3
2
4
6
2
6
1
4
x
3
x
4
4
5
6
3
1
5
1
2
4
3
3
5
3
6
4
1
5
6
1
4
x
x
x
4
x
5
1
5
4
1
2
1
4
1
3
5
3
1
5
1
2
4
2
5
4
1
x
x
x
5
x
x
6
4
3
1
3
5
3
6
6
3
2
5
3
5
2
6
4
6
2
6
x
x
x
6
x
x
4
1
2
3
6
4
3
4
2
3
1
3
2
6
5
x
1
4
4
x
x
x
x
7
x
x
3
2
4
4
5
1
6
3
4
6
5
1
4
4
x
x
x
x
x
x
x
x
x
8
x
x
1
3
5
4
2
2
1
5
6
2
5
5
2
x
x
x
x
x
x
x
x
x
x
9
x
x
6
1
5
2
5
3
4
1
1
x
x
2
x
x
x
x
x
x
x
x
x
x
x
10
x
x
x
2
4
4
2
6
2
4
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
11
x
x
x
x
x
x
x
4
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....................: 34526600 points
Total moves..............: 100000
Succesful moves..........: 100000
Bad moves................: 0
Average score per move...: 345 points
Move with highest score..: #96395 (2400 points)

Dit is de hoogste score die ik binnen 15 min kan halen op de orginele testset @ 63k effectieve moves/sec.

Of het kan gewoon niet snel met c# of ik doe iets helemaal verkeerd

Mwa, als ik daar aankom met mn slechts 700 moves/seconde... Met behoorlijk oude code trouwens, mn nieuwe spul krijg ik met geen mogelijkheid aan het werk. Eerst had ik overflows en nu acces violations Dus ik kan nog eens lekker aan de slag gaan

Ook nog even testset 2:

.
0
1
2
3
4
5
6
7
8
9
0
8
7
6
5
8
5
8
3
6
2
1
1
8
2
3
1
7
6
4
2
1
2
7
4
5
8
8
5
5
1
3
2
3
4
5
2
6
5
6
4
7
5
4
4
2
8
6
8
1
1
8
3
2
6
5
5
8
6
3
6
3
6
5
6
7
6
5
7
2
3
6
2
8
2
1
4
7
6
7
6
8
1
1
7
6
4
4
8
6
3
8
2
5
8
1
8
7
6
9
4
5
6
6
4
2
5
5
6
4
10
2
8
3
3
8
6
1
2
2
5
11
5
4
5
4
5
7
8
7
3
6
12
x
1
6
6
7
1
5
6
8
4
13
x
6
8
7
x
x
4
3
x
1
14
x
7
1
x
x
x
7
3
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....................: 11246900 points
Total moves..............: 100000
Succesful moves..........: 100000
Bad moves................: 0
Average score per move...: 112 points
Move with highest score..: #2039 (1150 points)

Bij deze run blijkt maar weer dat mijn autotuning nog wat werk nodig heeft -> 15:00.95 maar eerst even mijn nieuw AI idee uitproberen. Er is nog tijd genoeg voor autotuning...

edit: bij deze set is mijn algoritme weer wat sneller zo'n 100k effectieve moves/s, blijkbaar scheelt veldgrootte nog erg veel.

quote:

king_charles schreef op dinsdag 23 december 2008 @ 23:57:
Er is nog tijd genoeg voor autotuning...

Famous last words

quote:

RobIII schreef op dinsdag 23 december 2008 @ 23:58:
[...]

Famous last words

I hope not

Uit de openingspost:

quote:

De sluitingsdatum van de contest is maandag 10 januari 2009.

10 januari valt in mijn kalender op een zaterdag, niet op een maandag .

Dus we hebben tot 2011?

Dus als we straks weinig entries hebben of omdat iemand straks enorm slecht scoort met zijn of haar entry dan krijgen we te horen "Ja maar ik dacht dat we tot 2011 hadden!"

Ik meende dat de deadline uitgesteld was tot februari? Of ben ik nou in de war?

Nee hij was uitgesteld van (ik meen) 3 of 4 januari tot 10 januari

quote:

rwb schreef op dinsdag 23 december 2008 @ 12:43:
Ik kan me namenlijk herinneren dat er omtrent Tetris destijds wel wat rechten kwesties speelden, maar ik weet er het fijne niet van.

Geen idee hoe het met gameplay rechten zit, maar Zoo Keeper was volgens mij de eerste met dit concept

quote:

glashio schreef op woensdag 24 december 2008 @ 12:13:
[...]
Geen idee hoe het met gameplay rechten zit, maar Zoo Keeper was volgens mij de eerste met dit concept

Wat ik me kan herinneren is dat ze alleen de naam niet mochten gebruiken, of namen die er op lijken (eindigend op tris).

quote:

glashio schreef op woensdag 24 december 2008 @ 12:13:
[...]
Geen idee hoe het met gameplay rechten zit, maar Zoo Keeper was volgens mij de eerste met dit concept

als ik wiki moet geloven was bejeweled toch echt eerder Bejeweled

Maar het zal inderdaad wel alleen de naam zijn waar rechten op zitten, anders hadden al die andere clonen ook wel problemen gekregen lijkt me.

Hmm, een nieuwe contest.
Hij klinkt wel leuk, maar het is nu wel erg kort dag.

Eens kijken of ik nog ergens wat tijd kan vrij maken.

Een contest meedoen is zowieso al leuk

Hm, ik moet mijn code nog steeds opschonen sinds de 'grote' aanpassing van het initiele opzet Maar eens tijd en zin voor vrijmaken Al motiveert het niet veel meer nu ik scores van ~50M op de testset voorbij zie komen.. Mijn domme AI doet nog steeds de eerste de beste move met de beste score.

quote:

BalusC schreef op donderdag 25 december 2008 @ 20:55:
Hm, ik moet mijn code nog steeds opschonen sinds de 'grote' aanpassing van het initiele opzet Maar eens tijd en zin voor vrijmaken Al motiveert het niet veel meer nu ik scores van ~50M op de testset voorbij zie komen.. Mijn domme AI doet nog steeds de eerste de beste move met de beste score.

Die van mij ook En met 100 moves/s zal ik hem waarschijnlijk uit schaamte maar niet inzenden

quote:

Megamind schreef op donderdag 25 december 2008 @ 20:58:
[...]

Die van mij ook En met 100 moves/s zal ik hem waarschijnlijk uit schaamte maar niet inzenden

Gewoon doen. Meedoen is belangrijker dan winnen .

Het ziet er voor mij ook interessant uit om eens te proberen . Is er eigenlijk een maximale lengte voor een regel in kolommen.txt? Dat kon ik in de startpost niet vinden.

quote:

compufreak88 schreef op donderdag 25 december 2008 @ 22:14:
[...]


Gewoon doen. Meedoen is belangrijker dan winnen .

Ik weet niet wie jou dat verteld heeft, maar dat is een leugen

.oisyn wijzigde dit bericht 26-12-2008 16:31 (4%)

Dus ik mag per direct opgeven?

Al zou ik toch ook wel wat beters neer willen zetten dan ik nu heb, maar dat moet mogelijk zijn, ik heb er al een paar weken niets meer aan gedaan...

Mijn Python implementatie (ontworpen volgens het antipattern 'Rush to code', a.k.a. 'Code first, think later') is zo'n grote puinhoop geworden dat ik maar opnieuw begonnen ben. Aangezien Scala op mijn verlanglijstje van te leren talen stond, ben ik daar in begonnen, maar ik wil natuurlijk wel alles uitproberen en er is nog niet zo gek veel documentatie beschikbaar, dus ik denk dat ik niet meer aan een inzending toe ga komen.

quote:

Confusion schreef op zondag 28 december 2008 @ 13:40:
Mijn Python implementatie (ontworpen volgens het antipattern 'Rush to code', a.k.a. 'Code first, think later') is zo'n grote puinhoop geworden dat ik maar opnieuw begonnen ben. Aangezien Scala op mijn verlanglijstje van te leren talen stond, ben ik daar in begonnen, maar ik wil natuurlijk wel alles uitproberen en er is nog niet zo gek veel documentatie beschikbaar, dus ik denk dat ik niet meer aan een inzending toe ga komen.

Ik had het juist andersom, ik had eerst een nette implementatie geschreven, en daarna had ik een paar optimalistatie ideen, en nu is het een grote bende ( en de performance niet echt beter )

Heb helaas nog niet echt tijd gehad om een goede implementatie voor mijn AI te schrijven, maar ben alleen nog maar met het framework bezig geweest.

Het lukt me nog steeds niet om binnen de tijd de 50x50 testset van BalusC te halen. Na het verbeteren van enkele kleinigheden kom ik nu tot zo'n 30.000 zetten in 15 min.

Het lijkt erop dat ik het over een andere boeg moet gooien wat betreft het afhandelen van dode paden.

quote:

DaCoTa schreef op zaterdag 29 november 2008 @ 23:56:
Dit is mijn score van de 3e testset (de grote 50x50), nadat ik met een geweldig simpele ingeving eindelijk binnen de tijd kon blijven:
code:

Score: 10302450
Time:  14:59.094

Heeft iemand anders van dit veld al een score?

Het is mij (eindelijk ) gelukt om binnen een redelijke tijd door de grote testset van BalusC te komen:
code:

Total moves: 100000
Moves/sec: 093,30
Total score: 7792300
Highest Scoring move: #84 (750)
Execution time: 00:17:51.8500000

Bleek veel dingen dubbel te doen, waarvan ik nu een deel gefixt heb. Zal er de komende tijd nog wat meer aan verbeteren en dan kan ik waarschijnlijk ook een betere tijd/score neerzetten.

Edit: Na nog eens 2 uur werk -> Iets lagere score, maar wel binnen de tijd:
code:

Total moves: 100000
Moves/sec: 111,17
Total score: 7646250
Highest Scoring move: #28360 (800)
Execution time: 00:14:59.4940000

king_charles wijzigde dit bericht 30-12-2008 16:42 (13%)

Gelukkig nieuwjaar iedereen.

Intussen ben ik ook begonnen met een eerst opzetje. Alleen ben ik bang dat de deadline wel erg kort dag wordt.
Er staat al een opzetje voor een algoritme op papier en voor de verandering ben ik met coden eens begonnen met het inlezen van de data. Dat lijkt redelijk te gaan, maar het gaat natuurlijk om het algoritme

Iedereen iig veel succes gewenst.

Mijn inzending is verstuurd, ga niet winnen maar word hopelijk geen laatste. Was weer even het opfrissen van de .net kennis (die ik overigens nog steeds niet heb).

Ik krijg overigens een error mail terug:
The following recipient(s) cannot be reached:

'[e-mail]' on 3-1-2009 14:27
552 5.7.0 to review our attachment guidelines. y37sm41822204iky.16

Eskimootje wijzigde dit bericht 03-01-2009 14:28 (40%)
Reden: errormessage

Waarschijnlijk probleem je een exe los mee te mailen? Gooi hem even in een zip-file, dat komt meestal wel door virusscanners heen

Ik moet eens even flink aanpoten om nog op tijd iets in te leveren. Veel te veel tijd besteed aan familie en vrienden die ik ook aan coden had kunnen besteden natuurlijk!

Ik ga nog steeds wel iets inleveren, maar ik heb het donkerbruine vermoeden dat ik niet veel verder dan een naïeve brute force implementatie ga komen. (Ik heb nu al wel een TotallyRandomStrategy, misschien dat ik die erin houd op lage prioriteit zodat ik iets heb om op terug te vallen als mijn brute force vastloopt).

Gerco wijzigde dit bericht 03-01-2009 15:26 (20%)

quote:

frickY schreef op zaterdag 03 januari 2009 @ 15:07:
Waarschijnlijk probleem je een exe los mee te mailen? Gooi hem even in een zip-file, dat komt meestal wel door virusscanners heen

Een zipfile of ander archief is sowieso de bedoeling. Alleen een executable gaan we niet in beoordeling nemen, we willen sourcecode zien.

Het was allemaal gezipped, maar ik denk dat het de gmail server was die geen .exe wil. Als het goed is het nu wel gelukt.

De mail word ook geforward naar een gmail adres. Daar kreeg ik nog een error op terug.

Eskimootje wijzigde dit bericht 03-01-2009 15:49 (27%)

Mijn versie begint nu ook langzaam wat te gaan doen.
De huidige versie is nog veels te traag en neemt gigantisch veel geheugen/HD ruimte in beslag.
Voorlopig is het voornamelijk brute-forcen.

Is het mogelijk de inlevertermijn met 2 weekenden te verlengen?
Helaas zag ik de contest pas met de feestdagen...

Nog een vraagje,
Een lege kolom in kolommen.txt is mogelijk.
Is het echter wel toegestaan om een jewel te wisselen met een positie in de lege kolom zoals b.v.
code:

1 889
2 227
3 567
XXXXX
XXXXX

In dit voorbeeld zou de 2 op positie (0,1) verplaatst kunnen worden naar Oost.
Mag dat?
Of moet je een lege kolom zien als een echte muur?

KoW wijzigde dit bericht 03-01-2009 22:48 (36%)

Er zijn al entries ingeleverd. Het zou voor die mensen niet eerlijk zijn als we de deadline zouden verschuiven. De contest loopt al vanaf eind oktober (!) wat voor een beetje GoT bezoeker tijd genoeg zou moeten zijn.

quote:

KoW schreef op zaterdag 03 januari 2009 @ 20:35:
Nog een vraagje,
Een lege kolom in kolommen.txt is mogelijk.

quote:

NMe in "Programming Contest Nieuwe Stijl: Contest 4"
In dit bestand staat per regel een opeenvolging van cijfers die

Een spatie hoort niet thuis in een opeenvolging van cijfers

Creepy wijzigde dit bericht 04-01-2009 10:17 (80%)

Volgens NMe is het mogelijk:
NMe in "Programming Contest Nieuwe Stijl: Contest 4"
Zie ook:
NMe in "Programming Contest Nieuwe Stijl: Contest 4"

Er staat nergens een hoeveelheid voor die "opeenvolging" gedefinieerd (en ik heb het ook nooit over een spatie gehad )

offtopic:
November en december zat ik in Czech, maar dat is verder geen excuus. Ik zal mijn best doen.

quote:

Megamind schreef op donderdag 25 december 2008 @ 20:58:
[...]

Die van mij ook En met 100 moves/s zal ik hem waarschijnlijk uit schaamte maar niet inzenden

Hm... Jij gebruikte toch Delphi dacht ik? Interessant in dat geval dan, want de mijn oude oplossing is ook niet bijster snel vergeleken met de rest. Wat mn nieuwe oplossing gaat doen is alleen nog even afwachten, die is nog heel ergs zwaar onder constructie. Ik ben er nu maar vanuit gegaan dat ik iets te zwaar objectgeorienteerd aan de slag was gegaan, dus eens zien wat er uit komt. Wat ik er nog meer aan veranders is het geheugengebruik, ik vond het namelijk nogal jammer om slechts 3MB te gebruiken. Als ik nu zonder zetten te doen bij het geheugengebruik kijk zit ik zo tussen de 17MB en de 380MB.

dcm360 wijzigde dit bericht 04-01-2009 20:18 (15%)

quote:

KoW schreef op zondag 04 januari 2009 @ 20:06:
Volgens NMe is het mogelijk:
NMe in "Programming Contest Nieuwe Stijl: Contest 4"
Zie ook:
NMe in "Programming Contest Nieuwe Stijl: Contest 4"

Er staat nergens een hoeveelheid voor die "opeenvolging" gedefinieerd (en ik heb het ook nooit over een spatie gehad )

offtopic:
November en december zat ik in Czech, maar dat is verder geen excuus. Ik zal mijn best doen.

De eerste posts van NMe gaat over het aantal gems per kolom. Dat mogen er inderdaad minder zijn dan dat de kolom lang is. Je begint na het einde bereikt te hebben van de beschikbare gems per kolom in kolommen.txt weer aan het begin van de regel. Indien er een lege regel staat dan valt het spel niet te spelen.

Als het veld in tweeen wordt gesplitst dan gebeurd dat met speelveld.txt.

Creepy wijzigde dit bericht 04-01-2009 21:20 (3%)

Met mijn tweede post doelde ik ook meer op het stukje robuustheid. De uiteindelijke set zal geen gekke dingen bevatten om je erin te luizen. Een tweede set om de robuustheid te testen misschien wel.

O, dus dan kan ik zo'n set gewoon afkeuren.
Ik had het opgevat als een legitieme mogelijkheid die ongeveer hetzelfde effect heeft als een muur.

Kortom, kolommen.txt bevat minimaal 1 gem per kolom, maximum is undefined

quote:

NMe schreef op vrijdag 07 november 2008 @ 16:15:
[...]

Nee hoor. We zouden best zo sneaky kunnen zijn om het veld in tweeën te splitsen zonder een muur te gebruiken door gewoon een kolom géén invulling te geven. Ik zeg niet dát het gebeurt, maar het zou zomaar kunnen. Neem dus niet zomaar wat aan.

Dus kolommen.txt is valide wanneer een kolom geen gems bevat

Valide: ja. Zal het voorkomen in de set waarin jullie scores tegen elkaar opgemeten worden? Nee.

Zo, net klaar met doorlezen van alle posts hier. Ik zat al sinds het einde van de vorige contest te smachten naar een nieuwe, maar ik kom verder niet zo vaak in de devschuur. Ik zie deze thread dus nu pas , ik ga kijken of ik nog iets in elkaar ga flansen. Ik ben in ieder geval blij dat de volgende contest voor februari/maart op de planning staat.

Bij deze wil ik vragen om op een e-mail lijst gezet te worden waarover een melding gestuurd wordt wanneer er een nieuwe contest gestart wordt

Stiekem is één van de doelen van deze contest natuurlijk dat we mensen "vasthouden" in PRG, dus dan gooien we een beetje onze eigen glazen in met zo'n mailinglist. Als er een gebruikersinitiatief voor is: be my guest.

quote:

NMe schreef op dinsdag 06 januari 2009 @ 02:09:
Valide: ja. Zal het voorkomen in de set waarin jullie scores tegen elkaar opgemeten worden? Nee.

Ok, dan blijft dus de vraag openstaan:

quote:

KoW schreef op zaterdag 03 januari 2009 @ 20:35:
Is het echter wel toegestaan om een jewel te wisselen met een positie in de lege kolom zoals b.v.
code:

1 889
2 227
3 567
XXXXX
XXXXX

In dit voorbeeld zou de 2 op positie (0,1) verplaatst kunnen worden naar Oost.
Mag dat?
Of moet je een lege kolom zien als een echte muur?

Verder is mijn programma nog steeds een factor 20 te traag...

quote:

NMe schreef op vrijdag 07 november 2008 @ 16:15:

We zouden best zo sneaky kunnen zijn om het veld in tweeën te splitsen zonder een muur te gebruiken door gewoon een kolom géén invulling te geven.

In tweeën splitsen -> geldt dus als een muur.

Ik baal er best van dat ik in december en ook nu veel te weinig tijd hiervoor heb Ik heb nog zoveel leuke ideeen, maar nu moeten ze nog uitgewerkt worden... Nou ja, ik zie wel of ik nog iets red

Helaas lukt het mij ook niet meer om iets in te leveren. In november heb ik een uur of tien gebruikt voor een redelijke opzet, maar in december door allerlei omstandigheden totaal geen tijd meer gehad om iets aan m'n code te doen. Hopelijk heb ik bij de volgende contest meer tijd...

Mijn huidige versie heb ik om zeep geholpen en svn was er nog niet. Hij was bovendien nog veel te traag. Dus helaas geen inzending van mijn kant

Ik ga zeker iets inzenden, ook al ben ik effectief niet verder gekomen dan de eerste de beste move uitvoeren
Wel moet ik m'n zondag vrijhouden, want ik heb er zeker al een maand niks meer aangedaan...

Ik zou ook aan alle afhaekers willen adviseren om toch iets in te leveren, het is altijd leuk om te zien wat anderen bedacht hebben, eventueel geef je aan de organisatoren door dat je programma niet gerund hoeft te worden om hen tijd te besparen

Ik zit nog een beetje vast in het zoeken van de mogelijke moves. Ik kan momenteel niet veel anders bedenken dan bruteforce.

Heeft iemand nog een klein tipje van de sluier?

Wat bedoel je met brute force? Gewoon alle moves proberen en kijken of ze lukken?

Gewoon kijken of een bepaalde move iets oplevert (een figuur vormt).

Bedenk welke moves er allemaal mogelijk zijn, en baseer daar je zoektocht in het veld op.

Om te kijken of een bepaalde move mogelijk is hoef je niet helemaal figuren te gaan zitten detecteren. Dan heb je genoeg aan de kennis of ten minste een van de twee verplaatste blokjes deel uit maakt van een rij van 3 (met andere woorden, er is een gelimiteerde set combinaties van blokjes om de te verplaatsen blokjes heen).

Bijvoorbeeld, als er blokjes met relatieve coordinaten (-1, -1) en (-2, -1) dezelfde kleur hebben als het blokje op (0, 0), dan kun je dat blokje omhoog bewegen (met omhoog bedoel ik dan de richting (0, -1)). En natuurlijk zijn er meer van dit soort dingen die je moet gaan testen, maar meer hoef je feitelijk niet te doen.

Om erachter te komen wat voor score de move op gaat leveren dan kun je wel net zo goed de move uitvoeren, er is niet echt een andere manier om erachter te komen.

Nou, mijn inzending is verstuuurd. Het zal geen topper worden, maar ik had me voorgenomen in ieder geval íets in te sturen.

Ik denk dat ik me ook maar moet gaan concentreren op het submitbaar maken van m'n code. Ik denk niet dat ik nog veel tijd heb om algoritmische verbeteringen te maken... En dacota heeft ondertussen vast stiekem nog een betere score behaald die hij achter de hand houdt, maar dat is dan jammer

quote:

.oisyn schreef op woensdag 07 januari 2009 @ 13:51:
Ik denk dat ik me ook maar moet gaan concentreren op het submitbaar maken van m'n code. Ik denk niet dat ik nog veel tijd heb om algoritmische verbeteringen te maken... En dacota heeft ondertussen vast stiekem nog een betere score behaald die hij achter de hand houdt, maar dat is dan jammer

Nee, het heeft bij mij volledig stilgelegen door vakantie en feestdagen. Ook heb ik vrijwel geen tijd meer, alleen vanavond nog, dus ik ga kijken wat ik nog kan doen en het daarna ook maar submitbaar maken.

Ik ben wel benieuwd waar jullie de uiteindelijke snelheid vandaan halen.
Mij kost het enorm veel tijd om gewoon een paar zetten vooruit te rekenen en probeer ik te optimaliseren dan loopt de code al snel een dood spoor in.
Voorlopig is de code iig nog een factor 5 a 10 te traag voor het kleine testgridje. Een groter grid heb ik nog niet durven proberen.

Dat zit hem vooral in het niet steeds (her)scannen van het hele veld op combinaties/zetten/etc. Dat scheelt meer dan de helft in snelheid. Daarbij is het gebruikte algoritme voor het vinden van combinaties/moves van ook belang voor de snelheid.

Even nog voor de duidelijkheid: Is de hoeveelheid punten voor een gecombineerd figuur per definitie 250?

Correct, ik voel hier een optimalisatie aankomen

king_charles wijzigde dit bericht 07-01-2009 20:19 (75%)

quote:

king_charles schreef op woensdag 07 januari 2009 @ 20:18:
Correct

Oki

Ik heb mijn inzending klaar staan, alleen wil ik nog ff de resterende dagen mijn hoofd breken over eventuele optimalisaties Verder vooruit kijken dan 1 move levert in mijn code somehow een infinite loop op en dat is verdomd lastig te debuggen bij de huidige constructie

Dat is zeker lastig, maar wel handig om nog proberen te fixen. Maximaal 1 move vooruit levert niet echt een hoge score op, of je hebt een heel slimme AI natuurlijk

Ik ben ook nog wat aan het optimaliseren, aanpassen van de algoritmes doe ik niet meer. Dat vind ik te risicovol met nog zo weinig tijd over. Ik heb vandaag alweer 25% aan snelheid gewonnen, wat vrijwel automatisch een paar procent hogere score oplevert

king_charles wijzigde dit bericht 07-01-2009 20:31 (43%)

quote:

Arjan schreef op woensdag 07 januari 2009 @ 10:21:
Ik zou ook aan alle afhaekers willen adviseren om toch iets in te leveren, het is altijd leuk om te zien wat anderen bedacht hebben, eventueel geef je aan de organisatoren door dat je programma niet gerund hoeft te worden om hen tijd te besparen

Helaas zitten alle goede ideeën alleen nog maar in m'n hoofd. De code die ik tot nu toe geschreven heb lijkt waarschijnlijk erg veel op de code waarmee bijna iedereen hier begonnen is: figuren ontdekken, blokjes laten vallen en punten tellen. En daarnaast nog de nodige fouten en ontbrekende stukken...

Ik kan het programma hier (na de sluitingsdatum) wel posten, maar dan zal ik de opmerking toevoegen dat de code niet bekeken hoeft te worden om jullie tijd te besparen.

Ik ga het zo afronden, ik heb nog wat kleine optimalizaties doorgevoerd wat me nu op bijna 330k moves/sec brengt, maar geen hogere score. Oftewel, ik zit op een dead end. Ter illustratie, ik heb een 10% run (10000 stappen in 1.5 minuut) gedraaid op alle verschillende snelheden van mijn CPU, met het volgende resultaat:
code:

Step:           10000

CPU:            2.6 Ghz
Score:          5220100
Moves/sec:      329326

CPU:            2.0 Ghz
Score:          5108250
Moves/sec:      241641

CPU:            1.6 Ghz
Score:          4950350
Moves/sec:      188206

CPU:            1.2 Ghz
Score:          4775450
Moves/sec:      132626

CPU:            0.8 Ghz
Score:          4378900
Moves/sec:      80850

Oftewel, met mijn algoritme zijn de aantal moves/sec vrijwel lineair afhankelijk van de CPU snelheid, maar de scores absoluut niet. Conclusie: ik kan de code helemaal suf optimalizeren, maar veel hogere scores ga ik er niet door krijgen. Sterker nog, als ik mijn programma veel meer (10x zoveel) tijd geef, haal ik de finish niet

@DaCoTa Zijn deze scores met 2 cores? (T9500 toch)?

quote:

DaCoTa schreef op woensdag 07 januari 2009 @ 23:59:
Ik ga het zo afronden, ik heb nog wat kleine optimalizaties doorgevoerd wat me nu op bijna 330k moves/sec brengt, maar geen hogere score. Oftewel, ik zit op een dead end. Ter illustratie, ik heb een 10% run (10000 stappen in 1.5 minuut) gedraaid op alle verschillende snelheden van mijn CPU, met het volgende resultaat:
code:

Step:           10000

CPU:            2.6 Ghz
Score:          5220100
Moves/sec:      329326

CPU:            2.0 Ghz
Score:          5108250
Moves/sec:      241641

CPU:            1.6 Ghz
Score:          4950350
Moves/sec:      188206

CPU:            1.2 Ghz
Score:          4775450
Moves/sec:      132626

CPU:            0.8 Ghz
Score:          4378900
Moves/sec:      80850

Oftewel, met mijn algoritme zijn de aantal moves/sec vrijwel lineair afhankelijk van de CPU snelheid, maar de scores absoluut niet. Conclusie: ik kan de code helemaal suf optimalizeren, maar veel hogere scores ga ik er niet door krijgen. Sterker nog, als ik mijn programma veel meer (10x zoveel) tijd geef, haal ik de finish niet

Dan moet je dus niet meer de performance verbeteren, maar shortcuts in je algo vinden. Mischien kan je nog wel sommige branches veel eerder af kappen.

quote:

rwb schreef op donderdag 08 januari 2009 @ 08:53:
[...]
Dan moet je dus niet meer de performance verbeteren, maar shortcuts in je algo vinden. Mischien kan je nog wel sommige branches veel eerder af kappen.

Daar zit precies het probleem, als ik meer afkap, kom ik te vaak in een doodlopend pad terecht en moet ik terug, iets wat nog veel meer tijd kost.

quote:

phsmit schreef op donderdag 08 januari 2009 @ 08:27:
@DaCoTa Zijn deze scores met 2 cores? (T9500 toch)?

Ja.

Ik ben nu het ding aan het testen, thuis draait hij continue volledige runs achter elkaar, dan kan ik vanavond zien wat de variatie in de score is en of er nog iets crashed.

Wat gebruiken jullie voor multithreading frameworks? (If any?) Of wil je dat nog niet kwijt voor de deadline?

Ik heb geprobeerd met wat OpenMP directives meerdere cores te gebruiken en hoewel dat in principe wel werkte, kon ik het niet echt goed testen op mijn PC (1 core), bij een test op een multi-core machine traden sporadische rare bugs op (waarschijnlijk was ik nog wat niet-thread-safe code vergeten sequentieel te laten uitvoeren) en de snelheidswinst viel me ook tegen; bij lange na niet lineair (zeker niet als het aantal cores stijgt).

quote:

Soultaker schreef op donderdag 08 januari 2009 @ 11:22:
Wat gebruiken jullie voor multithreading frameworks? (If any?) Of wil je dat nog niet kwijt voor de deadline?

OTL

Oisyn's Threading Library . Geen dus, ik heb een simpel job-systeempje in m'n framework ingebouwd. Je kan een Job implementeren die je met AddJob() toevoegt aan de queue (kan vanaf elke thread), en als je een WaitForAll() doet dan gaat de huidige thread meewerken aan de jobqueue totdat alles klaar is.

quote:

king_charles schreef op woensdag 07 januari 2009 @ 16:49:
Dat zit hem vooral in het niet steeds (her)scannen van het hele veld op combinaties/zetten/etc. Dat scheelt meer dan de helft in snelheid. Daarbij is het gebruikte algoritme voor het vinden van combinaties/moves van ook belang voor de snelheid.

Mijn huidige versie doet dat inderdaad ook niet. Ik zit er nog over te denken om ook de score en de veldrepresentatie (gedeeltelijk) mee te kopieren.

Wel was mijn conclusie dat de winst hem niet echt zit in de zoektocht naar opties, maar meer in het doorrekenen van de zet-opties.

Met mijn algoritme probeer ik steeds wel x zetten vooruit te kijken, maar uiteindelijk probeert de routine lang niet alle opties die in het veld aanwezig zijn.
Een grote vertrager is bij mij dat voor elke veld-representatie er 50 nieuwe zetten mogelijk zijn.

Ook het backup-restore algoritme heeft hier last van omdat zodra een doodlopend pad wordt weggestreept een van de andere takken ook weer een verwijzing geeft naar de eerder afgekeurde zet en soms alsnog weer doodloopt.

quote:

KoW schreef op donderdag 08 januari 2009 @ 13:35:

Met mijn algoritme probeer ik steeds wel x zetten vooruit te kijken, maar uiteindelijk probeert de routine lang niet alle opties die in het veld aanwezig zijn.
Een grote vertrager is bij mij dat voor elke veld-representatie er 50 nieuwe zetten mogelijk zijn.

Alle moves x zetten vooruit kijken noemen we brute-force. Dus het is juist de bedoeling om een slimme manier te vinden om moves die weinig opleveren af te kappen of helemaal niet te bekijken en alleen ver vooruit te kijken met een percentage (goede) moves.

quote:

KoW schreef op donderdag 08 januari 2009 @ 13:35:
[...]
Ook het backup-restore algoritme heeft hier last van omdat zodra een doodlopend pad wordt weggestreept een van de andere takken ook weer een verwijzing geeft naar de eerder afgekeurde zet en soms alsnog weer doodloopt.

Dit is gewoon een kwestie van goed bijhouden welke moves doodlopen bij een gegeven movenummer, zodat je niet opnieuw een zet doet waarvan je al eerder ontdekte dat hij doodliep op dat moment.

king_charles wijzigde dit bericht 08-01-2009 16:46 (29%)
Reden: typo

quote:

king_charles schreef op donderdag 08 januari 2009 @ 14:49:
Alle moves x zetten vooruit kijken noemen we brute-force. Dus het is juist de bedoeling om een slimme manier te vinden om moves die weinig opleveren af te kappen of helemaal niet te bekijken en alleen ver vooruit te kijken met een percentage (goede) moves.

Jawel, maar om te kunnen bepalen hoe goed een zet is moet je de zet wel spelen. Wanneer er dan 50 verschillende opties zijn is dat best veel.
Het algoritme pakt nu uit die zetten gewoon de best scorende, maar moet dan dus weer die 50 opties uitwerken.

quote:

Dit is gewoon een kwestie van goed bijhouden welke moves doodlopen bij een gegeven movenummer, zodat je niet opnieuw een zet doet waarvan je al eerder ontdekte dat hij doodliep op dat moment.

Ja, maar hoe lang hou je dat dan vast.
Zodra een veld eenmaal is doorgevallen (na een paar zetten) kan op diezelfde positie een move ontstaan die juist wel valide is.
Op dit moment doe ik die controle dus niet.

Zoiets en het iets slimmer omgaan met vorige zetten staat nog wel op het programma mocht ik nog wat tijd overhebben. (Waarschijnlijk niet dus)

Op dit moment heeft een verkeerd uitgevoerde optimalisatie mijn uitvoer ongeldig gemaakt. Dat moet ik eerst even fixen en verder lijkt het me handig om toe te werken naar iets wat ook zonder mijn ingrijpen een spel uit kan spelen.

Het huidige programma heeft overigens een gemiddelde score van nog geen 300 per zet en een snelheid van 500 zetten in 30 seconden

quote:

Soultaker schreef op donderdag 08 januari 2009 @ 11:22:
Wat gebruiken jullie voor multithreading frameworks? (If any?) Of wil je dat nog niet kwijt voor de deadline?

Ik heb geprobeerd met wat OpenMP directives meerdere cores te gebruiken en hoewel dat in principe wel werkte, kon ik het niet echt goed testen op mijn PC (1 core), bij een test op een multi-core machine traden sporadische rare bugs op (waarschijnlijk was ik nog wat niet-thread-safe code vergeten sequentieel te laten uitvoeren) en de snelheidswinst viel me ook tegen; bij lange na niet lineair (zeker niet als het aantal cores stijgt).

DTL

DaCoTa's Threading Library . Ook geen dus, ik heb een producer met meerdere consumers met standaard Java Threads. Producer heeft alle logica om te bepalen welke velden doorgerekend moeten worden en de consumers gaan dat doen. Het doorrekenen van de consumer bestaat uit het vinden van moves en daarna alle unieke moves van dat veld doorrekenen. Alle resultaatvelden worden teruggegeven aan de producer en die bepaald welke nieuwe velden in de workload opgenomen moeten worden en welke weggegooid kunnen worden. Pretty straightforward eigenlijk.

De 20 uur loop van testset 1 is geslaagd, na 83 runs zit de gemiddelde score op 52.4m, met een variatie van ongeveer 400.000. Ik ben alleen vergeten alle outputs te bewaren, dus ik kan ze niet valideren. Nu doe ik nog nog een keer hetzelfde voor testset 3, maar deze keer bewaar ik wel alle outputs zodat ik die nog kan valideren.

Op mijn E6600 (2 cores, 2,4 GHz) met ubuntu en sun java 6 heb ik nu gemiddeld een score van ~53200000. Ik heb helaas geen andere systemen beschikbaar om op te testen

De resultaten van de supergrote set komen nog...

Netjes . I think we have a winner.

Is er al iets bekend over een volgende opgave? Of is er zoals ik verwacht eerst een pauze?

Zoiezo een kleine pauze... we hebben wel wat ideeen nog liggen maar die zijn nog niet helemaal uitgewerkt. Ook wij zijn lui dus hoe lang dat gaat duren daar ga ik geen uitspraken over doen
Wel durf ik te zeggen dat er minder tijd tussen zal zitten dan de vorige keer.

Mijn inzending ligt nu in de mailbox van tweakers

Hm, al redelijk wat mensen hebben al wat ingezonden en ik heb nog niet eens een fatsoenlijk algoritme... Vanmiddag heb ik nog wel een soort van testje gedaan om te kijken of mijn aanpak wel redelijk efficient was. Het kwam erop neer dat ik de twee meisjes tegenover me telkens lastigviel met getallen vragen en die dan handmatig te verwerken in het spel. De conclusie was overigens dat mijn 'oude' aanpak waarschijnlijk toch beter werkt. Dus ik ga maar eens aan de slag met de oude aanpak in mijn nieuwe code zetten.

Ik ben net een beetje bezig om het spel te laten draaien. Hij kiest nu een willekeurige zet, maar ik zie dat er soms nog iets niet helemaal goed gaat.

Maar ik vraag me af of ik toe kom aan een ander algoritme dan willekeurig eentje uitzoeken.

Ik zit hier nu ergens in een auto de boel te uploaden.

offtopic:
(heb nog geen internet hier.... brr...)

Uiteindelijk toch nog een stomme bug gevonden in het opslaan van de zet-opties waardoor sommige zetten onterecht niet doorgerekend werden.
Vervolgens ging de snelheid enorm vooruit, maar nu bleek vanavond bij het langer draaien van de testset dat er toch af en toe verkeerde moves tussen staan.

Op een of andere manier lijkt het gedeelte wat alleen het gekozen pad bewaard niet te werken. Daardoor kwamen er soms zetten voorbij die uit een heel andere al lang afgeschreven tak komen.
Vanwege de te korte tijd om dat nu nog op te lossen zit er nu een extra check op. Elke move wordt nogmaals gecontroleerd of hij wel score geeft voor hij in de lijst gezet wordt.

Het programma geeft op mijn pc een score van 169 per zet en het lukt hem nu bijna om de 100000 zetten te halen.

Edit: op deze laptop haalt ie slect de 43000 zetten met wel dezelfde score per zet. (Als de tijd niet gehaald kan worden draait ie met een minimum waarde)

KoW wijzigde dit bericht 09-01-2009 23:55 (8%)

quote:

Creepy schreef op vrijdag 09 januari 2009 @ 16:53:
Zoiezo een kleine pauze... we hebben wel wat ideeen nog liggen maar die zijn nog niet helemaal uitgewerkt. Ook wij zijn lui dus hoe lang dat gaat duren daar ga ik geen uitspraken over doen
Wel durf ik te zeggen dat er minder tijd tussen zal zitten dan de vorige keer.

Juist.

Het verzinnen van een goede opdracht die zowel voor beginners als gevorderden een uitdaging kan zijn is lastig genoeg, en dan proberen we daarnaast ook nog eens elke keer iets nieuws te verzinnen. En dan heb ik het nog niet over de validator die elke keer geschreven wordt en de daadwerkelijke runs van de inzendingen. Minstens een maandje pauze mag daarna toch wel?

Woei. Een mijlpaal.

De 50x50 set is eindelijk een keer gelukt (maar wel met een move te weinig )

--Statistieken--
Aantal moves		99999
0scores (ongeldige zet)	0
Score per zet		84.67885
Grootste zet score	850, zet 928

Snel opruimen en submitbaar maken.

Ik heb de mijne al opgeruimd en submitbaar gemaakt. Ik wacht nog wel even met inzenden voor het geval ik tegen de tijd een inval krijg en vooral tot in dit topic de laatste addertjes onder het gras uitkomen

't Doet nog steeds 'gewoon' de 1e de beste move uitvoeren dat de beste score in het veld oplevert, met een score van rond de 23M op de testset. Ik denk dat mijn code op het contest vooral moet hebben van de documentatie, indeling en robuustheid. Anyway, we zien wel

quote:

BalusC schreef op zaterdag 10 januari 2009 @ 00:53:
't Doet nog steeds 'gewoon' de 1e de beste move uitvoeren dat de beste score in het veld oplevert, met een score van rond de 23M op de testset. Ik denk dat mijn code op het contest vooral moet hebben van de documentatie, indeling en robuustheid. Anyway, we zien wel

Dat was ik eerst ook van plan....in Perl. Maar die bleek niet snel genoeg voor de 50x50. Dus heb ik alles geport naar C. Met 0 C ervaring was dat erg leerzaam moet ik zeggen Toen had ik wel genoeg snelheid om wat verder te kijken, maar ondanks dat ik nu tussen de 300K en 400K zetten per seconde kan doorrekenen komt mijn score op de officiele testset niet verder dan 400. Ben dus benieuwd wat de anderen voor truukjes hebben uitgehaald!

Hee, de deadline is veranderd. Daar stond eerst 10 januari.

quote:

KoW schreef op zaterdag 10 januari 2009 @ 09:24:
Hee, de deadline is veranderd. Daar stond eerst 10 januari.

quote:

MrHuge schreef op woensdag 24 december 2008 @ 08:55:
Uit de openingspost:

[...]

10 januari valt in mijn kalender op een zaterdag, niet op een maandag .

Ik denk dat het daarom veranderd is

Ik heb de mijne ook maar ingezonden... Laten we zeggen dat hij werkt

Ik ben toch erg nieuwsgierig naar andere inzendingen en hoe deze opgelost zijn!