CodeCup 2009

[Verwijderd]

Wat is dit voor een Topic?

Vorig jaar heeft een aantal tweakers al mee gedaan aan de CodeCup, dit jaar is er weer een nieuw spel. Het spel is iets makkelijker dan vorig jaar, maar om een goede AI te schrijven vormt het een flinke uitdaging.

Wat is het spel van 2009?

Het spel van dit jaar heet Pillars, een 2D versie van het wiskunde spelletje Nim. Om en om plaatsen twee spelers een rechthoek (mag ook één enkel hokje zijn) op het speelveld. De speler die het laatste hokje vult verliest het spel. Ook heb je de mogelijkheid om op een bepaald moment je joker in te zetten. Afhankelijk van het moment wanneer je je joker inzet, kun je meer punten scoren als je wint, maar ook minder als je verliest. Voorbeeldspel Regels Voorbeeld programma's

Hoe werkt de CodeCup?

Bij de CodeCup spelen steeds twee computerprogramma's een bepaald spel tegen elkaar. In een competitievorm wordt bepaald welk programma het beste is. In de eerste ronde mag ieder programma dat eerst geverifieerd is, meespelen om een plaats in de eindronde. De programma's worden tegenover elkaar gezet door het 'Zwitserse' algoritme dat ook bij schaakwedstrijden wordt gebruikt. In de eindronde spelen de beste 16 programma's een volledige competitie, waarbij de beste programma's pas in de laatste ronde tegen elkaar uitkomen om het zo spannend mogelijk te houden. Tussen de start en de officiele wedstrijd (17 januari 2009) wordt er acht keer een testcompetitie gehouden. In deze testcompetitie kan je bekijken hoe je programma het doet tegen andere de andere programma's. Aan de hand van de spelverslagen van jouw en andere programma's kan je weer aan de slag om je programma te verbeteren. Er is ook mogelijkheid om thuis te testen met Caia. Hiermee kun je twee spelers tegen elkaar laten spelen, Caia levert twee gecompileerde spelers aan waartegen je je programma kunt testen. Sinds vorig jaar zijn er een aantal bugs uit de software verdwenen en is er een competition manager die een volledige competitie kan laten spelen tussen de programma's.

Valt er een prijs te winnen?

Jazeker! Er zijn grotere en kleinere prijzen, wat het precies is, is een verrassing! De beste Nederlandse middelbare scholier of docent in de eindcompetitie wint de Windesheim-Digitalisprijs van 250 euro!

Limieten, deadlines, beperkingen.

Je programma moet geschreven zijn in C(++), Java, Pascal of Python (de CodeCup is bezig met Haskell, voor de echte die-hards). Op de site is voorbeeldcode voor deze talen te downloaden. Je moet de broncode insturen, deze moet op een floppy passen en bovendien moet je broncode uit één bestand bestaan (Java programmeurs kunnen alle klassen in hun bestand zetten, maar alleen de klasse waarin de main methode zit mag dan public zijn, de rest voorzie je niet van een access modifier) Ook heeft je programma gedurende elk potje maar 5 seconden bedenktijd die deze zelf mag indelen over de zetten. De testcompetities en de officiële competities beginnen allemaal om 12:00 GMT (tijdens de zomertijd dus om 14:00, tijdens de winter tijd om 13:00). Je kunt van alle goedgekeurde programma's kiezen welk programma mee gaat doen in de competitie door deze op Active te zetten. Verder mag iedereen meedoen, maar vanzelfsprekend mag je je programma niet vaker dan één keer insturen.

Ja, en wat nu?

Schrijf een programma, stuur deze in en deel je ervaringen! Welke algoritmes heb je gebruikt? Tegen welke problemen loop je aan? Vragen over de spelregels, onduidelijkheden, iets werkt niet?

[ Voor 86% gewijzigd door Verwijderd op 12-08-2008 10:19 ]

[Creepy]

offtopic:
En nu met toestemming

[ Voor 49% gewijzigd door Creepy op 12-08-2008 10:11 ]

[r0bert]

Waarom is het aantal scripttalen beperkt? Ik wil wel meedoen, maar dan met javascript. Ik begrijp dat dat niet mag, mocht er nog versoepeling in komen dan zou dat erg leuk zijn natuurlijk

[Verwijderd]

Leuk. Ik ga meedoen met Python Is er ergens een mailinglist waarvoor ik me op kan geven? Een duidelijkere link naar de CodeCup website is misschien ook leuk

Overigens telt de standard library (als je eventueel modules daaruit gebruikt) ook mee in je grootte van het script of moet alle code (dus inclusief eventuele modules) op die 1.44 MB passen?

[ Voor 67% gewijzigd door Verwijderd op 12-08-2008 10:20 ]

[Verwijderd]

We hebben de mailinglist een aantal jaren geleden dichtgegooid vanwege de grote hoeveelheid spam. Gelukkig is er GoT, maar we hebben ook een forum op de website draaien voor de mensen die een account hebben.

Voor wat betreft scripttalen, als er een gangbare taal is (zoals javascript bijvoorbeeld) en als deze beschikbaar is als standaard package in Debian etch/lenny, dan kunnen we er overnadenken (helaas heb ik geen javascript package gevonden voor Debian, ik weet ook niet of javascript een stdin en stdout heeft)!
Uiteraard zijn scripttalen wat betreft snelheid natuurlijk de mindere van C(++).

Voor de liefhebbers: We zijn bezig met Haskell.


CodeCup

[Verwijderd]

De grootte van het file wat je instuurt mag niet boven de 1.44 MB uitkomen.
De modules die je nodig hebt van Python (kunnen er nooit veel zijn) tellen dus niet mee.
Voor C(++), Java en Pascal gelden dezelfde regels.

[veldsla]

caiaio van het caia testsysteem compileert niet op een linux amd64 machine.
De asm code in cpuspeed is blijkbaar niet compatible met een amd64 cpu.

Ik krijg deze errors

g++ -Wall -O2   -c -o cpuspeed.o cpuspeed.cc
/tmp/ccdKuIlM.s: Assembler messages:
/tmp/ccdKuIlM.s:16: Error: suffix or operands invalid for `push'
/tmp/ccdKuIlM.s:20: Error: suffix or operands invalid for `pop'
/tmp/ccdKuIlM.s:33: Error: suffix or operands invalid for `push'
/tmp/ccdKuIlM.s:37: Error: suffix or operands invalid for `pop'

edit: Ik heb even in de source gegluurd en zag dit:
/* Use this code (older version; less accurate) if you have compiler or linker problems:

Dat stuk code compileert wel.

[ Voor 14% gewijzigd door veldsla op 12-08-2008 21:10 ]

[Verwijderd]

Tja, dat stukje van caia is nou niet bepaald het beste
De oude code hebben we destijds vervangen omdat we problemen hadden met Intel cores. Er werd een compiler optimalisatie gedaan waardoor het oude stuk niet correct werkte.

[Verwijderd]

r0bert schreef op dinsdag 12 augustus 2008 @ 10:12:
Waarom is het aantal scripttalen beperkt? Ik wil wel meedoen, maar dan met javascript. Ik begrijp dat dat niet mag, mocht er nog versoepeling in komen dan zou dat erg leuk zijn natuurlijk

Leer jezelf gewoon even een andere taal aan. Ook dat kan een doel zijn van zo'n competitie.

[GrooV]

Interressante competitie, misschien maar eens naar gaan kijken als ik tijd overheb

[Haan]

Verwijderd schreef op dinsdag 12 augustus 2008 @ 23:40:
[...]

Leer jezelf gewoon even een andere taal aan. Ook dat kan een doel zijn van zo'n competitie.

Maar het kan ook een drempel zijn om mee te gaan doen.

Ik neem aan dat je weinig kans maakt als je geen ervaring hebt met AI en/of redelijke wiskundige kennis?

[Verwijderd]

Haan schreef op woensdag 13 augustus 2008 @ 09:21:
[...]

Maar het kan ook een drempel zijn om mee te gaan doen.

Ik neem aan dat je weinig kans maakt als je geen ervaring hebt met AI en/of redelijke wiskundige kennis?

Als jij een raster kan begrijpen en hoe je lists in lists zet dan kun je dit ook. Je kan dan je eigen strategie bedenken.

Python is relatief gezien simpel om te leren en daarbij hebben ze volledige implementaties op de site staan waar je zelf je extra logica in kan zetten als je het simpel wil houden

Je kan natuurlijk AI gaan verwerken in je programma maar over het algemeen gok ik dat je gewoon het grootst mogelijke blokje gaat tonen en x aantal zetten vooruit rekent. Als AI kun je proberen de volgende move van je tegenstander te bepalen (bijvoorbeeld: tekent hij het grootst mogelijke oppervlak of doet hij iets anders) en op basis daarvan bepalen hoe de game gaat aflopen maar dat moet je zelf weten, dat hoeft niet

[ Voor 26% gewijzigd door Verwijderd op 13-08-2008 09:40 ]

[Creepy]

Een mini-max algoritme valt ook onder de noemer "AI" maar is eigenlijk niet veel meer dan het bruteforcen van de mogelijke zetten en het toekennen van een bepaalde score aan het speelbord op een bepaald moment. Als je echt niks van AI weet waar wel algemene programmeer kennis hebt dan is dit een algoritme dat vrij simpel te begrijpen en te implementeren is.

[Verwijderd]

Creepy schreef op woensdag 13 augustus 2008 @ 09:45:
Een mini-max algoritme valt ook onder de noemer "AI" maar is eigenlijk niet veel meer dan het bruteforcen van de mogelijke zetten en het toekennen van een bepaalde score aan het speelbord op een bepaald moment. Als je echt niks van AI weet waar wel algemene programmeer kennis hebt dan is dit een algoritme dat vrij simpel te begrijpen en te implementeren is.

En het wordt al een stuk meer AI-erig als je ook meteen in jouw move de mogelijke volgende move van je tegenstander gaat bepalen zoals die in andere algoritmes zou werken en daarmee dus meteen kan uitvinden hoe de game waarschijnlijk gaat aflopen. Standaard algoritmes voorspellen levert standaard uitkomsten op

[jmzeeman]

Ook heeft je programma gedurende elk potje maar 5 seconden bedenktijd die deze zelf mag indelen over de zetten.

Wat gebeurt er als je tijd op is verlies je dan automatisch? Zou wel grappig zijn, je zou dan als strategie in de eerste fase van het spel zoveel mogelijk 1x1 blokjes moeten neer gooien om grotere blokken te voorkomen zodat er veel zetten komen en op die manier je tegenstander in tijdsnood te brengen .
Als ik tijd kan vinden ga ik me hier maar is op storten, kijken of ik m'n AI lessen al weer vergeten ben.

[Verwijderd]

jmzeeman schreef op woensdag 13 augustus 2008 @ 10:02:
[...]

Wat gebeurt er als je tijd op is verlies je dan automatisch? Zou wel grappig zijn, je zou dan als strategie in de eerste fase van het spel zoveel mogelijk 1x1 blokjes moeten neer gooien om grotere blokken te voorkomen zodat er veel zetten komen en op die manier je tegenstander in tijdsnood te brengen .
Als ik tijd kan vinden ga ik me hier maar is op storten, kijken of ik m'n AI lessen al weer vergeten ben.

When you make an invalid move or when you use too much time, you lose the game. It will count as an irregular game loss. The opponent automatically wins the game (with 27-0).

[Dricus]

Dit wordt wel weer ff wat anders dan de contest van 2008. In deze opdracht heeft je proggie maar 5 seconden de tijd, vorig jaar 1 minuut geloof ik. Heel erg veel tijd om optimized-brute-force (want dat is min-max toch eigenlijk ) vooruit te kijken is er dus niet. Leuke uitdaging dus! Ik denk dat ik ook weer mee ga doen .

[ Voor 6% gewijzigd door Dricus op 13-08-2008 11:01 ]

[Soultaker]

Die irregular losses werken trouwens wel goed in het voordeel van de tegenstander, die er helemaal niets bijzonders voor hoeft te doen. Waarom is de score dan niet gewoon 18+joker, of 18+(vakjes over)/10 als de joker nog niet ingezet is? Dat is immers het maximum wat de speler op dit punt nog kan behalen.

[Verwijderd]

Haan schreef op woensdag 13 augustus 2008 @ 09:21:

Maar het kan ook een drempel zijn om mee te gaan doen.

Het kan een drempel zijn. Maar zeg nou zelf, wie dit in Javascript wil doen is volkomen kansloos. Hetzelfde geldt voor bijvoorbeeld PHP.

[Zyppora]

Verwijderd schreef op woensdag 13 augustus 2008 @ 12:25:
[...]

Het kan een drempel zijn. Maar zeg nou zelf, wie dit in Javascript wil doen is volkomen kansloos. Hetzelfde geldt voor bijvoorbeeld PHP.

Waarom zou dat zo zijn? Aangezien je 5 seconden krijgt per zet, kan dat in bijna alle talen nog gebeuren. Daarnaast gaat het, vooral bij Javascript, vooral om de uitdaging en niet zozeer om de winkansen.

[Dricus]

Zyppora schreef op woensdag 13 augustus 2008 @ 13:35:
[...]
Waarom zou dat zo zijn? Aangezien je 5 seconden krijgt per zet, kan dat in bijna alle talen nog gebeuren. Daarnaast gaat het, vooral bij Javascript, vooral om de uitdaging en niet zozeer om de winkansen.

Je krijgt geen 5 seconden per zet, maar in totaal 5 seconden om al je zetten uit te denken:

Ook heeft je programma gedurende elk potje maar 5 seconden bedenktijd die deze zelf mag indelen over de zetten.

[Verwijderd]

Zyppora schreef op woensdag 13 augustus 2008 @ 13:35:
[...]


Waarom zou dat zo zijn? Aangezien je 5 seconden krijgt per zet, kan dat in bijna alle talen nog gebeuren. Daarnaast gaat het, vooral bij Javascript, vooral om de uitdaging en niet zozeer om de winkansen.

Zie ook dit:

http://shootout.alioth.de...st=all&lang=php&lang2=gcc

De grijze getallen is hoeveel keer C sneller is dan PHP in die verschillende berekeningen

[Zyppora]

Damn je hebt gelijk Excuus.

Dan wordt het wel een beetje krap ja (NOG grotere uitdaging).

[Soultaker]

simonkey: maar als je PHP vergelijkt met Python dan kan PHP best aardig meekomen, en Python wordt ook ondersteund.

Ik denk dus dat je het probleem niet moet zoeken in de vermeende geschiktheid van de taal, maar in het simpele feit dat elke extra taal extra werk oplevert voor de organisatoren (ze moeten programma's immers server-side compileren en uitvoeren) en ze dus logischerwijs niet honderd verschillende talen kunnen aanbieden.

(Overigens is meedoen i.m.o. belangrijker dan winnen; waarschijnlijk zal het winnende programma wel in C, C++, Java of misschien Pascal geschreven zijn, maar dat betekend niet dat je geen zinnige inzending kunt doen in Python.)

[ Voor 18% gewijzigd door Soultaker op 13-08-2008 15:21 ]

[Verwijderd]

We hebben hier goed zitten zoeken naar javascript interpreters op linux machines, maar we kunnen echt niets vinden. Mochten we het over het hoofd hebben gezien, dan worden we daar natuurlijk graag op gewezen.

Voor wat deze competitie denken we dat de snelheid van de taal niet de doorslag gaat geven...

Het Haskell gedeelte is overigens nu helemaal klaar. Volgende week zaterdag kunnen jullie gaan committen (we gebruiken GHC 6.6).

Succes allemaal!

[Verwijderd]

Soultaker schreef op woensdag 13 augustus 2008 @ 11:53:
Die irregular losses werken trouwens wel goed in het voordeel van de tegenstander, die er helemaal niets bijzonders voor hoeft te doen. Waarom is de score dan niet gewoon 18+joker, of 18+(vakjes over)/10 als de joker nog niet ingezet is? Dat is immers het maximum wat de speler op dit punt nog kan behalen.

Ik heb dit even overlegd en we vinden dit een betere regel dan de 27-0. Dit gaan we implementeren.
Bedankt voor de tip;)

Voor de mensen die caia al hebben gedownload, hou de homepage even in de gaten voor updates.

[Verwijderd]

Soultaker schreef op woensdag 13 augustus 2008 @ 15:20:
simonkey: maar als je PHP vergelijkt met Python dan kan PHP best aardig meekomen, en Python wordt ook ondersteund.

Ik denk dus dat je het probleem niet moet zoeken in de vermeende geschiktheid van de taal, maar in het simpele feit dat elke extra taal extra werk oplevert voor de organisatoren (ze moeten programma's immers server-side compileren en uitvoeren) en ze dus logischerwijs niet honderd verschillende talen kunnen aanbieden.

(Overigens is meedoen i.m.o. belangrijker dan winnen; waarschijnlijk zal het winnende programma wel in C, C++, Java of misschien Pascal geschreven zijn, maar dat betekend niet dat je geen zinnige inzending kunt doen in Python.)

Mijn entry is dan ook in Python Ik zit lekker te dubben over hoe ik die jokers ga gebruiken, moet thuis eens even gaan profilen, denk dat ik iets met algoritme herkenning ga doen van de ander en dan na de eerste zet de games ga uitrekenen zodat ik hem zo vroeg mogelijk kan inzetten.

Dat, of ik gebruik de Nim-strategieën. Twijfel twijfel, ach tijd zat

[ Voor 16% gewijzigd door Verwijderd op 13-08-2008 15:51 ]

[Sphere-]

Wat voor systeem wordt er gebruikt om te testen? (kan het niet terug vinden in de faq op de site).
Ik neem aan dat het een single core is.

[Ruudjah]

Q: Is there a limit for the size of my program source ?
A: Yes. Your program source file must not be larger than 1,474,560 bytes (the size of a floppy disk).

Plus het feit dat je geen .NET code mag submitten doet mij vermoeden dat het hier om een stel open-source hippies van 70 gaat (no pun intended). Jammer, is niets voor mij denk ik.

[Verwijderd]

Zeg Ruud,
Aan je regel:

code:

Ruud Ruudjah = new Ruudjah();

kan ik zien dat ik je commentaar niet serieus hoef te nemen
Vraag maar eens aan de beheerders van tweakers wat ze van .NET vinden.

Verder is de machine die de spelletjes afhandelt inderdaad een single core. Je zult in de testcompetities/door te submitten moeten uitvinden hoe je je programma moet afstellen qua rekentijd en geheugen.

[jmzeeman]

Hoe zit het met inline assembler en het gebruik van sse in C, is dat toegestaan?
@ruudjah

Plus het feit dat je geen .NET code mag submitten doet mij vermoeden dat het hier om een stel open-source hippies van 70 gaat (no pun intended). Jammer, is niets voor mij denk ik.

Hoe groot is de kans dat als je met AI bezig gaat je niet met allerlei OSS hippies zit . En doe niet zo moeilijk over de taal joh, een beetje programmeur kan de principes die die in de ene taal gebruikt in no time omzetten naar een andere taal. Zeker als je weinig gebruik hoeft te maken van de libraries lijkt het allemaal zo op elkaar. Je bent (als het goed is) vooral aan het rekenen en datastructuren aan het maken (alhoewel dat laatste wat meer van elkaar zal verschillen, zijn ook daar de verschillen miniem).

code:

i= x*y;
board[i,j]=1;

struct Move
{
  int x;
  int y;
  int width;
  int height;
}
move.x=1;

en dergelijken werken direct op het grootste deel van de talen en met wat kleine aanpassingen ook op andere talen.

[Verwijderd]

Ruudjah schreef op donderdag 14 augustus 2008 @ 13:26:
[...]

Plus het feit dat je geen .NET code mag submitten doet mij vermoeden dat het hier om een stel open-source hippies van 70 gaat (no pun intended). Jammer, is niets voor mij denk ik.

Nutteloze opmerking. 1.44 MB is zat, werkelijk zat, voor de implementatie voor wat algoritmes voor een Nim-variant.

[Verwijderd]

Over assembler wordt in de regels niet gesproken. We hebben in het verleden weleens mensen gehad die hun hele programma in assembler hebben gemaakt. Zolang je assemblercode werkt en door de test heen komt mag je het gewoon gebruiken!

[Hydra]

Verwijderd schreef op donderdag 14 augustus 2008 @ 17:28:
Vraag maar eens aan de beheerders van tweakers wat ze van .NET vinden.

Pardon?

[user109731]

Voor JavaScript zou je Mozilla Spidermonkey kunnen gebruiken. Ubuntu heeft een spidermonkey-bin package, ik weet niet of Debian deze ook heeft.

Met print() kun je data naar stdout schrijven, readline() leest een regel van stdin:

JavaScript:

function foo(x) {
  return x.toUpperCase();
}
print("Input:"); 
var line = readline();
print(foo(line));

Dat gebruik je dan zo:

$ js script.js
Input:
test
TEST

Willen jullie ook .Net ondersteunen dan zou je Mono kunnen overwegen...

Erg leuke contest verder, ik zal eens kijken of ik tijd heb om iets met Python of Haskell te doen...

[Creepy]

Hydra schreef op maandag 18 augustus 2008 @ 10:40:
[...]


Pardon?

Eeh ja... pardon? Wat heeft dat er nu weer mee te maken? Dat jullie geen .NET ondersteunen heeft niks met Tweakers.net te maken.

Ruudjah schreef op donderdag 14 augustus 2008 @ 13:26:
[...]

Plus het feit dat je geen .NET code mag submitten doet mij vermoeden dat het hier om een stel open-source hippies van 70 gaat (no pun intended). Jammer, is niets voor mij denk ik.

No offence, maar als het niks voor je is, blijf dan ook gewoon weg hier. Een beetje flamerig lopen doen is natuurlijk niet de bedoeling.

[ Voor 45% gewijzigd door Creepy op 18-08-2008 12:52 ]

[Verwijderd]

Spidermonkey kenden we nog niet, we gaan er even naar kijken!

[Woy]

Ik zou ook serieus overwegen om .NET te supporten met Mono, dat werkt ( zolang je niet te zwaar leunt op WinForms, maar dat is hiervoor ook totaal niet nodig ) zeer goed. Ik denk dat er een hoop Informatica studenten zijn die op dit moment les krijgen in .NET waarvoor dit een leuke competitie is.

[Soultaker]

De performance van Mono is wel dramatisch slecht vergeleken met recente Sun JVMs voor Java, en waarschijnlijk ook veel slechter dan Microsoft's implementatie onder Windows. Je kan natuurlijk zeggen dat dat risico voor de deelnemers is (wat ook geldt voor Python en Haskell) maar een volwaardige .NET omgeving is het dan toch niet echt.

[veldsla]

Soultaker schreef op dinsdag 19 augustus 2008 @ 17:04:
De performance van Mono is wel dramatisch slecht vergeleken met recente Sun JVMs voor Java, en waarschijnlijk ook veel slechter dan Microsoft's implementatie onder Windows.

Dat is niet echt wat ik de verschillende planets langs zie komen en de language shootout geeft dat beeld ook niet echt.

[Soultaker]

Hmm, ok, blijkbaar ben ik way out-of-date. Ik dacht dat Mono niet eens een JIT code generator had, maar blijkbaar was dat alleen helemaal in het begin zo.

[Haan]

Maargoed, als je een programma in .Net kan schrijven, kan je het met een beetje moeite ook wel in Java schrijven. Ik denk trouwens ook dat Java het meest wordt gebruikt bij programmeerlessen.

[Soultaker]

Op zich waar, al kan ik me voorstellen dat als je gewend bent te ontwikkelen in Visual Studio (Express) met geïntegreerde debugger, code highlighting en allerlei andere toeters en bellen, het nogal een verschil is als je over moet schakelen op Java (hoewel je met Eclipse ook wel een aardige ontwikkelomgeving hebt).

Overigens is mijn ervaring bij dit soort wedstrijden dat je 10x zoveel code schrijft als je uiteindelijk inlevert, om allerlei strategiën en algoritmes uit te proberen. Die kun je natuurlijk schrijven in welke taal je maar wilt, zolang het uiteindelijke programma geschreven wordt in een supported taal. (Maar dan nog zit je met het probleem dat je je uiteindelijke inzending wel wil kunnen debuggen).

Om een lang verhaal kort te maken: ik betwijfel niet dat de geboden talen meer dan voldoende zijn om iedereen mee te kunnen laten doen, maar ik denk wel dat de drempel lager zou zijn als .NET talen ook ondersteund worden.

[Woy]

Soultaker schreef op dinsdag 19 augustus 2008 @ 17:51:
Om een lang verhaal kort te maken: ik betwijfel niet dat de geboden talen meer dan voldoende zijn om iedereen mee te kunnen laten doen, maar ik denk wel dat de drempel lager zou zijn als .NET talen ook ondersteund worden.

Dat is inderdaad mijn punt. Mij haalt het persoonlijk niet uit aangezien ik meerdere van de ondersteunde talen ken, en ik waarschijnlijk toch uberhaupt niet mee doe.

Maar zeker voor studenten Informatica kan het leuk zijn om mee te doen, en dan kan het toch een drempel zijn, aangezien er volgens mij wel een aantal scholen zijn die tegenwoordig in .NET ipv Java of een andere taal les geven.

Bovendien hoeft het niet zo veel moeite te kosten om een Mono omgeving op te zetten.

[ Voor 5% gewijzigd door Woy op 19-08-2008 17:59 ]

[Verwijderd]

rwb schreef op dinsdag 19 augustus 2008 @ 17:58:
[...]
Maar zeker voor studenten Informatica kan het leuk zijn om mee te doen, en dan kan het toch een drempel zijn, aangezien er volgens mij wel een aantal scholen zijn die tegenwoordig in .NET ipv Java of een andere taal les geven.

Wij op de Fontys Informatica krijgen in het 1e jaar alleen maar C# (.NET), en in het 2e jaar pas Java.

Hoe dat zit bij andere scholen weet ik dus niet, maar .NET lijkt wel aan populariteit te winnen in het onderwijs .

[RayNbow]

Verwijderd schreef op woensdag 13 augustus 2008 @ 15:25:
We hebben hier goed zitten zoeken naar javascript interpreters op linux machines, maar we kunnen echt niets vinden. Mochten we het over het hoofd hebben gezien, dan worden we daar natuurlijk graag op gewezen.

Rhino?

[Verwijderd]

Rhino is onder debian geen package in de huidige stable. Verder weet ik niet of rhino een stdin/stdout heeft... Voor zover ik weet is rhino een scripting engine die je kan embedden in je eigen applicatie (bijv firefox, maar ook de java 6 scripting api).
Ik zie wel dat ze ook een scripting shell hebben, maar voor ons is het criterium dat het in debian stable moet draaien.

[RayNbow]

Hmm, stdout heeft het wel... maar in tegenstelling tot Spidermonkey mist Rhino de functie readline().

addendum: wat eig. jammer is, gezien Rhino gemakkelijk te installeren is.

[ Voor 31% gewijzigd door RayNbow op 19-08-2008 22:02 ]

[Verwijderd]

Ik ben even vergeten kenbaar te maken dat het implementeren van de nieuwe regels voor wat betreft een crashende tegenstander al is gedaan (ik had per ongeluk de credits aan Cheatah gegeven op de codecup website, foutje is hersteld;)). De caia versie die online staat bevat deze nieuwe regel.

Ook is het submitten i.t.t. de berichten op de homepage al in werking gesteld. Dit komt doordat een deel van onze organisatie reclame aan het maken is op de IOI in Egypte, we willen de eventuele deelnemers daar de kans geven om hun eerste versie in te sturen. Als het heel hard loopt zullen we misschien sneller een testcompetitie houden.

Voor wat betreft de talen, we gaan dit jaar geen extra talen meer toevoegen. Voor volgend jaar gaan we kijken naar Mono, maar we beloven vooralsnog niets. Ben je ervan overtuigd dat wij perse een taal moeten toevoegen, open dan een thread op ons forum (engelstalig).

[Dricus]

* klein schopje *

Ik heb de strategie voor m'n AI al aardig uitgedacht, vooral het gedeelte aan het einde van het spel. Alleen loop ik wel te dubben over hoe ik de AI ga opzetten. 5 seconden over een heel potje is weinig tijd, dus het moet flink efficiënt zijn. Optimized bruteforce-achtige zaken zoals minmax vallen dan wel een beetje af lijke me.

Ook loop ik nog een beetje te zoeken naar een handige manier om m'n game logica op te zetten, voornamelijk als het gaat om het bepalen van de mogelijke zetten.

Kortom: nog geen regel code geschreven, maar wel druk aan het brainstormen .

Hoe staat het met de andere deelnemers?

[ Voor 3% gewijzigd door Dricus op 26-08-2008 10:43 ]

[Face_-_LeSS]

Ik heb mezelf er ook even over gebogen. In de eerste instantie leek het me niet extreem moeilijk en vond het de moeite waard om er een poging aan te wagen. Nu ik er over nagedacht heb vind ik het toch een vrij pitigge uitdaging. Wat betreft de AI zit ik nog druk na te denken en informatie in te winnen over NIM en andere wiskundige berekeningen.

[jmzeeman]

Ben ook lekker bezig, ik heb zelfs al redelijk wat code . Ik ben begonnen met de code die de het spel en de statistieken rond het spel bijhoud. Ik denk dat wat meer van te voren uit geprogrammeerde strategieen meer kans maken als 'echte' AI algoritmen(die zelf een strategie bedenken) gezien de gelimiteerde tijd. Zelf denk ik aan een gemixte variant die 'dom' begint en geleidelijk slimmer wordt. Aan de andere kant valt het aantal zetten nog wel mee dus zou een (eventueel wat gepimpte) minimax variant nog best kunnen in de toegestane tijd.
Op het moment ben ik nog druk bezig om de mogelijke zetten op een snelle en slimme manier te bepalen en (gedeeltelijk) bij te houden. Zelf denk ik eraan om dit zo te doen dat ik alle mogelijke zetten bij hou en na elke zet zal ik de beinvloede zetten verwijderen zodat ik niet elke keer opniew alles moet bedenken.
volgens mijn proefondervindelijk bedachte/geteste formule kunnen er in het slechtste geval (als alle pillars een muur aan een zeide vormen) maximaal het volgende aantal zetten mogelijk zijn:
een open gebied van 9x10 =
(9+8+7+6+5+4+3+2+1)*(10+9+8+7+6+5+4+3+2+1)=2475
iemand die hier de wiskundige kennis heeft om deze formule te bevestigen/te ontkrachten? Is er eigenlijk een notatie/naam voor faculteit met + in plaats van x (naast de sigma notatie)?
Volgens mij is dit een redelijke hoeveelheid om nog bij te houden.

[roy-t]

je noteert het normaal

9!*10!

Als ik het goed heb heet dat faculteit maar voor de hele formule weet ik zo geen naam.

[ Voor 25% gewijzigd door roy-t op 26-08-2008 14:07 ]

[Soultaker]

MrHuge schreef op dinsdag 26 augustus 2008 @ 10:43:
Alleen loop ik wel te dubben over hoe ik de AI ga opzetten. 5 seconden over een heel potje is weinig tijd, dus het moet flink efficiënt zijn. Optimized bruteforce-achtige zaken zoals minmax vallen dan wel een beetje af lijke me.

Ik denk dat de korte tijd (op een vrij snel systeem ) wel in balans is met de kleine hoeveelheid geheugen die je ook hebt. Ik hoop dat door de korte executietijd dit jaar een volledige competitie mogelijk is.

Kortom: nog geen regel code geschreven, maar wel druk aan het brainstormen .
Hoe staat het met de andere deelnemers?

Ik heb wel een aardige aanpak momenteel. Ik kan met de hand i.i.g. niet winnen, of ik moet een half uur per zet uittrekken.

[Dricus]

jmzeeman schreef op dinsdag 26 augustus 2008 @ 13:39:
volgens mijn proefondervindelijk bedachte/geteste formule kunnen er in het slechtste geval (als alle pillars een muur aan een zeide vormen) maximaal het volgende aantal zetten mogelijk zijn:
een open gebied van 9x10 =
(9+8+7+6+5+4+3+2+1)*(10+9+8+7+6+5+4+3+2+1)=2475
iemand die hier de wiskundige kennis heeft om deze formule te bevestigen/te ontkrachten? Is er eigenlijk een notatie/naam voor faculteit met + in plaats van x (naast de sigma notatie)?
Volgens mij is dit een redelijke hoeveelheid om nog bij te houden.

Faculteit is hier niet van toepassing. Faculteit is het product van alle natuurlijke getallen 1..n, niet de som! Voor de som is dacht ik ook een term, maar daar kom ik zo ff niet op.

Edit: Je berekening klopt volgens mijn berekeningen wel trouwens .

[ Voor 64% gewijzigd door Dricus op 26-08-2008 14:21 . Reden: Kleine toevoeging + quote toegevoegd ]

[Soultaker]

Maar de pillars kunnen niet allemaal aan de rand staan, want er staat er één in elke rij en één in elke kolom. Geen idee wat het antwoord dan wel is, maar ik gok dat de worst case is dat de pillars op een diagonaal staan.

[ Voor 34% gewijzigd door Soultaker op 26-08-2008 15:19 ]

[Vaan Banaan]

Leuk project, misschien dat ik er aan mee ga doen. Maar om het voor mezelf duidelijk te krijgen:
Klopt het dat, zoals in de faq staat, je dus niet kan rekenen terwijl de ander bezig is?

Q: Can my program continue its calculations during the opponent's turn ?
A: No, it is not possible to continue your calculations in the turn of your opponent (thinking in the time of your opponent). While your opponent is thinking, your program is temporarily suspended.

En verder zag ik nog in de rules:

Runtime environment
Computer:	Pentium IV, 2.8 Ghz
Memory:	1 GB, your program can use 64 MB
Operating system:	Linux 2.6 (Debian 4.0)
Time limit:	5 seconds per game

Moet je die RAM zelf bijhouden, of wordt dat door de manager geregeld?

[Soultaker]

Uit ervaring kan ik je laten weten dat als je die grens overschrijft, je proces vanzelf afgeschoten wordt. Overigens is het voor Java vermoedelijk de heap size, niet de totale hoeveelheid gereserveerd geheugen, anders zou je de VM niet eens op kunnen starten.

[jmzeeman]

Maar de pillars kunnen niet allemaal aan de rand staan, want er staat er één in elke rij en één in elke kolom. Geen idee wat het antwoord dan wel is, maar ik gok dat de worst case is dat de pillars op een diagonaal staan.

In dat geval is de berekening wat lastiger, ik ben het met je eens dat het worst case scenario dan diagonaal is. Daarvan uitgaande is mijn berekening nu :
2*(
1*(9+8+7+6+5+4+3+2+1)+
2*(8+7+6+5+4+3+2+1)+
3*(7+6+5+4+3+2+1)+
4*(6+5+4+3+2+1)+
5*(5+4+3+2+1)+
6*(4+3+2+1)+
7*(3+2+1)+
8*(2+1)+
9*(1)
)
=
2*(1*45+2*36+3*28+4*21+5*15+6*10+7*6+8*3+9*1)
=990

met sigma notatie:( als ik me dat nog goed heb herrinnerd van school klopt t zo )


Aangezien we allemaal programeurs zijn zal ik de berekening hier ook even in code schrijven.
voor een vlak met hoogte n is het maximaal aantal zetten z:

code:

int z=0;
int n=10;
for(int i=1;i<=(n-1);i++)
{
    int a=0;
    for(int j=1;j<=(n-i);j++)
    {
        a=a+j;
    }
    z=z+i*a;
}
z=z*2;

Edit: Dit is meteen een hint over hoe ik de zetten bereken: steeds van uit elk vlak naar rechts en naar boven zoeken.

[ Voor 5% gewijzigd door jmzeeman op 26-08-2008 17:31 ]

[Verwijderd]

Diagonaal is niet worst case. Ik ben ondertussen zover dat ik alle zetten kan genereren met mijn programma, en op het volgende bord zijn 1090 zetten mogelijk. Op een bord met alleen stenen diagonaal zijn idd 990 zetten mogelijk. Het zou kunnen dat er nog wel meer zetten mogelijk zijn, maar die mogelijkheden heb ik nog niet gevonden. (Het kan natuurlijk dat er nog een bug in mijn programma zit, maar alle kleine testcases die ik heb getest kloppen, en ook de 990 voor een diagonale rij stenen komt overeen met wat jmzeeman uitrekende.)

code:

-----X----
------X---
-------X--
--------X-
---------X
X---------
-X--------
--X-------
---X------
----X-----

[Soultaker]

Klopt, dat blijkt de worst case te zijn met 1090 zetten, zoals te verwachten was met een zo groot mogelijk open deel. Leuk detail om over na te denken: die beginstelling is bovendien winnend voor de eerste speler.

[Verwijderd]

Hoe ben je er zeker van dat die stelling winnend is voor de eerste speler?

[Soultaker]

Omdat ik een winnende strategie voor de eerste speler bedacht heb.

[jmzeeman]

Ik begon gister nacht (ben hier niet meer geweest na m'n post) al te twijfelen toen ik in mijn random gegenereerde pillars meer dan 990 zetten vond. Ben maar gaan slapen omdat ik niet meer wist of het nou aan m'n algoritme of m'n berekening lag(ik was ook zo dom om de pillar verdeling niet te loggen). Gelukkig, zie ik nu, was m'n berekening fout (achteraf logisch). Maakt verder weinig uit het blijft een redelijk klein aantal zetten om bij te houden. Voor een onaangepaste minimax is het echter nog best veel, die loopt snel stuk denk ik, met richting een miljoen (geen zin om de exacte hoeveelheid uit te rekenen) opties voor de eerste beurt(AI+tegenstander). Wat nog wel interresant zou zijn om te weten is wat het gemiddelde aantal mogelijke zetten in de eerste beurt is(ik schat dat dit veel lager ligt als 1090). Dit zou kunnen helpen om de AI te optimaliseren voor dit soort hoeveelheden zetten. Met de 10!=3628800 mogelijke start situaties denk ik dat ik m'n pc maar gewoon een tijdje laat rekenen aangezien mijn wiskundige benaderingen tot nu toe niet 100% accuraat bleken .

[Jewest]

roy-t schreef op dinsdag 26 augustus 2008 @ 14:07:
je noteert het normaal

9!*10!

Als ik het goed heb heet dat faculteit maar voor de hele formule weet ik zo geen naam.

Sorry maar het is geen faculteit..
Wikipedia: Faculteit (wiskunde)

[Dricus]

Als ik überhaupt al minmax (met alpha-beta pruning, wellicht een transposition table, etc) ga gebruiken, dan ga ik dat pas doen als het aantal mogelijke zetten onder een bepaalde grens zit. Wat die grens dan moet zijn zal een performance-test moeten gaan uitwijzen.

Momenteel zit ik echter een hele andere kant uit te denken, dus minmax zal er voorlopig nog niet aan te pas gaan komen .

[Soultaker]

jmzeeman schreef op woensdag 27 augustus 2008 @ 10:33:
Maakt verder weinig uit het blijft een redelijk klein aantal zetten om bij te houden.

Klopt, gaat meer om de orde van grote, maar het maximum is ook wel aardig als je b.v. statisch arrays wil alloceren.

Wat nog wel interresant zou zijn om te weten is wat het gemiddelde aantal mogelijke zetten in de eerste beurt is(ik schat dat dit veel lager ligt dan 1090).

Ik kom op ongeveer 826 zetten gemiddeld (173483/210 exact); dat is dus niet echt veel minder.

Het minimum is trouwens 715 zetten, voor deze stelling:

  abcdefghij
A #.........
B ....#.....
C ......#...
D ..#.......
E ........#.
F .....#....
G .#........
H .......#..
I ...#......
J .........#

[jmzeeman]

maar het maximum is ook wel aardig als je b.v. statisch arrays wil alloceren.

Inderdaad, dat was mijn eerste reden om opzoek te gaan naar het maximum (als embedded programeur heb ik een natuurlijke afkeer van malloc ).

[De Cowboy]

Hoeveel mensen hier hebben nu daadwerkelijk een inzending? Er zijn in ieder geval heel wat nederlanders, maar helaas toch tamelijk veel complete random spelers.

De test competitie vandaag pakte wel mooi uit voor mij, met een 2e plek Heel veel tijd zit er nog niet in maar veel strategie eigenlijk ook niet. Ik heb een beetje onderzoek gedaan naar nim en varianten, maar de organisatie verwacht denk ik toch dat er geen 'oplossing' voor het spel gevonden zal worden.

[Soultaker]

Mijn inzending is toch al wel behoorlijk serieus. Ik heb er dan ook de eerste twee testcompetities mee gewonnen. Deze keer was het slechts een vierde plek waard, wat betekent dat minstens drie andere mensen toch een behoorlijk goed programma hebben ingezonden. Ook al zeg je zelf dat er weinig tijd/strategie in zit, blijkbaar doe je toch wel iets goed.

Sowieso zaten er alleen serieuze spelers in de top 12. Dat er verder nog een aantal mensen met test/random-programma's spelen, verbaast me niet echt; de finale is ook pas in januari, en zelfs dan zullen er wel een aantal spelers afgehaakt zijn.

[Verwijderd]

Elk jaar hebben we inderdaad een hoop mensen die een (random) versie maken en het daar verder bij laten. Ik heb zelf ook alleen een random speler. Daarom spelen we een aantal ronden volgens het zwitserse systeem. Dit selecteert de "beste" 12 (16 in de finale tenzij we boven de 80 deelnemers uitkomen) spelers. Ik zeg ""beste"" omdat je natuurlijk nooit zeker weet dat de nummer 12 uit de voorrondes echt beter presteert dan de nummer 13 uit de voorrondes. Er zit een kleine factor geluk in. We zijn er wel van overtuigd dat de "echte" top 8 binnen de geselecteerde spelers vallen. De volledige competitie is in onze ogen de enige manier om uit te maken daadwerkelijk de besten zijn.
Een van de deelnemers van vorig jaar claimde een beter algoritme te hebben, maar hij kon ons, ondanks zijn goede uitwerking, niet overtuigen.

[Verwijderd]

Ik heb in de competitie van afgelopen weekeinde ook maar weer een nieuw programma ingeleverd. Ik heb een aantal weken niks gedaan, maar ik had een paar nieuwe ideeen en wilde deze proberen. Wat me wel opvalt is dat over grote deel van de mensen die bij de top 14 horen zijn C of C++ programma's. Slechts mijn Java programma en een ander python programma. Betekent dit dat er weinig niet C/C++ programeurs zijn die een goed idee hebben uitgewerkt? of dat het toch belangrijk is om snel moves uit te rekenen en dat C/C++ daarom een voordeel heeft. Aangezien ik geen C/C++ (niet goed iig) kan ga ik toch proberen om de top te halen met Java Hopelijk komen er meer niet-C/C++ programeurs bij de top om de balans een beetje beter te maken . Ik ben 11de geworden deze keer, maar heb nog genoeg ideeen voor een volgende competitie.