Keskustelu: Ohjelmointiputka: Pomppis-kilpailu alkaa!

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

nuubiX) kirjoitti:

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

Voitto olkoon siis minun ;)

nuubiX) 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.

nuubiX) 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.