On taas aika suunnitella Ohjelmointiputkan tulevaisuutta, tarkemmin sanoen tulevia kilpailuja. Kilpailut ovat jatkossakin pääasiassa tekoäly- ja algoritmikilpailuja, ja juuri näihin voi nyt ehdottaa ideoita. (Tätä keskustelua ei ole tarkoitettu esimerkiksi demo- tai sävellyskilpailuille vaan jotenkin tekoälyihin tai algoritmeihin liittyville ideoille.)
* Kuinka teoreettinen tai käytännöllinen kilpailun pitäisi olla? Älykäs ohjelma, ristinolla vai jotain aivan muuta?
* Mikä olisi kiinnostava peli tekoälyä varten tai aihe algoritmille?
* Mitä erikoista kilpailussa voisi olla, esimerkiksi joukkuepeliä tai oljenkorsia?
Nyt on tilaisuus vaikuttaa – kiinnostavia mutta tarpeeksi yksinkertaisia ideoita toteutetaan ainakin kerran tai kaksi vuodessa!
Sokkeloäly
Eli äly joka yrittää ratkoa mahdollisimman nopeasti sokkelon.
tesmu kirjoitti:
äly joka yrittää ratkoa mahdollisimman nopeasti sokkelon
Ei sellaisenaan kelpaa, koska http://en.wikipedia.org/wiki/Dijkstra's_algorithm
Tehtävän pitäisi olla sellainen, ettei siihen löydä suoraan optimaalista ratkaisua kirjasta, netistä tai tiedelehdestä. Lisäksi kilpailu muiden osallistujien tekoälyjä yms. tuotoksia vastaan on mielestäni keskeinen elementti houkuttelevassa kisassa.
Mielellään joku peli missä siirretään vuorotellen eikä samanaikaisesti, niin ei tarvitse keskittyä vastustajan strategian arvailuun ja kristallipallon kiillottamiseen.
Esimerkiksi Pah Tum olisi minusta hyvä. Säännöt ovat todella yksinkertaiset. Lisäksi vahvan tekoälyn koodaaminen vaatii loogista ajattelua ja algoritmien suunnittelua eikä paljoa kokemusta itse pelistä.
Wikipediassa on pitkä lista pelejä, joista useimmat joihin olen tutustunut sopisivat hyvin tällaiseen kilpailuun. Moniin ei löydy yhtään tekoälyä netistä.
Olis mielenkiintosempaa jos olis valmiina graafinen ohjelma/peli (mieluiten 3D) jolla seurata tekoälyn käyttäytymistä ja testata eri älyjä vastakkain. Sitä saisi ihan vapaasti käyttää tekoälyä tehdessä, sama julkaistaanko sen lähdekoodi vai ei kun säännöt tunnetaan kuitenkin.
User137 kirjoitti:
Olis mielenkiintosempaa jos olis valmiina graafinen ohjelma/peli (mieluiten 3D)
Miksi 3D? Tarkoitatko tällä, että kilpailun pitäisi käsitellä jotain 3D-aihetta, vai haluatko vain (yli)hienon testausohjelman? Testausohjelman teossa sinänsä ei ole muuta ongelmaa kuin se, että tyylikkään graafisen ohjelman teosta aiheutuu melkoisesti lisävaivaa.
Lisää ideoita saisi vielä esittää. :)
Itse tuskin tulen osallistumaan, mutta ideoita varmaan saa silti esittää. :)
Olen samaa mieltä graafisen pelin mielenkiintoisuudesta, mutta hyvin karkea 2d-grafiikkaa on täysin riittävä. 3d:n en näe tuovan mitään lisäarvoa, ellei kilpailun aihe nimenomaisesti sitä vaadi.
Miten olisi urheilun maailma? Sitä ei kai tähän mennessä ole vielä kokeiltu. Eli jokin mahdollisimman simppeli (mutta ainakin jollain tasolla fysiikkaa mallintava) urheilupelin pohja, jossa tekoälyt kilpailevat toisiaan vastaan. Esim. ralli tai jalkapallo.
Miten olisi pokeri-turnaus? Saisivat botit pelata toisiaan vastaan. Näkeepähän, kellä on paras tekoäly.
Tuo rallipeli vois olla hyvä idea...
goala kirjoitti:
Miten olisi pokeri-turnaus?
Se olisi varmasti mielenkiintoinen, mutta pokeria harrastavilla olisi minusta aika epäreilu etulyöntiasema. Jotkut ovat saattaneet jo ohjelmoida pokeribotteja tai ainakin miettiä asiaa. Joku vähemmän tunnettu peli antaisi kaikille tasavertaisemmat mahdollisuudet.
Torgon ehdotus on minustakin hyvä, mutta vaatisi aika paljon työtä kilpailun järjestäjältä.
Olisikohan esimerkiksi kauppamatkustajan ongelma tai vastaava mielenkiintoinen kilpailun aihe? Tosin erittäin nopeita ja lähes-täydellisiä ratkaisuja saattaa löytää netistä.. Ja sääntöjen kanssa pitäisi olla tarkka, joko niin, että pisteitä on niin vähän että oikea ratkaisu voidaan myös bruteforcea ja sitten kilpaillaan nopeudesta; Tai kilpaillaan nopeuden ja reitin tehokkuuden yhdistelmästä, jos täydellistä ratkaisua ei pystytä muodostamaan.
No, kuitenkin.
Ehkä pelilistasta löytyy ne parhaimmat :>
Jotta rallista tulisi hyvä, siihen vaaditaan kaikenlaista voimaa, kiihtyvyyttä ja kitkaa. Onnistunut osallistuminen vaatisi siis hyviä tietoja fysiikasta, ja näillä tiedoilla taas yksin ajettava ralli taitaa olla melko optimaalisesti laskettavissa. Jalkapallo taas on näin pikaisesti mietittynä aika lähellä hippakilpailua, vai mitä mieltä muut ovat?
Tzaerun algoritmiehdotus vaatisi, että kaikki käyttävät samaa kieltä. (Muutenhan nopeudesta ei ole järkeä kilpailla.) Kilpailun voisi ehkä toteuttaa jollain esoteerisella kielellä. Miltä kuulostaa?
Wikipedian pelilista on toki aina valmis ehdotuslista, joka varmasti pidetään mielessä, jos perinteiseen älypelitekoälykilpailuun lähdetään. :)
funktio kirjoitti:
Se olisi varmasti mielenkiintoinen, mutta pokeria harrastavilla olisi minusta aika epäreilu etulyöntiasema.
Tosin jollain voi olla mihin tahansa kisaan etulyöntiasema, joten hiukka ontuva perustelu minusta. Futis olisi varmaankin mielenkiitoinen, mutta aika lähellä hippaa kuitenkin. Tietty joku rankkarikisa voisi olla ok. Tosin se taas taitaa olla taas aika lähellä tuota kivi-paperi-sakset peliä?
Teuro kirjoitti:
funktio kirjoitti:
Se olisi varmasti mielenkiintoinen, mutta pokeria harrastavilla olisi minusta aika epäreilu etulyöntiasema.
Tosin jollain voi olla mihin tahansa kisaan etulyöntiasema, joten hiukka ontuva perustelu minusta.
No ainahan se on mahdollista, mutta pointtini on, että pokerin tapauksessa se on IMHO aika iso ongelma. Vertaa vaikka hippakisaan, joka oli varmaan kaikille kohtalaisen uusi juttu. Kukaan tuskin oli sattumalta tutkinut juuri niitä sääntöjä satojen tuntien ajan.
Metabolix kirjoitti:
Jotta rallista tulisi hyvä, siihen vaaditaan kaikenlaista voimaa, kiihtyvyyttä ja kitkaa. Onnistunut osallistuminen vaatisi siis hyviä tietoja fysiikasta, ja näillä tiedoilla taas yksin ajettava ralli taitaa olla melko optimaalisesti laskettavissa.
Fysiikkaa pitää toki osata jossain määrin, mutta ei sitä mielestäni tarvi kovin tarkkaan mallintaa. Pääasia että säännöt on kilpailijoiden tiedossa ja samat kaikille. Sehän voi olla vaikka kokonaan toisenlaisessa maailmassa, missä on ihan omanlaisensa fysiikan lait. Optimaalisen radan laskeminen on todennäköisesti mahdollista, jos ajetaan vain kelloa vastaan. Mutta entäs jos sen ottaa "no rules duelina". Eli tekoälyt ajavat toisaan vastaan ja kiilata saa ihan surutta. Pisteitä saisi ainakin voitosta, mutta mahdollisesti myös ajasta. Onhan se varmasti aika vaivalloinen toteuttaa, mutta olisi kyllä mielenkiintoinen ja viihdyttävä. Varsinkin jos kisoja voi seurata reaaliaikaisen pelin avulla.
Metabolix kirjoitti:
Jalkapallo taas on näin pikaisesti mietittynä aika lähellä hippakilpailua, vai mitä mieltä muut ovat?
Ei minun mielestäni. En ole hippakisaan perehtynyt, mutta idea kai oli että hipat jahtaavat jahdattavia ja jahdattavat yrittävät pakoon? Yhtäläisyyksiä tietty on, mutta idealla että palloton joukkue jahtaa pallollista joukkuetta ja pallollinen joukkue yrittää paeta taikka rynniä maalille, ei pitkälle ainakaan oikeassa jalkapallossa pötkitä.
Urheilulajeja on toki muitakin ja moni niistä vaatii menestymiseen myös älyä. Sekä yksilö- että joukkuelajeissa. Nämä olivat vain ensiksi mieleen tulleet esimerkit.
Miten olisi pistää tekoälyt pelaamaan joskus aiemmin mainitsemaani Ansa-peliä. Ansa-pelissä ohjataan viivaa ja yritetään olla osumatta omaan, tai vastustajan ohjaamaan viivaan.
Tämän voisi toteuttaa verkkopelinä client-server toteutuksena.
Alla esimerkkinä Infernolle Limbolla testimielessä toteutettu 2-pelaajan Ansa-pelin runko. Verkkopeli puuttuu vielä ja tällä hetkellä 2-pelaaja matkiikin 1-pelaajan liikkeitä.
implement Ansa; include "sys.m"; sys: Sys; include "draw.m"; draw: Draw; Display, Point, Screen, Image, Rect: import draw; include "tk.m"; tk: Tk; include "tkclient.m"; tkclient: Tkclient; include "keyboard.m"; Ansa: module{ init: fn(ctxt: ref Draw->Context, argv: list of string); }; Tick: adt { delay: int; new : fn(delay : int) : ref Tick; set : fn(t : self ref Tick, delay : int); }; DX: con 100; DY: con 100; size: int; EMPTY, PLAYER, PLAYER2 : con iota; win: ref Tk->Toplevel; board := array[DX] of { * => array[DY] of{* => EMPTY}}; ticki : ref Tick; tick : chan of int; gamech : chan of string; keych : chan of string; init(ctxt: ref Draw->Context, nil : list of string) { sys = load Sys Sys->PATH; draw = load Draw Draw->PATH; tkclient = load Tkclient Tkclient->PATH; if(tkclient == nil){ sys->print("sys->fildes(2), couldn't load %s: %r\n", Tkclient->PATH); raise "fail:bad module"; } tkclient->init(); tk = load Tk Tk->PATH; if (ctxt == nil) { ctxt = tkclient->makedrawcontext(); #sys->fprint(sys->fildes(2), "Ansa: no window context\n"); #raise "fail:bad context"; } sys->pctl(Sys->NEWPGRP, nil); ctlchan: chan of string; (win, ctlchan) = tkclient->toplevel(ctxt, nil, "Ansa", Tkclient->Hide); gamech = chan of string; keych = chan of string; tk->namechan(win, keych, "keych"); cmd(win, "canvas .c -bd 2 -relief ridge"); cmd(win, "frame .f"); cmd(win, "pack .f -side top -fill x"); cmd(win, "pack .c"); cmd(win, "bind .c <Key> {send keych %s}"); cmd(win, "bind . <ButtonRelease-1> {focus .c}"); cmd(win, "bind .Wm_t <ButtonRelease-1> +{focus .c}"); cmd(win, "focus .c"); cmd(win, ".c configure -width 400 -height 400"); size = int cmd(win, ".c cget -actheight") / DY; cmd(win, ".c configure -width " + string (size * DX) + " -height " + string (size * DY)); tkclient->onscreen(win, nil); tkclient->startinput(win, "kbd"::"ptr"::nil); tick = chan of int; spawn winctl(ctlchan); spawn rungame(); gamech <- = "new"; } winctl(ctlchan : chan of string) { for(;;) alt { s := <-win.ctxt.kbd => tk->keyboard(win, s); s := <-win.ctxt.ptr => tk->pointer(win, *s); s := <-win.ctxt.ctl or s = <-win.wreq or s = <-ctlchan => case s { "exit" => keych <- = string 'q'; * => tkclient->wmctl(win, s); } } } rungame() { kch := chan of string; dummykch := chan of string; dir : Draw->Point; p1 : Draw->Point; p2 : Draw->Point; for(;;) alt { s := <- gamech => case s { "new" => deleteall(); kch = keych; p := Point(DX/2, DY/2); dir = Point(1, 0); p1 = p; createp1(p1); p2 = p.add((8,8)); createp2(p2); ticki = Tick.new(40); spawn ticker(tick, ticki); cmd(win, "update"); } c := <-kch => kch = dummykch; ndir := dir; case int c{ Keyboard->Up => ndir = (0, -1); Keyboard->Down => ndir = (0, 1); Keyboard->Left => ndir = (-1, 0); Keyboard->Right => ndir = (1, 0); 'q' => tkclient->wmctl(win, "exit"); } if (!ndir.eq(dir) && !ndir.eq(dir.mul(-1))) { dir = ndir; } <-tick => p1 = p1.add(dir); p1.x = (p1.x + DX) % DX; p1.y = (p1.y + DY) % DY; p2 = p2.add(dir); p2.x = (p2.x + DX) % DX; p2.y = (p2.y + DY) % DY; collision1 := createp1(p1); collision2 := createp2(p2); if(!collision1 || !collision2) { if(!collision1) cmd(win, ".c create oval " + r2s(square(p1).inset(-5)) + " -fill yellow -tags b." + string p1.x + "." + string p1.y); if(!collision2) cmd(win, ".c create oval " + r2s(square(p2).inset(-5)) + " -fill yellow -tags b." + string p1.x + "." + string p1.y); cmd(win, "update"); ticki.set(-1); while(<-tick); if(int <- keych == 'q') tkclient->wmctl(win, "exit"); spawn gamecmd("new"); } else { cmd(win, "update"); kch = keych; } } } gamecmd(message : string) { gamech <- = message; } Tick.new(delay : int) : ref Tick { t := ref Tick (delay); return t; } Tick.set(t : self ref Tick, delay : int) { t.delay = delay; } board2s(board: array of array of int): string { s := string DX + "." + string DY + "."; for (y := 0; y < DY; y++) for (x := 0; x < DX; x++) s[len s] = board[x][y] + '0'; return s; } createp1(p: Point): int { if(board[p.x][p.y] == PLAYER || board[p.x][p.y] == PLAYER2) return 0; cmd(win, ".c create rectangle " + r2s(square(p)) + " -fill red -outline {} -tags b." + string p.x + "." + string p.y); board[p.x][p.y] = PLAYER; return 1; } createp2(p: Point): int { if(board[p.x][p.y] == PLAYER || board[p.x][p.y] == PLAYER2) return 0; cmd(win, ".c create rectangle " + r2s(square(p)) + " -fill blue -outline {} -tags b." + string p.x + "." + string p.y); board[p.x][p.y] = PLAYER2; return 1; } delete(p: Point) { board[p.x][p.y] = 0; cmd(win, ".c delete b." + string p.x + "." + string p.y); } deleteall() { for(j := 0; j < DY; j++) { for(i := 0; i < DX; i++) { board[i][j] = 0; cmd(win, ".c delete b." + string i + "." + string j); } } } square(p: Point): Rect { p = p.mul(size); return (p, p.add((size, size))); } ticker(tick: chan of int, ticki: ref Tick) { tick <-= 1; while((delay := ticki.delay) >= 0){ sys->sleep(delay); tick <-= 1; } tick <-= 0; } r2s(r: Rect): string { return sys->sprint("%d %d %d %d", r.min.x, r.min.y, r.max.x, r.max.y); } readfile(f: string): string { fd := sys->open(f, Sys->OREAD); if (fd == nil) return nil; buf := array[Sys->ATOMICIO] of byte; n := sys->read(fd, buf, len buf); if (n <= 0) return nil; return string buf[0:n]; } cmd(win: ref Tk->Toplevel, s: string): string { r := tk->cmd(win, s); if(len r > 0 && r[0] == '!'){ sys->print("error executing '%s': %s\n", s, r[1:]); } return r; }
jalski kirjoitti:
Miten olisi pistää tekoälyt pelaamaan joskus aiemmin mainitsemaani Ansa-peliä. Ansa-pelissä ohjataan viivaa ja yritetään olla osumatta omaan, tai vastustajan ohjaamaan viivaan.
Tämän voisi toteuttaa verkkopelinä client-server toteutuksena.
Alla esimerkkinä Infernolle Limbolla testimielessä toteutettu 2-pelaajan Ansa-pelin runko. Verkkopeli puuttuu vielä ja tällä hetkellä 2-pelaaja matkiikin 1-pelaajan liikkeitä.
Edellisen, sekä toiseen aiheeseen lähettämäni serveri esimerkin pohjalta saisi kohtuullisen pienellä työllä kyhättyä serveri-ohjelman tekoälyjen peluuttamista ja pelin seuraamista varten.
Pelitilanteen seuranta voisi näyttää vaikka tältä:
http://www.tip9ug.jp/who/jalih/ansa.jpg
Aiemmin postittamani serveri-esimerkki toiminnassa näytti tältä:
http://www.tip9ug.jp/who/jalih/chat.jpg
Toimiva kahden pelaajan verkkopelituki Ansa-peliin oli yllättävän helppo lisätä.
Pelin logiikka on valmis ja loppu on kosmeettista: parempi käyttöliittymä, random aloituspaikat sekä lähtösuunnat pelaajille. Pelialueelle voisi myös randomilla laittaa esteitä, jotta pelialue muuttuisi jokaisella pelikerralla.
Mikäli ehdotukseni Ansapeli-tekoälystä kiinnostaa ketään, niin tarjoudun tekemään serveri-ohjelman kahden tekoälyn reaaliaikaista verkkopeluuttamista varten. Pelin seuraaminen onnistuisi graafisesti ja tekoälyn kehitysvaiheessa ohjelmaa voisi käyttää testaustyökaluna.
Ihan jännä ongelma olis koodata ohjelma, joka tulostaa oman lähdekoodin (lähdekoodin, ei mitään binäärimössöä). Kilpailla voi sitten vaikka ohjelman lähdekoodin lyhyydestä, mutta kielien väliset erot on kuitenkin liian suuria. C/C++:lla tälläisen ohjelman koodaaminen voi olla vaikeata, kun taas jollain tulkattavalla komentoriviskriptillä onnistuu helposti: cat $0.
En ole vielä itse kerennyt perehtyä ongelmaan, niin en osaa sanoa onko tollaisen koodaaminen C:llä mahdotonta vai kovinkin helppoa. Ehkäpä teitä kiinnostaisi, vaikkei sitten kilpailuksi sopisikaan :) Varmaan tätä on mietitty ennenkin, mutta joo.
Deffi kirjoitti:
C/C++:lla tälläisen ohjelman koodaaminen voi olla vaikeata
main(){char *c="main(){char *c=%c%s%c;printf(c,34,c,34);}";printf(c,34,c,34);}
Tuollainen oman lähdekoodinsa tulostava ohjelma tunnetaan nimellä Quine. Tuolta löytyy joitakin satoja esimerkkejä eri kielillä.
Deffi kirjoitti:
En ole vielä itse kerennyt perehtyä ongelmaan, niin en osaa sanoa onko tollaisen koodaaminen C:llä mahdotonta vai kovinkin helppoa.
Suunnilleen kaikilla kielillä se on kohtalaisen helppoa, jos ymmärtää perustana olevan teorian. http://en.wikipedia.org/wiki/Quine_(computing)
lainaus:
In some languages, an empty source file is a fixed point of the language, producing no output. Such an empty program, submitted as "the world's smallest self reproducing program", once won the "worst abuse of the rules" prize in the Obfuscated C contest.
Mielenkiintoinen yleistys: http://blog.sigfpe.com/2008/02/third-order-quine-in-three-languages.html
lainaus:
This is a Haskell program that outputs a Python program that outputs a Ruby program that outputs the original Haskell program.
Minä olen ehdotetun pokeri-tekoälyn tai robotwars tyylisen multiplayer robottitekoälyn koodauksen kannalla. Kummankin tekeminen on kiinnostanut jossain vaiheessa, mutta on jäänyt tekemättä.
Robotwarsista esimerkkeinä
http://necrobones.com/atrobots/
http://www.robotbattle.com/
Tuollaisen simulaattorin tekeminen on aika helppoa ja robottien ohjelmointikieli voidaan muokata esim. yksinkertaiseksi suomalaiseksi komentokieleksi.
Heh, tulipa tässä aamulla mieleen sellainen kuin liikennevaloäly. Äly yrittää ohjata liikennevaloja parhaansa mukaan, päästämällä mahdollisimman monta tienkäyttäjää risteyksestä/risteyksistä tietyn ajan sisällä. Auton läpipäästämisestä saisi yhden pisteen ja jalankulkijan kaksi. Jos autot törmäävät, menettää äly pisteen ja jos auto ajaa jalankulkijan yli, menettää äly kaksi pistettä. Kilpailun voittaja on se äly, jolla on eniten pisteitä.
Tästä saisi suhteellisen helpolla graafisen testiohjelman, jolla voisi mukavasti seurata älyjen toimintaa. Kilpailuun osallistumisen kynnys on myös aika matala, mutta hyvän älyn tekeminen vaatii jonkun verran optimointia.
Tuohan kuulostaa oikein hyvälle idealle. Olisi esimerkiksi risteys, jossa on 4 tietä ja jokaisen tien yli voi mennä jalan. Valojen ajastuksen pitää huomioida, että jalankulkija kulkee hitaamminen, kuin auto -> varoaika pitää olla suurempi. Yhtä aikaa voi kulkea useita autoja, sekä jalankulkijoita. Kuulostaa todella hienolle idealle.
Kuulostaa ihan mielenkiintoiselta...
Tämän ratkaisussa pystyisi kivasti käyttämään säikeitä. Tuli heti mieleen toteutus, missä jokainen liikennevalo, auto ja jalankulkija toimisivat itsenäisesti omissa säikeissään. Edellä mainitut kommunikoisivat toistensa kanssa käyttäen kanavia. Esimerkiksi jalankulkija lähettäisi liikennevalon kanavaan viestin, jonka jälkeen liikennevalo vastaisi onko valo punainen vai vihreä.
trilog kirjoitti:
Heh, tulipa tässä aamulla mieleen sellainen kuin liikennevaloäly. Äly yrittää ohjata liikennevaloja parhaansa mukaan, päästämällä mahdollisimman monta tienkäyttäjää risteyksestä/risteyksistä tietyn ajan sisällä. Auton läpipäästämisestä saisi yhden pisteen ja jalankulkijan kaksi. Jos autot törmäävät, menettää äly pisteen ja jos auto ajaa jalankulkijan yli, menettää äly kaksi pistettä. Kilpailun voittaja on se äly, jolla on eniten pisteitä.
Jossain vanhassa datatähdessä oli muuten tehtävä jossa piti tehdä liikennevalosimulaattori.
Mielestäni toi on muuten todella hieno systeemi, että kolarissa tai yliajossa menettää vain saman verran pisteitä kuin mitä onnistuessa saa. Kannattaa siis vetää ajoitus sen verran tiukalle, että keskimäärin yksi jalankulkija enemmän pääsee joka kierroksella yli, vaikka se tarkoittaisi että keskimäärin joka kolmannella kierroksella jalankulkija jäisi auton alle :D
Jos ajattelisi että hommassa pitäisi olla realismia, niin kolarista pitäisi menettää miljoona ja jalankulkijan yliajosta kymmenen miljoonaa pistettä. Tämä siis mikäli autoilijat ja jalankulkijat toimii sääntöjen mukaan, ja onnettomuudet johtuu valojen toimimattomuudesta.
Haittaohjelma kisa.. Kuka tekee vittumaisimman ohjelman mahdollisimman vähällä määrällä koodia?
Milloin on uutta kisaa tulossa?
Itse olen tuon liikennevaloäly:n kannalla. Myös semmoinen kisa olisi mukava, missä tehdään tekoäly Go peliin.
Aihe on jo aika vanha, joten et voi enää vastata siihen.