Keskustelu: Ohjelmointiputka: Pomppis-kilpailu alkaa!

Tänään alkaa Ohjelmointiputkan tekoälykilpailu:

https://www.ohjelmointiputka.net/kilpa.php?tunnus=pomppis

Aiheena on kahden pelattava lautapeli nimeltä Pomppis. Pelaajat aloittavat laudan vastakkaisilta reunoilta, ja tavoitteena on kuljettaa kaikki omat pelinappulat laudan halki. Nappulaa saa yhdellä vuorolla siirtää joko yhden askeleen tai mieleisensä mittaisen hyppysarjan, jossa jokainen hyppy vie yhden muun nappulan yli. Voittaja on se, joka saa ensin kaikki nappulansa toiselle puolelle. Kaikki tekoälyt pelaavat toisiaan vastaan, ja koko kilpailun voittaa se, joka voittaa eniten yksittäisiä pelejä.

Viimeinen osallistumispäivä on sunnuntai 17.1., mutta aiemminkin saa ilmoittautua. Kilpailusta voi kysellä ja keskustella tässä aiheessa. Tervetuloa mukaan!

Nyt täytyy heti heittää kiitosta että on saatu mielenkiintoinen peli ja hyvät testiympäristöt aikaiseksi.

Pitääpi alkaa suunnittelemaan tekoälyä...

Kertoisiko joku miten tuo C++ tai C esimerkki saa tietonsa komentorivillä.

Tutkihan noita esimerkkejä. Kirjastosta iostream löytyy oliot cin ja cout std-nimiavaruuden sisältä. Oliota cin voit käyttää tiedon lukemiseen ja oliota cout tulostukseen.

On kyllä mielenkiintoinen peli ja heti tuli rutkasti ideoita mieleen.
Kysyisin vaan, kun tuolla rajoituksissa sanottiin, että ohjelma saa käyttää kokonaisuudessaan 60 sekuntia aikaa, tarkoitettiinko sillä, että koko kisan aikana vai vain yhden siirron miettimiseen?

Anaatti kirjoitti:

On kyllä mielenkiintoinen peli ja heti tuli rutkasti ideoita mieleen.
Kysyisin vaan, kun tuolla rajoituksissa sanottiin, että ohjelma saa käyttää kokonaisuudessaan 60 sekuntia aikaa, tarkoitettiinko sillä, että koko kisan aikana vai vain yhden siirron miettimiseen?

Yhteen siirtoon se olisi ainenkin melko rutkasti... >:D

Niin jos yhtä pelia kohden tehdään noin 250 - 300 siirtoa ja pelejä pelataan vaikkapa 12 kpl. 12 * 300 * 60 / 3600 = 60 tuntia :)

Minuutin aikaraja koskee yhtä kahden tekoälyn välistä peliä. Siinä kummallakin tekoälyllä on minuutti aikaa kaikkien siirtojensa laskemiseen.

No joo. Lähinnä ajattelin vaan sitä, että koska kokonaisen pelin siirtojen määrää ei voi ennalta tietää, on eri peleissä eri määrä aikaa käytettävissä yksittäiseen siirtoon. Jos vaikka laittaa tuon esimerkkiohjelman kilpailemaan itseään vastaan, niin siirtoja kertyy kyllä aika paljon yhden pelin aikana ja saattaa ajan loppuminenkin olla jo aika lähellä.

Onko tuo minuutti prosessoriaikaa vai aikaa tehdä siirrot? Otatko sen prosessoriajan jotenkin järjestelmältä vai teetkö tähän tyyliin:
1. Kerro vastustajan siirrot
2. Kello käyntiin
3. Odota vastausta
4. Kello seis

Itse kannatan sellaista ratkaisua, että aikaa olisi alussa vaikka 10s ja sitten saisi aikaa aina siirron tehtyään vaikka 250 millisekunttia lisää.

Kuten säännöissä sanotaan, "kilpailussa mitataan ohjelman itse käyttämää aikaa", toisin sanoen prosessoriaikaa, joka saadaan suoraan järjestelmältä. Esimerkiksi Linuxissa ohjelman aikarajan voi asettaa ulimit-komennolla.

Minusta aikarajaa ei ole syytä muuttaa: aiemmissakin kilpailuissa suunnilleen vastaava aika siirtoa kohden riitti aivan hyvin, ja kiinteä rajoitus on kaikkien kannalta selkeämpi. Esimerkkiohjelma pelaa erittäin huonosti, ja silti peli kestää alle 250 kierrosta; hieman järkevämmän tekoälyn pitäisi päästä arviolta puoleen tästä määrästä. Mitä parempi tekoäly on, sitä enemmän aikaa sillä on kunkin siirron miettimiseen. Tiukka aikaraja myös rohkaisee keksimään strategisempia ratkaisuja kuin kaikkien vaihtoehtojen tutkiminen.

Jokotai kirjoitti:

Kertoisiko joku miten tuo C++ tai C esimerkki saa tietonsa komentorivillä.

Jos tarkoitat kilpailun teknistä toteutusta, niin esimerkiksi tuo valmis testausohjelma käynnistää tekoälyn Javalla, jolloin ohjelman standardivirrat ovatkin suoraan Java-ohjelman luettavissa ja kirjoitettavissa. Kilpailijan ei kuitenkaan tarvitse tästä välittää, kunhan vain tulostaa tekstiä aivan normaalisti.

Mieltä lämmittää erityisesti Infernon Limbon löytyminen kilpailun sallittujen ohjelmointikielien listasta ja löytyipä esimerkkiohjelmista vielä Limbo toteutuskin.

Jos vaan saan jostain raavittua tarpeeksi vapaa-aikaa, niin yritän itse saada jonkunlaisen toteutuksen kasaan.

Päivällä sain alustavan idean rinnakkaismalliseen (concurrent) toteutukseen:

Jokainen pelilaudan pelinappula toimii omassa säikeessään. Säikeitä varten on monitori, mikä varmistaa, että säikeet saavat samanverran prosessoriaikaa. Edellä mainittu on toteutettu token-ring tyyliin. Pelinappula tekee siirron, kun se saa tokenin. Varsinainen työ, eli mahdollisten siirtojen laskeminen tapahtuu kuitenkin silloin, kun pelinappulalla ei ole tokenia. Jos pelitilanne pelilaudalla on muuttunut siten, että ennalta laskettu siirto ei ole mahdollinen, siirtää pelinappula tokenin, eli vuoron seuraavalle omalle pelinappulalle.

Mielestäni pelien maksimipituutta olisi syytä rajoittaa. Mikäli näin ei tehdä, voidaan joutua tilanteisiin, joissa toinen osapuoli lukittaa vastustajan pelin niin, ettei ole mahdollista saada kaikkia kiviä pois laudalta. Tällaisessa tilanteessa loppupeli olisi vain mahdollisimman nopeaa siirtojen väliinjättämistä, mikä ei liene kisan tarkoitus.

Lisäksi voisi olla hyvä asia jos molempien passatessa peli päättyisi (esimerkiksi tasapeliin), mutta ymmärrän myös jos peliin on tarkoituksella jätetty tämä ominaisuus. Mikäli pelin ei haluta loppuvan jos molemmat passaavat, olisi kuitenkin syytä määritellä, montako siirtoa peli maksimissaan kestää. Vaihtoehtoisesti voitaisiin antaa edes molempien pelaajien aikatilanteet, jotta pikapelioptimointi onnistuu paremmin ;).

Laitinen kirjoitti:

Mielestäni pelien maksimipituutta olisi syytä rajoittaa. Mikäli näin ei tehdä, voidaan joutua tilanteisiin, joissa toinen osapuoli lukittaa vastustajan pelin niin, ettei ole mahdollista saada kaikkia kiviä pois laudalta.

Ei voida joutua. Fiksu äly pääsee aina esteen ohi.

Valitettavasti Laitinen on aivan oikeassa, kiitokset huomiosta. Tapoja on kaksi: 8 nappulaa vastustajan yhden nappulan ympärille (tuskin onnistuu) tai leveä muuri (tai edes yksi fiksusti liikkuva nappula) vastustajan maaliriville. Näistä muuri on varmasti helpoin toteuttaa.

Lisäys sääntöihin: jos peli ei pääty aiemmin, 1000 pelikierroksen eli yhteensä 2000 vuoron jälkeen lähempänä maalia oleva pelaaja voittaa.

Molempien passaaminen on sikäli epäolennainen seikka, että käytännössä aina voisi sen sijaan liikkua maalia kohti.

Onko pelaajan etäisyys maaliin määritelty pelaajan nappuloiden etäisyyksien summana?

Kiva sääntölisäys.

Tuntien työ meni hukkaan kun bottini ei enää pärjäisikään :|

Grandi kirjoitti:

Tuntien työ meni hukkaan kun bottini ei enää pärjäisikään :|

Aika sama täällä :/ (tosin ihan tuntien työstä ei voida puhua; botti vain teki joukon vakiosiirtoja ja siirtyi passaamiseen). Itse ehdin jo lähettääkin voittamatonta muuritaktiikkaa käyttävän bottini, mutta tämä muutos vaikeuttaa kilpailun trollausta ikävästi.

Sisuaski kirjoitti:

Onko pelaajan etäisyys maaliin määritelty pelaajan nappuloiden etäisyyksien summana?

Kyllä, juuri näin, eli rivillä 15 oleva nappula on vain yhden askeleen päässä ja ensimmäisellä oleva taas 15 askelen päässä maalista.

Grandi ja Sisuaski (ja muut lurjukset): Jottei enempää ikäviä yllätyksiä tulisi, varoitan jo etukäteen, että mikäli vastaavia "voittamattomia" porsaanreikiä vielä löytyy, nekin kielletään. :)

Uskon, että kilpailusta on eniten iloa, kun jokainen pyrkii voittamaan rehellisin keinoin eli saamalla kaikki nappulansa maaliin. Säännöissäkin sanotaan, että tämä on pelin tarkoitus.

Metabolix kirjoitti:

Valitettavasti Laitinen on aivan oikeassa.

Totta, olin väärässä; estäminen onnistuu tarpeeksi tehokkaasti. Yksinäinen blokkaaja maalirivillä riittää, koska maalirivin yli ei saa hypätä laudan ulkopuolelle.

Joka tapauksessa kiitokset järjestämisestä, eiköhän tästä tule hyvä kisa.

Muoks: ajatusvirhe, poistin osan

Miksiköhän en onnistunut laittamaan edes esimerkkiohjelmaa kilpailemaan tuossa testaussivulla? Ilmoittaa virheeksi: "java.io.IOException: error=13, Lupa evätty". Mikä avuksi?

Jätitkö ehkä sertifikaatin hyväksymättä? Java vaatii erikseen oikeudet ulkoisten ohjelmien ajamiseen.

Tuo kysyy itseltäni vain, että halutaanko java-sovelma suorittaa. Onko se sitten tuo sertifikaattikysely, sitä en tiedä. Käytössä Firefox ja Ubuntu 9.10.

Mitä testiohjelmaa yrität ajaa? Käynnistyykö ohjelma yrittämälläsi komennolla komentoriviltä? (Oletko tarvittaessa kääntänyt ohjelman? Onko ohjelmalla suoritusoikeus (chmod +x esim.py)?)

Huomasin että kuvassa pomppis.php?2812 on päiviäjäljellälaskuri:)

Minulla herjaa tuossa Pomppis-testausohjelmassa nyt: "Tuki Javalle tai LiveConnect-tekniikalle puuttuu, tai et hyväksynyt sertifikaattia.". Toimi täysin vielä eilen ja aikaisemmin päivällä.

Edit: Valittaa myös jostain komentosarjaongelmista.

Testausohjelma ei ole muuttunut 26.12. jälkeen.

Onko muilla ollut vastaavia ongelmia?

Minulla ohjelma toimii aivan entiseen tapaan. Voit varmuuden vuoksi tyhjentää sekä selaimen että Javan välimuistin. Jälkimmäisen saa tyhjennettyä Java-konsolissa näppäimellä x.

Minulla on aivan sama ongelma. Välimuistien tyhjentäminen ei auttanut.

Mikä käyttöjärjestelmä, selain ja Javan versio mahtaa olla kyseessä?

Tiedoston pomppis.jar voi myös ladata ja ajaa komentoriviltä. Tällöin peliä ei tosin näytetä graafisesti, vaan ohjelma vain tulostaa siirrot ensimmäisen pelaajan näkökulmasta. Ohjelmalle annetaan parametreiksi tekoälyjen ajamiseen käytettävät komennot, esimerkiksi näin:
java -jar pomppis.jar "python pomppis-esim/esim.py" "./pomppis-cpp.bin"

Pahoittelut. Ongelmalla ei ollutkaan mitään tekemistä testausohjelman kanssa.

Grandi: kannattaa katsoa, toimiiko mikään Java-appletti selaimessa. Ainakaan jos käytät Debian squeezeä, niin luultavasti ei. Jälkimmäisessä linkissä omalla kohdallani toiminut ratkaisu ongelmaan.

http://bugs.debian.org/cgi-bin/bugreport.cgi?bug=561693
http://bugs.debian.org/cgi-bin/bugreport.cgi?bug=560044

Nyt minullakin toimii ihan hyvin. Voi olla, että oma tekoälyni vain kaatui ja sai aikaan testausohjelman kaatumisen tai jotain.

Edit: Käytän Windows 7 (64 bit) ja Java appletit ovat pelanneet kuten kuuluukin.

Ihan vain mielenkiinnosta...

Kuinka moni päätyi tekemään useampi säikeisen toteutuksen? Etunahan tuossa säikeiden käytössä tietysti on, että ohjelma pystyy tutkimaan siirtomahdollisuuksia odotellessa vastustajan siirtoa.

Oma toteutukseni käyttää omaa säiettä (Infernon proc) jokaiselle pelilaudan omalle nappulalle. Monitori säie pitää huolen, että jokainen nappula saa saman verran prosessoriaikaa. Tämä tapahtuu siten, että jokainen nappula yrittää siirtää vuorollaan, eikä voi yrittää tehdä uutta siirtoa ennenkuin kaikki muut nappulat ovat yrittäneet vuorollaan tehdä siirron. Nappula voi toki yrittää laskea seuraavaa siirtoaan ennen kuin se saa vuoronsa. Monitori varmistaa, että jos mikään nappula ei pysty toteuttamaan siirtoaan vuorollaan, niin jättää se pelivuoron väliin ja siirtää sen vastustajalle.

Taidanpa osallistua tähän. Tosin en osaa/jaksa tehdä mitään hienosti optimoitua älyä, joten teen vain jonkun pilipalitekoälyn pythonilla ;)

jalski kirjoitti:

Kuinka moni päätyi tekemään useampi säikeisen toteutuksen? Etunahan tuossa säikeiden käytössä tietysti on, että ohjelma pystyy tutkimaan siirtomahdollisuuksia odotellessa vastustajan siirtoa.

Ja mikä se etu sitten siinä on, että voit tutkia siirtomahdollisuuksia vastustajan siirron aikana? Käytössäsi on kuitenkin tasan 60 sekuntia prosessoriaikaa, käytit sen sitten miten ja milloin tahansa. Lisäksi miksei tätä samaa voisi tehdä ilman säikeitäkin?

Sami kirjoitti:

Ja mikä se etu sitten siinä on, että voit tutkia siirtomahdollisuuksia vastustajan siirron aikana? Käytössäsi on kuitenkin tasan 60 sekuntia prosessoriaikaa, käytit sen sitten miten ja milloin tahansa. Lisäksi miksei tätä samaa voisi tehdä ilman säikeitäkin?

Omassa toteutuksessani, jos nappulat ja niiden vuorot järjestelee fiksusti laudalla, niin suurin osa niistä pystyy aluksi tekemään siirtonsa välittömästi, kun oma vuoro tulee. Luulen, että tuo 60 sekunttia riittää kyllä aika monen siirron tekemiseen.

Eiköhän ilman säikeiden käyttöä ohjelman suoritus blokkaa pelisilmukassa vastustajan siirron lukemiseen, kun odotat vastustajan siirtoa.

jalski kirjoitti:

Omassa toteutuksessani, jos nappulat ja niiden vuorot järjestelee fiksusti laudalla, niin suurin osa niistä pystyy aluksi tekemään siirtonsa välittömästi, kun oma vuoro tulee. Luulen, että tuo 60 sekunttia riittää kyllä aika monen siirron tekemiseen.

Ei se anna sinulle yhtään lisäaikaa, vaikka laskisitkin vastustajan vuorolla. Käytössäsi on 60 sekuntia prosessoriaikaa, joka kuluu vaikka käyttäisitkin sitä vastustajan vuoron aikana.

jalski kirjoitti:

Eiköhän ilman säikeiden käyttöä ohjelman suoritus blokkaa pelisilmukassa vastustajan siirron lukemiseen, kun odotat vastustajan siirtoa.

Miksi blokkaisi? Voithan vähän väliä tarkistaa onko siellä mitään luettavaa ja jos ei ole, niin älä yritäkään vielä lukea sieltä mitään vaan tee jotain muuta sillä välin.

Osallistujalle usean säikeen käytöstä ei ole hyötyä, koska kaikki ohjelman kuluttama prosessoriaika lasketaan. Lisäksi täytyy muistaa säännöissä mainittu vaatimus deterministisyydestä!

Kokonaiskilpailu voi kuitenkin nopeutua, jos prosessorin molemmat ytimet ovat tehokkaasti käytössä. ;)

Metabolix kirjoitti:

Osallistujalle usean säikeen käytöstä ei ole hyötyä, koska kaikki ohjelman kuluttama prosessoriaika lasketaan. Lisäksi täytyy muistaa säännöissä mainittu vaatimus deterministisyydestä!

Motiivina säikeiden käytölle ei välttämättä tarvitse olla ohjelmasta nopeamman saaminen. Itse monesti tykkään vain jakaa ongelman pienempiin yksinkertaisiin kokonaisuuksiin.

Alla esimerkki, miten toteuttaa Infernolla proc monitori ja miten jakaa työläissäikelle prosessoriaikaa tasapuolisesti:

implement Proctest;

include "sys.m";
   sys : Sys;

include "draw.m";


Proctest : module
{
   init : fn(nil : ref Draw->Context, nil : list of string);
};




init(nil : ref Draw->Context, nil : list of string)
{
   sys = load Sys Sys->PATH;

   spawn monitor(10);

}



monitor(numprocs : int)
{
   if(numprocs < 1)
   {
      sys->print("No procs! Nothing to do.\n");
      exit;
   }

   proca := array [numprocs] of chan of int;

   for(i := 0; i < numprocs; i++)
   {
      proca[i] = chan of int;
      spawn workerproc(proca[i], i);
   }

   proc := 0;

   for(;;)
   {
      sys->print("\nproc array index : %d\n", proc);
      procch := proca[proc];
      procch <- = 1;

      token := <- procch;
      if(token < 1)
      {
         sys->print("\tproc: %d exit\n", proc);
         proca[proc:] = proca[proc + 1:];
         proca = proca[0:len proca - 1];

         if(len proca == 0)
         {
            sys->print("All done!\n");
            exit;
         }
      }
      proc++;
      if(proc > len proca - 1)
         proc = 0;

   }


}




workerproc(c : chan of int, num : int)
{
   proc := num;

   while(1)
   {
      num++;   # Tee jotain

      <-c ;    # Odota vuoroa

      if(num > 9)
      {
         c <- = 0; # Anna vuoro seuraavalle ja lopeta
         exit;
      }

      sys->print("\tproc: %d \tnum: %d\n", proc, num);


      c <-= 1; # Anna vuoro seuraavalle

   }

}

En haluaisi olla ilonpilaaja, mutta eikö usean keskenään kommunikoivan säikeen käyttö ole aika monesti sääntöjen vastaista, koska näiden skedulointi vaihtelee ajokerrasta toiseen?

Oma ideani perustui ajatukseen, että kaikilla pelinappuloilla olisi oma älynsä. Pelinappulan äly tekisi työnsä itsenäisesti mahdollisesti taustalla, mutta yrittäisi kuitenkin toteuttaa mahdollisen siirtonsa vasta omalla vuorollaan.

Aiemmasta esimerkistäni saa muuten täysin deterministisen, kun laittaa työläissäikeessä työnteon alkamaan vasta, kun monitori on luovuttanut vuoron säikeelle. Tällöin tosin osa ajatukseni ideasta katoaa.

jalski kirjoitti:

Aiemmasta esimerkistäni saa muuten täysin deterministisen, kun laittaa työläissäikeessä työnteon alkamaan vasta, kun monitori on luovuttanut vuoron säikeelle. Tällöin tosin osa ajatukseni ideasta katoaa.

Mutta mikä järki on käyttää säikeitä, jos ne ei kuitenkaan toimi samaan aikaan? :D

Ei juma, menee totaalisesti hermot tähän testausohjelmaan.

Koko firefox kaatui kun yritin laittaa ohjelmani pelaamaan itseään vastaan. Nyt se testausohjelma ei enää edes suostu avautumaan vaan valittaa vain siitä sertifikaatti/javatuki-virheestä. Ja kuten sanottua, se on aiemmin kyllä toiminut täysin ongelmitta. Tekoälyssäni ei pitäisi olla vikaa :/

Java 6, Firefox 3.5.6, Win7.

Jos ohjelma on kuitenkin aiemmin toiminut, vika ei nähdäkseni voi olla siinä. (Jos riittää intoa tutkia asiaa, voin lähettää lähdekoodin.)

No lähdekoodeista ei ole iloa kun en osaa Javaa :(

Nyt 4. yrityskerralla ei tullut virheilmoitusta. Nyt toimii muuten normaalisti, mutta koko kone lagittaa ihan helvetisti tätä ajaessa.

Tekoälyni on miltei valmis, joten kyllähän se vähän harmittaa jos joudun tälläisen asian takia luovuttamaan :(

Joo, ei toimi minulla tuo. Luovun koko kisasta.

Nyt sain sen toimimaan. Ongelmana oli, että testausohjelma ei aina sulkenut tekoälyjäni ja niitä rupesi vähitellen kasautumaan muistiin :P

Mutta, uusi ongelma tuli vastaan! Kun pelitilanne on tämä:

.......OO.......
......OOOO......
......O..O......
.....E..........
......OOOO......
......OOOO......
................
......E.........
................
................
................
................
.......EEE......
.......EEE......
......EEEE......
......EEEE......

Ja tulostan seuraavanlaista kamaa:

S
8 1 8 3
S
8 3 6 3
S
6 3 6 5

Niin jostain syystä testausohjelma hyväksyy vain tuon ensimmäisen hypyn. Miksi? Eikö vuorolla saanut hyppiä niin paljon kuin sielu sietää? :o

Mutta ei pidä tulostaa jokaista hyppyä erikseen, vaan vain alkuperäinen sijainti ja lopullinen sijainti.

Okei, kiitos :)

Testaustyökalu voisi tosiaan lopettaa ohjelmat kun toinen voittaa. Kääntäjä siitä aina huomautteli ettei voi kirjoittaa levylle kun on käytössä. Lopeta-nappi tosin ajaa asian.

Eikä sillä että enää niin väliä, oma botti on jo valmis, ellei vielä ideoita keksi ;)

Eikö testausohjelma siis lähetä L:ää pelin päätyttyä vai toimivatko tekoälynne virheellisesti (= eivät sammuta itseään käskystä huolimatta)?

Testausohjelma ei lähetä L:ää lopuksi. Lopeta napin painaminen lopettaa ohjelmat ja kirjoittaa logiin:

+ P1: L
+ P2: L

Toimiiko Python 3? Esimerkkikoodin totetuts on 2.x koodia, joten ajattelinpa kysyä...

Kilpailun ohjeissa lukee:

lainaus:

Kilpailukoneen tiedot...
... Python 2.6.4, Python 3.1.1 ...

Oho, anteeksi vain... on tainnut sokeus iskeä

User137 kirjoitti:

Testausohjelma ei lähetä L:ää lopuksi.

Kiitos havainnosta! Korjattu versio on nyt palvelimella.

Mitenkäs tuota omaa ohjelmaa voi testata?
Käytössä Python 3.1.1.

New Samppi kirjoitti:

Mitenkäs tuota omaa ohjelmaa voi testata?
Käytössä Python 3.1.1.

Käytä kilpailusivulla linkattua testausohjelmaa. Vaatii javan toimiakseen.
https://www.ohjelmointiputka.net/pomppis/

Itse toimin Windowsin puolella Pythonin kanssa niin, että tein .bat tiedoston jossa oli komento "python tekoaly.py", jonka sitten annoin siihen tiedostokenttään. Toiseen kenttään voi laittaa vaikka esimerkkiälyn tai ihmispelaajan.

aaämdee kirjoitti:

Itse toimin Windowsin puolella Pythonin kanssa niin, että tein .bat tiedoston jossa oli komento "python tekoaly.py", jonka sitten annoin siihen tiedostokenttään.

Linuxissa (Firefox) laitoin tiedostokenttään suoraan "python /oikea/polku/tekoaly.py"

Chiman kirjoitti:

aaämdee kirjoitti:

Itse toimin Windowsin puolella Pythonin kanssa niin, että tein .bat tiedoston jossa oli komento "python tekoaly.py", jonka sitten annoin siihen tiedostokenttään.

Linuxissa (Firefox) laitoin tiedostokenttään suoraan "python /oikea/polku/tekoaly.py"

Juu, mutta Windows ei ymmärrä tuota tiedostoa komennoksi, pelkästään .exe .bat .cmd jne.. kelpaavat

Linuxilla toimi hyvin minullakin, kun pisti tiedoston alkuun #!/polku/tulkkiin

Windowsissa seuraava komento voisi toimia:

c:\python\python c:\omat\esim.py

Tässä c:\python\ on hakemisto, johon Python on asennettu.

Kyllä se Windowsissakin kelpaa kunhan python.exen kansio löytyy PATH-ympäristömuuttujasta.

En ehdi toteuttaa omaa ideaani kilpailuun ja taitaapi olla, että oma monisäikeinen toteutukseni ei aivan täyttäisi sääntövaatimuksia.

Alla kuitenkin esimerkkinä Limbolla toteutettu 18-säikeinen testiohjelma. Pomppista ohjelma ei pelaa, mutta pelilaudalle voi laittaa esteitä ja pelilaudan yläosassa olevat omissa säikeissä toimivat typerät laatikot yrittävät löytää tiensä pelilaudan alimmalle riville. Prosessorikuorma jaetaan tasan laatikoiden kesken ja laatikot siirtyvät yhtäaikaa laudalla.

Koodi ei ole mitenkään nättiä ja kommentteja ei ole paljoa, mutta ehkä tuosta joku jotain tolkkua saa...

(Mod. poisti pitkän koodin, ei tukita keskustelua.)

Onko sallittua tarkastaa ohjelman käyttämä aika esim. clock()-funktiolla? Säännöissä lukee "ottelun on joka kerta kuljettava täsmälleen samalla tavalla riippumatta kellonajasta, tietokoneesta tai säätilasta", joka vinkkaisi, että clockin käyttäminen ei ole sallittua. Jos aikaa ei saa tarkistaa, on hyvin hankalaa välttää ajalla häviäminen ovelasti toteutettua muuritaktiikkaa vastaan.

Itse ainakin tulkitsin, ettei ajankulku saa vaikuttaa valittavaan siirtoon. Jos esim. 50 sekunnin kohdalla alkaisi rajoittaa laskennan syvyyttä, pienet satunnaiset vaihtelut operaatioiden kestoissa voisivat aiheuttaa tuon 50 s -rajan umpeutumisen vaihtelevasti kahdella eri siirtovuorolla muuten identtisissä peleissä.

Vastustajan taktiikkaa voi kuitenkin päätellä muustakin kuin ajasta ja toimia sen mukaan.

Ajankäytön seuraaminen tosiaan tekisi ohjelmasta satunnaisen, joten tällä kertaa jokaisen täytyy vain arvioida ennalta ajankäyttönsä. (Henkilökohtaisesti toivoisin, että mahdollisimman monen tekoälyn pääpaino olisi tehokkaassa taktiikassa eikä raskaassa laskennassa. Ei ole järkeä kilpailla siitä, kuka koodaa parhaan minmax-algoritmin.)

Pystytkö kuvailemaan muuritaktiikkaa, jolla yhä voisi voittaa pelin? Ainoa käytännössä mahdollinen väistämätön muuri on kyhättävä heti omaan päätyyn. Koska pelin pituus on nyt rajoitettu 1000 kierrokseen, muurille ei pitäisi hävitä, kunhan ei käytä aivan tolkuttomasti aikaa toivottomiin laskuihin.

Ovelalla muurilla tarkoitin muuria josta ei näe heti että se on muuri. Sen voittaa helposti jos varmistaa että oma tekoäly ei käytä liikaa aikaa (60ms / siirto). Tekoälyn käyttämää aikaa voi toki arvioida ilman kelloakin. Nyt ajan arviominen kuitenkin muodostuu tärkeäksi osaongelmaksi, joka ei ehkä ollut tarkoitus.

Melkein hävettää oman tekoälyn yksinkertaisuus kun täällä porukka keskustelee tällaisista asioista.

No enpähän sentäs yöunia menettänyt tämän kilpailun takia ;)

En saa ajettua testausohjelmalla java-botteja; en omaani enkä esim-bottia. Saan vain No line found -ilmoituksen. Olen yrittänyt mm.:

* P1 = java /home/kayttaja/pomppis-esim/esim
+ P1: 1
No line found

Komentoriviltä ajaminen onnistuu, mutta tulostuvan siirtolistan avulla oman botin kehittymisen seuraaminen on liian työlästä.

Toimii:

$ java -jar pomppis.jar "python esim.py" "java esim"

Millaisella komennolla java-botin saisi toimimaan selaimessa? (Alustana Ubuntu 9.10, Firefox 3.5.6, uusin java)

Helpoin ja varmin konsti on kirjoittaa komentorivillä toimiva käynnistyskomento shell-skriptiin ja antaa testausohjelmalle ajettavaksi tuo skripti.

Kiitos, sen avulla onnistui. Vaati näköjään myös työhakemiston asettamisen.

Jos joku painii saman ongelman kanssa, tässä esim_run.sh:

#!/bin/sh
cd /home/kayttaja/pomppis-esim
java esim

Tuo vielä suoritettavaksi (chmod a+x esim_run.sh), niin sitten toimii selaimesta valittuna.

Kilpailua on nyt jäljellä hieman yli neljä vuorokautta, vielä ehtii osallistua! Tekoälyn pohjaksi voi ottaa vaikka esimerkkiälyn lähdekoodin; siitä pääsee helposti alkuun. Tähän mennessä mukana on esimerkin lisäksi vasta seitsemän varsinaista osallistujaa, eli jopa kymmenen parhaan joukossa on yhä tilaa.

Metabolix kirjoitti:

Kilpailua on nyt jäljellä hieman yli neljä vuorokautta, vielä ehtii osallistua! Tekoälyn pohjaksi voi ottaa vaikka esimerkkiälyn lähdekoodin.

Ku noi helpoks tehtiin niin pitihän sitä parintunnin parantelulla osallistua :)

Top 10 täältä tullaan

Sain eilen "Kuovi"-työnimeä kantavan tekoälyni sellaiseen kuntoon että uskallan luvata varmasti osallistuvani kilpailuun. On paikallaan lämpimästi kiittää järjestäjää hienon kisan järjestämisestä. Etenkin esimerkkiohjelmien väsääminen noinkin monelle kielelle ansaitsee hatunnoston.

Kuovissa on vielä vähän paranneltavaa. Tämän hetkinen "parhaan" siirron arvioiva algoritmi nimittäin pitää paikallaan pysymistä erinomaisena taktiikkana, eikä ohjelma sen takia tahdo pärjätä esimerkkitekoälylle eikä edes itselleen. Eiköhän tällaisista pikku pulmista kuitenkin selvitä sunnuntaihin mennessä.

Muokattu 15.01.2010 15:37 - Rivivälit kuntoon

Valmis tekele lähti. Toivottavasti tulee paljon osallistujia.

Kilpailu lähestyy loppuaan. Kaikkiin tähän mennessä saapuneisiin viesteihin on nyt vastattu, joten jos vastausta ei ole kuulunut, kannattaa mitä pikimmin lähettää tekoäly uudestaan.

Milloin tuloksia o tiedossa?

Kilpailu on päättynyt ja tulokset julkaistu!

Mukaan ehti lopulta 15 toimivaa tekoälyä, joista tosin yksi on kilpailun esimerkkiäly ja toinen käyttää kieroa blokkaustaktiikkaa, joka sääntömuutoksen jälkeen tuotti ruhtinaalliset nolla pistettä.

Voittaja on Aleksi Hartikainen (ahr) tekoälyllään Kettu. Onneksi olkoon!

Kiitokset kaikille muillekin osallistujille hyvästä kilpailusta.

Kiitokset Laurille laadukkaasta kilpailusta (kuten aina) ja ennätysnopeista tuloksista.

Hyvin järjestetty kilpailu,

ja pääsin kuin pääsinkin TOP 10! Uutta kilpailua vaan putkeen niin voi yrittää kovemmin. Huomaa että voittaja oli selvästi panostanut kun koodirivejä oli jaksanut yli 1000 kirjoittaa, itselläni jäi tasan 100, joista n. 70 oli esimerkistä :P

Mielestäni sopiva tahti tälläisille kilpailuille olisi yksi kuukaudessa. Ensikerralla voisi olla hiukan monimutkaisempi peli.

Onnea voittajalle!

tkok kirjoitti:

Mielestäni sopiva tahti tälläisille kilpailuille olisi yksi kuukaudessa. Ensikerralla voisi olla hiukan monimutkaisempi peli.

Laadukkaan kilpailun järjestämisessä on sen verran työtä, että hyvin harva sitä tekisi palkatta kuukauden välein. Tietysti järjestäjä voisi aina vaihtua, mutten usko tämän kokoisessa yhteisössä olevan heitä tarpeeksi, jotta hyviä kilpailuita voisi järjestää kovin usein. Osallistuvien ohjelmien määrä ja/tai tasokin laskisi tiheämmän tahdin myötä.

Hienosti järjestetty kisa. Onnittelut voittajalle ja muille kärkeen sijoittuneille.

Oma luovuus ei tällä kertaa riittänyt toteuttamaan parempaa kuin yksinkertaisen minimaxin, joten jätin lähettämättä. Hyvä niin, niitä oli ainakin kaksi parempaa jo mukana.

tkok kirjoitti:

Mielestäni sopiva tahti tälläisille kilpailuille olisi yksi kuukaudessa.

Chiman kirjoitti:

Laadukkaan kilpailun järjestämisessä on sen verran työtä...

Tilastoja: Kilpailun järjestäminen vaati sääntöjen lisäksi noin 3000 koodiriviä: noin 900 riviä esimerkkiälyihin 11 kielellä, noin 1400 riviä testausohjelmaan ja otteluita näyttävään sivuun ja loput 700 otteluiden automatisointiin sekä bannerin, tulossivun ja tilastojen generointiin. Nämä ovat vieläpä lopullisia rivimääriä kaikkien kokeilujen ja muutosten jälkeen. Esimerkkien kirjoittaminen tosin oli ensimmäisen jälkeen melko mekaanista.

Suurin osa ajasta meni graafiseen testausohjelmaan, joten jos kilpailuja halutaan pitää paljon useammin, tällaisiin hienouksiin ei ole aikaa. Onneksi perushommat alkavat olla siinä määrin selvillä, että yhä suuremman osan hallintakoodista voi kopioida seuraavaan kilpailuun vain pienillä muutoksilla.

Jos kilpailun järjestäminen kiinnostaa muttei halua ottaa vastuuta ohjelmien ajamisesta, on kyllä mahdollista jakaa työ useamman kesken. Kilpailua varten tarvitaan hyvä tehtävä, realistinen arvio rajoista (laudan koko), järkevä pisteytysmalli, yksinkertainen esimerkkiäly, toimiva tarkistusohjelma ja selkeät säännöt. Hyvä tehtävä on helppo ymmärtää ja ratkaista jotenkuten mutta niin vaikea, ettei kukaan voi lähettää täydellistä ratkaisua. Ideoita ja luonnoksia voi lähettää minulle ja Antille.

Chiman kirjoitti:

Oma luovuus ei tällä kertaa riittänyt toteuttamaan parempaa kuin yksinkertaisen minimaxin

Itse olen perinteisesti suosinut hyvin karkeita heuristiikkoja ennemmin kuin raakaa laskentaa. Näin tälläkin kertaa, ja menestys kyllä yllätti täysin. Onneksi hyvin kirjoitettu minimax voitti, muuten olisi varmaan pitänyt vetää oma tekoäly pois kilpailusta. :)

Eron tekoälyjen periaatteissa huomasi kyllä laskenta-ajasta: useimmat ottelut kestivät vain pari sekuntia, mutta kummatkin minimax-tekoälyt (Kettu ja Awesome) käyttivät joka kerta nelisenkymmentä sekuntia.

Metabolix kirjoitti:

... kummatkin minimax-tekoälyt (Kettu ja Awesome) ...

Myös kolmanneksi tullut Mijuku on käsittääkseni minimax-pohjainen.

Chiman kirjoitti:

Myös kolmanneksi tullut Mijuku on käsittääkseni minimax-pohjainen.

Edit: Käsittääkseni Mijuku (ehkä myös Ants?) on itse asiassa ahne eli valitsee aina suurimman mahdollisen hyödyn. Minimaxissa pitäisi valita pienin mahdollinen haitta eli mahdollisimman varma siirto.

Suurin mahdollinen hyöty ja pienin mahdollinen haitta tarkoittavat yleensä samaa asiaa (zero-sum game). Minimax on tavallaan ahne algoritmi (valitsee paikallisesti optimaalisen siirron) jos ei käy koko hakupuuta läpi.

Itse minimax on triviaali toteuttaa, mutta yksinään se ei riitäkään mihinkään. Tekoälyn kiinnostavat ja vaikeat osat ovat heuristiikkafunktio, siirtojen järjestely yms.

Täältä vielä kehut ja kiitokset kilpailun pitäjälle.

funktio kirjoitti:

Suurin mahdollinen hyöty ja pienin mahdollinen haitta tarkoittavat yleensä samaa asiaa

Jos esimerkiksi siirtosarja A-B johtaa pelaajan häviöön mutta A-C pelaajan voittoon, tarkoittamani ahne algoritmi tekee siirron A, koska sillä on mahdollisuus voittaa (eli hyöty on suuri mutta epätodennäköinen). Sen sijaan minimax ei tee tätä siirtoa, koska hyvää vastustajaa vastaan sillä häviää varmasti (eli mahdollinen haitta on todella paha).

Ahaa, ok. Optimistinen kuvaa tuollaista ehkä vähän paremmin kuin ahne.

Hieno kisa oli ja todella mukavaa, että kilpailun tulosten esittämiseenkin oli nähty vaivaa. Oma tekoälykin näytti pärjäävän melko hyvin. :)

Tuli vielä mieleen, että olisi varmaan aika jännää nähdä kuinka hyvin nuo tekoälyt toimisivat, jos tuo kilpailun huonoin tekoäly olisikin tarkoituksella jättänyt yhden aukon tuonne puolustukseen.

Hauska kisa.
Itse olin aika varma, että kisasta tulee minimaxien taisto, mutta metabolixin siltataktiikan toimivuus yllätti. Tuota kettuakin olisi varmaan vielä voinut parantaa vastaavilla ideoilla.

Kiitos hauskasta kisasta ja kätevästä testausohjelmasta. Tulossivun kuvat ovat myös hienoja!

maueri.cpp: In function ‘void ytoimi()’:
maueri.cpp:52: error: lvalue required as left operand of assignment
maueri.cpp:52: error: expected ‘)’ before ‘;’ token
maueri.cpp:52: error: expected primary-expression before ‘)’ token
maueri.cpp:52: error: expected ‘;’ before ‘)’ token
maueri.cpp:197: error: expected ‘}’ at end of input
Hups... pitäisi varmaan lukea useammin sähköpostia:)

Jokotai: älyssäsi oli muuten kymmeniä virheitä, jopa ylimääräisiä sulkumerkkejä. (Kääntäjä vain jumahti jo ensimmäisiin.) Millä ihmeen välineellä olet sen tehnyt?

Tein "pikkukorjauksia" ohjelmaani. Pikkulisäyksiä kun olivat niin eipä siinä sitten tullut tarkistettua. Aihetta olisi ollut.

Neljäs sija yllätti jos ottaa huomioon että huomasin outouksia vielä lähetyksen jälkeen. Jos ihmispelaajana esim tekisin 2 kerroksisen muurin sen eteen niin ei osaa kiertää sitä, itseasiassa jäi tekemään ihan turhia ylös-alas siirtoja taimmaisella nappulalla. Yritin vielä korjata sen virheen mutta kaikki yritykset hävisivät tuolle lähetetylle versiolle joten annoin olla...

Kävi myös mielessä soveltaa tuohon reitinhakualgoritmia mutta käytännössä nopein tie maaliin on kai raakasti keskeltä läpi hyödyntäen omia ja vastustajan nappuloita.

Joo mukava kisa oli kyllä ja erityisesti testi ja tulosohjelmat olivat hieno lisä. Kolmas sija oli paras mitä uskalsin toivoa ja olen oikein tyytyväinen siihen. Pitänee pyrkiä sitten seuraavassa kilpailussa vielä samalle sijalle, niin tulee mukava kolmen putki kolmosia :)

Metabolix kirjoitti:

Jos esimerkiksi siirtosarja A-B johtaa pelaajan häviöön mutta A-C pelaajan voittoon, tarkoittamani ahne algoritmi tekee siirron A, koska sillä on mahdollisuus voittaa (eli hyöty on suuri mutta epätodennäköinen). Sen sijaan minimax ei tee tätä siirtoa, koska hyvää vastustajaa vastaan sillä häviää varmasti (eli mahdollinen haitta on todella paha).

Uskoisin tosiaan tekoälyni (Mijuku) toimivan minimaxilla siinä mielessä, että se olettaa vastustajan myös siirtävän parhaan mahdollisen siirron. Eli tuossa Metabolixin esimerkissä olettaisi A-B siirtosarjan tapahtuvan (ja johtavan häviöön) eikä siis valitse siirtoa A.

Kiitokset kilpailun järjestäjälle mukavasta kilpailusta !
Oman tekoälyni sijoitus ei tosin kovin mahtava ollut, mutta enpä ihan viimeiseksi kuitenkaan tullut :)

Hyvin järjestetty kilpailu. Itselläni kävi samalla lailla kuin Chimanilla, eli ensimmäinen versio omasta minimaxista ei oikein tyydyttänyt ja parempien strategioiden testaamiseen ei oikein ollut aikaa. Mietin hiukan rooman legiooniota matkivaa taktiikkaa eli kaksi ensimmäistä riviä etenisi nopeasti paririvissä blokaten keskustan ja sitten takarivin hevoset kiertäisivät neljän ryhmissä vasemmalta ja oikealta. Neljän palikan ryhmähän voi tuossa edetä jatkuvasti kahden pisteen hypyillä ja jopa muuttaa kulkusuuntaa. Laskeskelin kuitenkin, että Metabolixin käyttämä tikapuu strategia olisi häiritsemättä suoritettuna nopeampi eikä oikein ollut aikaa testailla hyviä blokkausstrategioita. On kohtuullisen haastavaa keksiä fiksu, ei brute force strategia peliin jota ei itse osaa pelata :)

Metabolix kirjoitti:

Jos kilpailun järjestäminen kiinnostaa muttei halua ottaa vastuuta ohjelmien ajamisesta, on kyllä mahdollista jakaa työ useamman kesken. Kilpailua varten tarvitaan hyvä tehtävä, realistinen arvio rajoista (laudan koko), järkevä pisteytysmalli, yksinkertainen esimerkkiäly, toimiva tarkistusohjelma ja selkeät säännöt. Hyvä tehtävä on helppo ymmärtää ja ratkaista jotenkuten mutta niin vaikea, ettei kukaan voi lähettää täydellistä ratkaisua. Ideoita ja luonnoksia voi lähettää minulle ja Antille.

Voisi olla mielenkiintoista valita seuraavan kilpailun aiheeksi joku reaaliaikainen kahden pelattava verkkopeli. Serveri ohjelma kellottaisi peliä ja välittäisi pelaajien siirrot toisilleen. Se näyttäisi pelin kulun graafisesti ja toimisi näin samalla tekoälyn testiohjelmana sekä kilpailun tuomarina. Tuohon saa muutamalla rivillä koodia toteutettua asiakasohjelman, jolla ihmispelaaja voisi pelata tekoälyään vastaan testimielessä.

Olen toteuttanut toimivan kahden pelaajan serveri ohjelman rungon Infernolle Limbolla omaa Ansa peliäni varten ja voisin auttaa kilpailun toteuttamisessa.

Ansa peli sopisi sinänsä muuten kilpailun aiheeksi, koska peliä käytännössä sisäisesti pelataan pelilaudalla: törmäystarkistus ja tekoälyn peruslogiikan toteutus on helppo.

Ansa peli: http://www.tip9ug.jp/who/jalih/ansa-game.jpg

User137 kirjoitti:

Jos ihmispelaajana esim tekisin 2 kerroksisen muurin

;_; Tuo oli minun ohjelmani idea:(

Onko Ansa jonkinlainen tron-kopio?

Tuollainen ansa-peli näyttäisi ainakin minusta aika mielenkiintoiselta idealta tekoälykilpailulle.

tgunner kirjoitti:

Onko Ansa jonkinlainen tron-kopio?

Ansa on tällä hetkellä vain erittäin yksinkertainen Tron kopio. Ansassa ei ole toteutettuna seiniä ja erilaisia kenttiä. Toki näiden lisääminen olisi helppoa.

Ansa nimi pelille juontaa ajalta ennen ajanlaskua, kun joskus pikkupoikana pelasin kaverin Amstradilla Ansa-nimistä peliä, jossa ohjattiin kokoajan etenevää viivaa ja yritettettiin olla törmäämättä omaan tai kaverin ohjaamaan viivaan.

Ansa syntyi, kun halusin kokeilla miten helppo Infernolle olisi Limbolla saada aikaiseksi yksinkertainen kahdenpelattava reaaliaikainen verkkopeli.

Olen siistinyt koodia ja lisännyt serverin ja asiakkaan samaan ohjelmaan, jottei erillistä asiakas -tai serveriohjelmaa tarvittaisi. Saatan lisätä muutaman seinillä varustetun kentän mukaan, jos ehdin. Postitan tuon koodivinkkeihin, kunhan saan sen siihen kuntoon, että olen siihen tyytyväinen.

Tässä näyttääkin olevan seuraavan kisan aihe jo valmiina. Olisiko kellään päivämäärää seuraavan kisan alkamiseen?

Aiheestakin on vielä pitkä matka kilpailuun.

Korjatkaa toki, jos olen väärässä, mutta eikö jalskin ehdottamaan peliin ole (ainakin symmetrisissä alkuasetelmissa) melko yksinkertaista toteuttaa voittava strategia? Peli olisi siis liian triviaali kilpailua varten.

Ideoilla on paremmat mahdollisuudet päästä kilpailuiksi asti, jos niiden tueksi pystyy esittämään hyvän arvion tehtävän vaikeusasteesta ja sopivista resurssirajoista sekä kattavat mutta tarpeeksi yksinkertaiset säännöt. (Jottei aiheita paljastettaisi etukäteen, on ehkä parempi käyttää tarkempiin ehdotuksiin sähköpostia.)

Metabolix kirjoitti:

Peli olisi siis liian triviaali kilpailua varten.

Idea lienee siinä että ohjelma osaa sopeutua eri kartoille. Eikä tapaus tyhjä neliökään ole yksinkertainen

+ - - - - - - - - +
| . . . . . . . 3 |
| . . . . . . . . |
| . . . . . . . . |
| . . . . . . . . |
| . . . . . . . . |
| 0 . . . . . . . |
+ - - - - - - - - +

+ - - - - - - - - +
| . . . . 3 3 3 3 |
| . . . . 3 . . . |
| 0 0 0 0 3 . . . |
| 0 . . . 3 . . . |
| 0 . . . . . . . |
| 0 . . . . . . . |
+ - - - - - - - - +

Ohjelma kolme voittaisi jos ei tekisi virhettä

+ - - - - - - - - +
| . . . . 3 3 3 3 |
| . . . . 3 . . . |
| 0 0 0 0:3 . 3 3 |
| 0 . . 0:3 3 3:3 |
| 0 . . 0 0 0 0 0 |
| 0 . . . . . . . |
+ - - - - - - - - +

+ - - - - - - - - +
| . . . . . . . 3 |
| . . . X X . . . |
| . . X X X X . . |
| . . X X X X . . |
| . . . X X . . . |
| 0 . . . . . . . |
+ - - - - - - - - +

Jo noin pieni muutos muodostaa suuren strategisen muunnoksen.
EDIT: Nuo kartat näyttivät paljon paremmilta kirjoitus vaihteessa :)

Mod. lisäsi kooditagit

Omassa versiossani pelaaja ei kuole osuessaan pelialueen seinään, vaan tulee ulos toiselta puolelta kenttää.

Oma ajatukseni olisi saada kilpailuksi sellainen, jossa tekoäly joutuisi tekemään siirtonsa realiajassa pelitilanteen mukaaan, eikä niinkään käyttäisi pelkästään valmiiksi laskettua strategiaa.

Jokotai: Jotta pohdintasi olisivat jotenkin yhteydessä muuhun keskusteluun, selvitä ensin käsitteen "voittava strategia" merkitys. Wikipedia auttaa (ks. myös selkeämpi ruotsinkielinen artikkeli). :)

Voittavan strategian olemassaolo tarkoittaa lyhyesti, että alkutilanteesta voidaan suoraan kertoa pelin lopputulos. Esimerkiksi 3×3 ruudun ristinollassa peli päättyy tasan, mikä tosin tarkoittaa, ettei voittavaa strategiaa ole. Vastaavasti kuitenkin joissain peleissä voi olla, että toinen pelaajista voittaa aina. ("Aina" tarkoittaa tässä yhteydessä samaa kuin "ellei pelaa tyhmästi".)

Oletetaan, että pelaajat liikkuvat vuorotellen ja törmäävät seiniin. On helppo havaita, että 2×2-ruudukossa aloittaja häviää ja 3×3-ruudukossa aloittaja voittaa. Pienellä ohjelmalla voidaan tästä jatkaa tutkimusta, ja ellen koodannut sitä väärin, niin parillisessa ruudukossa aloittaja häviää ja parittomassa voittaa muutamaa poikkeustilannetta lukuun ottamatta.

Vaikka reunoilta pääsisi ympäri, lopputulos on yhä ennustettavissa. Seinätkään tuskin muuttavat asiaa. Arvelen myös, että tulos on mahdollista laskea isollakin tasolla niin nopeasti, ettei tätä voi järkevästi estää laskuaikaa rajoittamalla.

Realiaikainen peli kannattaa kilpailutilanteessa simuloida kierros kerrallaan tapahtuvana simulaationa, jossa kaikkien pelaajien syötteet kerätään ja sitten suoritetaan samanaikaisesti(Samalla lailla kuin tehtiin kivi-paperi-sakset kilpailussa). Jokaisella kierroksella olisi aikaraja, joka olisi tarpeeksi pieni, jotta peli vastaisi reaaliaikaisuutta. Jos pelaaja ei ehdi vastata tässä ajassa, toimisi peli taustalla ikaan kuin näiden kierrosten aikana pelaaja ei antaisi syötettä.

Simulaatiolla saavutetaan se, ettei vaihtelevat viiveet nettiliikenteessä tai vaikkapa testikoneen prosessien skeduloinnissa aiheuta epäreilua kilpailutilannetta. Simulaatio on myös täysin toistettavissa (paitsi, jos sallitaan ajanylitys ja vuoron väliin jääminen), toisin kuin reaaliaikainen peli oikeiden kommunikointirajapintojen yli.

Metabolix kirjoitti:

Oletetaan, että pelaajat liikkuvat vuorotellen ja törmäävät seiniin. On helppo havaita, että 2×2-ruudukossa aloittaja häviää ja 3×3-ruudukossa aloittaja voittaa. Pienellä ohjelmalla voidaan tästä jatkaa tutkimusta, ja ellen koodannut sitä väärin, niin parillisessa ruudukossa aloittaja häviää ja parittomassa voittaa muutamaa poikkeustilannetta lukuun ottamatta.

Vaikka reunoilta pääsisi ympäri, lopputulos on yhä ennustettavissa. Seinätkään tuskin muuttavat asiaa. Arvelen myös, että tulos on mahdollista laskea isollakin tasolla niin nopeasti, ettei tätä voi järkevästi estää laskuaikaa rajoittamalla.

Tässä molemmat pelaajat tekisivät siirtonsa yhtäaikaa ilman tietoa toisen pelaajan tulevasta siirrosta. Toki vastustajan seuraavaa liikettä voi yrittää arvata tai laskea aiemman kulkusuunnan mukaan. Serveri-ohjelma siis kellottaisi peliä ja vastaanottaisi pelaajien siirtoja aina yksi siirto/frame. Jos siirtoa ei tulisi jatkaisi pelaaja aiemman kulkusuunnan mukaan.

Tähän kyseiseen tehtävään voisi olla mielenkiintoista käyttää tekoälyn pohjana geneettistä algoritmia.

jalski: Itse ongelman kannalta ei ole kovin olennaista, liikkuvatko pelaajat samaan aikaan vai erikseen. Unohda nyt hetkeksi säieteoriat ja genetiikka ja palaa ihan tavallisiin peliälyjen hakualgoritmeihin. Miten laskisit oikeasti parhaan siirron? Miten vastustajan seuraavan siirron arvaaminen mielestäsi vaikuttaa valintaan? Käytännössähän tekoäly varmasti laskisi kaikilla kolmella vaihtoehdolla ja valitsisi omaksi siirrokseen turvallisimman – siis perinteinen minmax-algoritmi jälleen.

FooBat: Miten toteuttaisit yksinkertaisesti mutta luotettavasti yksittäisen vuoron ajastuksen ja ohjelman pysäytyksen aina vuorojen välissä? Jos vielä huomioidaan esitetyt vaatimukset graafisesta testausohjelmasta, joka toimisi sekä Windowsissa että Linuxissa, homma alkaa mennä todella mutkikkaaksi.

Minusta kyllin tarkkaan tulokseen päästäisiin ilmankin simulaatiota. Ohjelmat toimivat samalla koneella, joten kommunikaatiossa ei ole merkittävää viivettä. Kumpikin saa oman ytimen prosessorista, joten skeduloinnin ei pitäisi olla ongelma. Itse kilpailua pyörittävä ohjelma on niin kevyt, ettei sen pitäisi vaikuttaa juuri enempää kuin muidenkaan satunnaistekijöiden.

Jos puhutaan reaaliaikaisesta pelistä, ideana ilmeisesti on juuri sallia ajanylitys ts. jättää aika mittaamatta ja päivittää tilannetta vain tekoälyn viimeisimmän viestin mukaan, olkoonpa päivitysväli 0,5 tai 0,01 sekuntia. Myös jokin aivan konkreettisesti reaaliaikainen peli (rallia joku ehdotti) olisi tällä tavalla mahdollinen.

Sillä, liikkuvatko pelaajat vuorotellen vai erikseen, on kyllä olennainen merkitys. Ero on siinä, että oman siirron voi tehdä tietäen, että vastustaja ei voi suoraan reagoida tähän siirtoon, vaan vasta seuraavaan. Vertaa: tavallinen vs. vuoropohjainen kivi-paperi-sakset.

Samanaikaisuus ei tietenkään vielä tee pelistä luonteeltaan reaaliaikaista.

Itse asiassa tässä pelissä ei ole voittavaa strategiaa

+ - - - - - - - - +
| 0 0:3 3 3 3 3 3 |
| 0:0:3 . . . . . |
| 0:0:3 . . . . . |
| 0 . 3 . . . . . |
| 0 . . . . . . . |
| 0 . . . . . . . |
+ - - - - - - - - +

Tuo simuloi tilannetta jossa 0 tekee serpentiini tien kaltaista tyyliä ja 3 yrittää turvata itselleen mahdollisimman paljon tilaa. Vaikka 0 aloittaisi olisi se jo hävinnyt pelin(jos ei vierheitä). Toki voitaisiin tehdä kolmiulotteinen taulukko ihan hauskuuden vuoksi:)

Jokotai: En ymmärrä argumenttiasi. Taaskin esität vain yhden tavan liikkua, kun pitäisi tarkastella kaikkia vaihtoehtoja. Kai tuosta jokainen näkee, että 0 teki virheen mennessään nurkkaan (tai jos puhutaan jalskin versiosta, virhe oli U-käännöksessä). Yhtä hyvin se olisi voinut tehdä täsmälleen saman kuvion kuin 3, jolloin sillä ei olisi mitään hätää.

Jos pelaajat liikkuvat samaan aikaan, näissä mainitsemissani 2. pelaajan voittoon johtavissa tilanteissa päädytään tasapeliin, koska lopputilanteessa kumpikaan ei voi liikkua. Erikseen liikuttaessa vain toinen pelaajista törmää ensin.

os: Toki, mutta en usko, että se muuttaisi (tässä pelissä) ratkaisumallia.

Mutta miten haluatte: jos aihe tosiaan kiinnostaa, laitetaan kilpailu pystyyn. Tarvitaan vielä pelin nopeus ja pelilaudan koko – ehdotuksia otetaan vastaan.

Voisiko pelissä olla 3-ulotteiset kentät? ja hieman esteitä. Myös vielä useampi ulottuvuus (4-6) voisi tuoda peliin lisää haastetta?

tkok kirjoitti:

Voisiko pelissä olla 3-ulotteiset kentät? ja hieman esteitä. Myös vielä useampi ulottuvuus (4-6) voisi tuoda peliin lisää haastetta?

Voi.

Miten lisäät peliin enemmän kuin 3 ulottuvuutta? Teleportteja tms?

Eihän siinä ulottuvuuksien lisäämisessä laskennallisesti mitään kummallista ole. Paikkavektoriin vaan tulee useampia ulottuvuuksia, esimerkiksi 2-ulotteisessa maailmassa sijaintisi voisi olla (3, -5) ja 6-ulotteisessa maailmassa (3, -5, 0, 0, 7, 12).
Hankaluuksia tulee vasta lähinnä siinä vaiheessa kuinka esittää moniulotteinen maailma havainnollisesti käyttäjälle 2-ulotteisena (näytöllä).

Jo kolmiuloitteisessa tapauksessa graafinen testausohjelma on käytännössä hyödytön, ja luultavasti osallistumiskynnys nousisi samalla aivan liian korkealle – tarkoitus on saada kilpailuista myös aloittelijoille ymmärrettäviä.

Pelistä tulee mielenkiintoisempi myös lisäämällä samalle tekoälylle kahden madon ohjaaminen, jolloin erilaisten taktiikoiden määrä kasvaa huomattavasti. Tällöin on vaikeampi suunnitella täydellistä ratkaisua.

Metabolix kirjoitti:

Jo kolmiuloitteisessa tapauksessa graafinen testausohjelma on käytännössä hyödytön, ja luultavasti osallistumiskynnys nousisi samalla aivan liian korkealle – tarkoitus on saada kilpailuista myös aloittelijoille ymmärrettäviä.

Totta vaikeaksi menee, mutta jos tämän tyyppinen kisa järjestetään, niin sen jälkeen voidaan pitää jatkosarja, jossa taistellaan lisä ulottuvuuksissa.

vehkis91 kirjoitti:

Teleportteja tms?

Teleportit jätetään jatkosarjan jatkosarjaan :)

Jokotai kirjoitti:

Teleportit jätetään jatkosarjan jatkosarjaan :)

Kuten pommit ja miinat, ansat ja power-upit

Sivuston oikeasta alaosasta löytyvän Ohjelmoi tekoäly pikkukuvan perusteella taitaa olla Ansa-peli kilpailu tulossa...

Metabolix: minkälaiseen ratkaisuun päädyit toteutuksen kanssa: Käydäänkö kilpailu reaaliaikaisesti verkkopeli tyylisesti serveri-ohjelman avulla, vai jotenkin muuten syötteiden avulla?

jalski: Keskustelu tapahtuu jatkossakin komentorivillä. Tämä ei suinkaan estä reaaliaikaisuutta: socketeista tutun select-kutsun (tai non-blocking-lukemisen) sijaan täytyy vain kysyä käyttäjältä (tai kilpailun tapauksessa pelipalvelimelta), onko dataa tarjolla.

Verkko-ohjelmoinnin vaatiminen on sikäli huono ajatus, että se rajaa monet aloittelijat ja myös suuren joukon ohjelmointikieliä pois kilpailusta. Esimerkiksi C:llä tai Pascalilla verkkotoiminnot ovat suhteettoman hankalia käyttää, ja joissain kielissä verkkokirjastoja ei ole lainkaan. Voi olla, että jossain vaiheessa otetaan komentorivin lisäksi käyttöön verkkovaihtoehto.

Teknisistä asioista saa toki puhua, mutta itse kilpailusta on turha udella enempää ennen lauantaita. :)

Metabolix kirjoitti:

jalski: Keskustelu tapahtuu jatkossakin komentorivillä. Tämä ei suinkaan estä reaaliaikaisuutta: socketeista tutun select-kutsun (tai non-blocking-lukemisen) sijaan täytyy vain kysyä käyttäjältä (tai kilpailun tapauksessa pelipalvelimelta), onko dataa tarjolla.

Tuo on ihan ok. Jos hyväksyt vielä Limbon sallituksi ohjelmointikieleksi, niin saatanpa itsekin jopa osallistua. Tämä tietenkin olettaen, että ehdin saada jotain järkevää kasaan.

Näyttää muuten olevan korjattu ainakin vanhemman Infernon emussa ollut bugi. Jos teet esimerkkiohjelman kilpailuun Limbolle, niin ainakin nyt toimii seuraava:

Isäntäkäyttöjärjestelmän stdin, stdout ja stderr löytyvät Infernolla:

/dev/hoststdin
/dev/hoststdout
/dev/hoststderr

esimerkki:

Olet tehnyt Infernolle Limbolla ohjelman, mikä laskee stdin syötteestä rivien ja sanojen määrän ja tulostaa sen. Haluat käyttää tekemääsi ohjelmaa Windowsin komentoriviltä suoraan. Muutat vain ohjelman lukemaan stdin sijasta tiedostoa /dev/hoststdin ja käynnistät Infernon komennolla:

type testi.txt | c:\inferno\nt\386\bin\emu -d /usr/inferno/wc.dis

(esimerkissä wc on ajettava ohjelma = word count)

jalski kirjoitti:

Isäntäkäyttöjärjestelmän stdin, stdout ja stderr löytyvät Infernolla: /dev/hoststdin, /dev/hoststdout, /dev/hoststderr

Minulla noiden tiedostojen käyttö ei ainakaan toiminut. Kilpailuympäristössä täytyy käyttää tavallisia luku- ja tulostustoimintoja eli tiedostokahvoja 0 ja 1.

jalski kirjoitti:

olettaen, että ehdin saada jotain järkevää kasaan

Saa siihen tyhmemmälläkin osallistua, niin saadaan edes jonkinlainen kilpailu aikaan.

Kilpailu on ajoitettu juuri hyvin yo-kirjoitusten päälle ;D

Jalmari91 kirjoitti:

Kilpailu on ajoitettu juuri hyvin yo-kirjoitusten päälle ;D

Voitto olkoon siis minun ;)

Jalmari91 kirjoitti:

Kilpailu on ajoitettu juuri hyvin yo-kirjoitusten päälle ;D

No mitä nyt, nehän ovat vain kolmena päivänä viikossa ja kestävät vaivaiset kuusi tuntia! :)

Juu, eipä tullut mieleen. Onneksi kilpailuun ehtii hyvin mukaan vielä kirjoitusten jälkeenkin.

Jalmari91 kirjoitti:

Kilpailu on ajoitettu juuri hyvin yo-kirjoitusten päälle ;D

Tämä on hei priorisointikysymys, teetkö jotain oikeasti tärkeää elämässäsi (tekoäly) vai keskitytkö turhuuksiin (yo-kirjoitukset). Samasta aiheesta tuskin tulee toista kilpailua, sen sijaan yo-kirjoituksia järjestetään parikin kertaa vuodessa.