Nyt uusi tehtävä on näkyvillä:
https://www.ohjelmointiputka.net/postit/tehtava.
Tämä tehtävä on haastavampi, mutta kaikki oikeaan muodostelmaan johtavat siirtosarjat hyväksytään.
Kysytään nyt että ymmärsinkö nyt varmasti oikein oikean alanurkan kirjain "A" on tämä mainostettu "tyhjä ruutu"?
Tuonhan piti vaihtua kuukausittain, mutta nyt on kulunut vasta viikko. En ehtinyt ratkaista ensimmäistäkään kun vasta eilen huomasin sen. Voisiko nuo vanhatkin tehtävät jättää saataville?
Mielestäni olisi myös hyvä idea lisätä tuonne se keskustelualue, jollaista joku jo ehdottikin. Ja niin että vain oikean vastauksen lähettäneillä on pääsy sinne.
JTS: Ymmärsit oikein. Tyhjän ruudun kohdalla on aina A-kirjain ruudukon pohjakuvioinnin takia.
Kaikki tehtävät ovat sivulla:
https://www.ohjelmointiputka.net/postit.php
Tämä tehtävä ilmestyi siksi jo nyt, koska ensimmäinen osoittautui varsin helpoksi. Ainakin aluksi tehtävien julkaisutahti on epäsäännöllinen.
182, mutta ainakin algoritmi on 100% oma... Pitänee koittaa parantaa vielä (tai no samapa tuo, kunhan en viimeiseksi jää ;)
Et jää. Minun satunnaislukuihin perustuva puolivalmis algoritmi on varmasti huonompi.
Onkohan Antilla haluja/mahdollisuuksia vertailla ensimmäisen putkapostin tuloksia, ja lähetellä eri vastauksia?
Erityisesti kiinnostaisi tietää kenen ratkaisu on otollisin Ordo-arvo ja kenen ratkaisu tekee nopeimmin 1-1000000 alueen.
Tämä toinen tuli sen verran nopeasti, että taidan passata sen.
P.S. Voisikohan putkapostin sykliä vähän pidentää, jotta päästään katsomaan eri ratkaisuehdotuksia, ja keskustelemaan niistä.
peran kirjoitti:
P.S. Voisikohan putkapostin sykliä vähän pidentää, jotta päästään katsomaan eri ratkaisuehdotuksia, ja keskustelemaan niistä.
Antti taisi sanoa tuossa edellisessä aiheessa, että tämä saattaa olla aluksi vähän epämääräinen, mutta sitten tämä vakiintuu kyllä.
Jotain vinkkiä voisi antaa tähän tehtävään. En ole näitä liikkuvien laattojen pelejä tottunut vääntämään.
Kahkonen kirjoitti:
Jotain vinkkiä voisi antaa tähän tehtävään. En ole näitä liikkuvien laattojen pelejä tottunut vääntämään.
Voithan ainakin aluksi kaivaa jostain vastaavankaltaisen pelin esiin (esim. sähköisessä muodossa hakukoneen avustuksella) ja yrittää etsiä jonkinnäköistä ratkaisumenetelmää vaikka käsin. Jos intoa riittää, tehokkaampien ratkaisujen löytämiseksi kannattanee tutustua yleisemmin tekoälyohjelmoinnin teoriapuoleen (internetistä löytyy).
Kaikki putkapostit jäävät arkistoon, eli ne voi ratkoa jälkeenpäinkin. Myöhemmin julkaistaan toki myös tehtävien ratkaisutapoja sekä sanallisina että koodiesimerkkeinä. Tarvittaessa voidaan antaa myös vinkkejä hankaliin tehtäviin.
Kyllä Antti on nyt kehitellyt kinkkisen tehtävän, jossa oma äly sopivan ohjelman myötäilemänäkään ei näytä pärjäävän tekoälylle. Mielenkiinnolla odottelen noita 54-siirron ratkaisuja.
Joo, erittäin mielenkiintoinen tehtävä. Ei tule omaan pieneen mieleeni suoraan mitään kuningasideaa tuon ratkaisemiseksi. Täytyy yrittää jotain tuossa viikonloppuna jos kerkeis.
Oikein hyvä tehtävä. Tälläkin kertaa tuli laadittua algoritmi kokonaan omin avuin, vaikka netistä löytyisi runsaasti apuja. Duunijutuissa ei kannata lähteä liikaa säveltämään itse ja tuhlaamaan siten aikaa, mutta tällaisten parissa on mukava testata omia taitojaan.
Taidan tyytyä tuohon tulokseen 78.
Hmm... millä nimellä tämän tyyppisiä pelejä edes kutsutaan?
Noista tehtävistä voisi olla linkit tänne keskusteluun...
Kahkonen kirjoitti:
Hmm... millä nimellä tämän tyyppisiä pelejä edes kutsutaan?
Olen ainakin yhdestä tekoälyn kurssiprujusta lukenut nimen liukupeli.
AI: A Modern Approach -kirjassa tämän tyyppisiä kutsutaan sliding-block puzzle -peleiksi. Suomennos voisi olla vaikkapa liukulaattapeli.
Antti Laaksonen kirjoitti:
Kaikki putkapostit jäävät arkistoon, eli ...
Tuo linkki arkistoon voisi olla myös Putkapostin tehtäväsivuilla eikä vain tällä kekustelualueella.
Sehän onkin, otsikossa nimittäin. "Putkaposti: "
Niinpä onkin. Se ei vaan näkynyt kuin viemällä kohdistin otsikon päälle. Siis ei näy sinisenä ja alleviivattuna kuten linkit yleensä.
Eikö se kannattaisi lisätä tuonne linkkiriville?
Tein tuossa Java-harjoituksena tuollaisen liukupelin:
http://cgi.evtek.fi/~k0101030/liukupeli/
Voi koittaa pärjääkö oma äly noille tekoälyille :)
Seuraavaksi vois alkaa miettiin sitä tekoälyy tohon
ajv kirjoitti:
Tein tuossa Java-harjoituksena tuollaisen liukupelin:
http://cgi.evtek.fi/~k0101030/liukupeli/
Voi koittaa pärjääkö oma äly noille tekoälyille :)Seuraavaksi vois alkaa miettiin sitä tekoälyy tohon
Kätevä ohjelma. Putkapostin ratkomista ajatellen varsin hyödyllisiä ominaisuuksia olisivat vielä UNDO-toiminto ja käytetyn siirtosarjan tulostaminen.
ajv kirjoitti:
Tein tuossa Java-harjoituksena tuollaisen liukupelin:
http://cgi.evtek.fi/~k0101030/liukupeli/
...
Aivan upea!
Mutta pakko on sanoa, että siinä on pieni bugi (toisinaan), eli joskus siinä pystyy siirtymään vinottain.
coaster kirjoitti:
Mutta pakko on sanoa, että siinä on pieni bugi (toisinaan), eli joskus siinä pystyy siirtymään vinottain.
Jep. Kahdesta kohtaa onnistuin tuossa: kohdasta (1, 1) kohtaan (2, 0) ja kohdasta (2, 2) kohtaan (3, 3) - jossa (0, 0) on vasen alakulma ja (3, 3) oikea yläkulma.
Tuo jälkimmäinen näyttäisi onnistuvan vain, jos siitä oikeasta yläkulmasta on siirretty palikka vasemmalle - alaspäin-siirron jälkeen ei bugaa.
Ja palikan saa myös hyppäämään yhden "yli".
Huppista joo :) Sallitut siirrot on taulukossa ja sen taulukon nollaaminen siirron yhteydessä oli unohtunu tehä loppuun... Nyt pitäs toimia paremmin.
Eikös niitä putkaposteja pitänyt tulla kuukausittain?
Kuukausittain ei tarkoita että uusi tulisi jokaisen kuukauden alussa.
No nyt on jo mennyt se kuukausi, jos tarkkoja ollaan :-P
Ei, ei ole. 14. päivänähän tämä tämänhetkinen alkoi.
Putkaposti alkoi 7. päivä, mutta tosin en ottanut huomioon sitä toista
Edelleenkin kuukausittain tarkoittaa enemmänkin kerran kuussa kuin kuukauden välein.
Älkääs nyt lapset kitiskö, vaan olkaa tyytyväisiä, että Antti viitsii tuollaisia pikku pähkinöitä edes tehdä!
Uusi tehtävä voisi tulla ensi viikon perjantaina. Sitä ennen kannattaa pohtia Datatähti-tehtäviä, etenkin toista ohjelmointitehtävää. Mitään tarkkaa rytmiä Putkapostilla ei siis edelleenkään ole.
Okei
Tässä olisi tällainen algoritmi:
1. Etsi kaikki mahdolliset tilanteet kymmenen siirron jälkeen ja pisteytä ne sen mukaan kuinka lähellä ratkaisua ne ovat.
2. Valitse paras, mutta älä siirry suoraan kymmenen siirron päähän, vaan tee ainoastaan yksi siirto.
3. Toista kohdasta 1, kunnes ratkaisu löytyy.
Minulla on tämä puolivalmiina C++-kielisenä, en ehkä saa sitä valmiiksi ennen seuraavaa putkapostia, mutta eihän sillä väliä.
Sainpas kaivettua sen 54 siirron ratkaisun esiin, kun viilailin algoritmin riittävän hyväksi ja annoin hitaan koneeni jauhaa pari tuntia. Kielenä C.
Pitäisiköhän heittää kone bruteforcettamaan pariksi päiväksi? :)
No, ainakaan pelkällä bruteforcella ei pärjää :) Siirtomahdollisuuksia on keskimäärin 2 kpl joka tilanteessa, joten eri siirtoyhdistelmiä on suunnilleen 2^54 = 18,014,398,509,481,984.
Ellei usko tuuriinsa, täytyy laskea todennäköisimmät vaihtoehdot ensin tai karsia epätodennäköiset kokonaan pois. Itse tein jälkimmäisen, ja sen virittelyssä se suurin homma olikin.
Ei toi mun algoritmi toiminut kovin tehokkaasti. Tulos oli 66 siirtoa. Jonkin verran siinä pystyisi viilaamaan, mutta lähtökohta on aika heikko. Etsin kaikki mahdolliset asetelmat viidentoista siirron jälkeen, mikä oli suunnilleen suurin mahdollinen syvyys. Kone pääsi noin kolmessa sekunnissa askeleen eteenpäin. Kun pisteytin eri asetelmia, huomasin, että kulmapalat olivat tärkeimpiä, sitten reunapalat ja keskipalat, jolloin annoin eri painoarvot niille.
jutti kirjoitti:
Tulos oli 66 siirtoa.
Et kuitenkaan lähettänyt sitä vastausta?
Ohjelmani tuotti ratkaisun, mutta itse ohjelmassa oli virhe, jota en ole korjannut. Korjaamalla virheen saatan parantaa tulosta.
Miksi siirtomahdollisuuksia on keskimäärin 2 kpl joka tilanteessa. Jos tyhjä ruutu on kulmassa, sen voi siirtää 2 paikkaan. Jos tyhjä ruutu on reunassa mutta ei kulmassa, sen voi siirtää 3 paikkaan. Jos tyhjä ruutu ei ole reunassa eikä kulmassa, sen voi siirtää 4 paikkaan. Eikös siirtovaihtoehtoja ole siten keskimäärin (4*2+8*3+4*4)/16=3 kpl joka tilanteessa?
Jaska kirjoitti:
Miksi siirtomahdollisuuksia on keskimäärin 2 kpl joka tilanteessa. Jos tyhjä ruutu on kulmassa, sen voi siirtää 2 paikkaan. Jos tyhjä ruutu on reunassa mutta ei kulmassa, sen voi siirtää 3 paikkaan. Jos tyhjä ruutu ei ole reunassa eikä kulmassa, sen voi siirtää 4 paikkaan. Eikös siirtovaihtoehtoja ole siten keskimäärin (4*2+8*3+4*4)/16=3 kpl joka tilanteessa?
Suuntaa, josta edellisen kerran siirrettiin ei kannata tutkia, koska siellä on jo käyty.
Ahaa. Oletin, että brute forcessa tätä seikkaa ei oteta huomioon. Nyt selkis. Täytyypi opetella määritelmät kunnolla.
Enpä minäkään tunne brute forcen määritelmää niin tarkasti, että tietäisin "saako" edellisen aseman jättää uusimatta. Laillinen siirtohan se on ja brute forceen käsittääkseni kuuluu kaikkien vaihtoehtojen testaaminen.
Joka tapauksessa edellisen aseman toistamatta jättäminen on ainoa triviaali keino pienentää laskentaurakkaa.
Onkohan mun ohjelmassa vieläkin joku virhe? Kun se tutkii kaikki tilanteet 15 siirtoa eteenpäin (ja siirtyy sen jälkeen yhden askeleen eteenpäin) saan tulokseksi 66, joka on paras saamani tulos. Kun syvennän hakua, tulos heikkenee.
Toinen juttu, jota en ole ottanut huomioon, on että muutamaa kirjainta on kaksi kappaletta. Periaatteessa se helpottaa ratkaisua, mutta perinteisessä pelissä, jossa on luvut 1 - 15, jos murtaa pelin ja vaihtaa kahden laatan paikkaa keskenään, pelistä tulee mahdoton (pienellä varauksella, luultavasti kaksi vierekkäistä vaihtamalla pelistä tulee mahdoton). Periaatteessa on mahdollista, että ohjelma yrittää vääntää laatat sellaiseen järjestykseen, jossa esim. O-kirjaimet ovat keskenään väärin.
jutti kirjoitti:
Onkohan mun ohjelmassa vieläkin joku virhe? Kun se tutkii kaikki tilanteet 15 siirtoa eteenpäin (ja siirtyy sen jälkeen yhden askeleen eteenpäin) saan tulokseksi 66, joka on paras saamani tulos. Kun syvennän hakua, tulos heikkenee.
Kuulostaa siltä, että pelitilanteiden paremmuuden arvioinnissa on puutteita. Taidat siis sulkea 54 siirron ratkaisun pois jo aiemmin, koska jokin muu siirtosarja näyttää algoritmisi mielestä lupaavammalta laskettaessa 15 siirtoa eteenpäin. Tuttu tilanne :)
jutti kirjoitti:
Onkohan mun ohjelmassa vieläkin joku virhe? Kun se tutkii kaikki tilanteet 15 siirtoa eteenpäin (ja siirtyy sen jälkeen yhden askeleen eteenpäin) saan tulokseksi 66, joka on paras saamani tulos. Kun syvennän hakua, tulos heikkenee.
Itse olin yllättynyt, että tuolla algoritmilla sait noinkin hyvän tuloksen aikaan. Tässä ongelmassa nimittäin hakuavaruus on niin iso ja ratkaisuja niin harvassa, että olisin kuvitellut tuon algoritmin tekevän paljon enemmän virhearvioita tai mahdollisesti jäävän jopa pyörimään silmukkaa. Eli lyhyesti: algoritmillasi kävi tuuri tuossa tavassa, missä se laskee vain 15 siirtoa eteenpäin.
jutti kirjoitti:
Toinen juttu, jota en ole ottanut huomioon, on että muutamaa kirjainta on kaksi kappaletta. Periaatteessa se helpottaa ratkaisua, mutta perinteisessä pelissä, jossa on luvut 1 - 15, jos murtaa pelin ja vaihtaa kahden laatan paikkaa keskenään, pelistä tulee mahdoton (pienellä varauksella, luultavasti kaksi vierekkäistä vaihtamalla pelistä tulee mahdoton). Periaatteessa on mahdollista, että ohjelma yrittää vääntää laatat sellaiseen järjestykseen, jossa esim. O-kirjaimet ovat keskenään väärin.
Olet aivan oikeassa. Ei ole ainoastaan periaatteessa mahdollista vaan myös ihan oikeasti. Tämän havaitsin yrittäessäni ratkaista peliä käsin ajv:n ohjelmalla. Tämä peli on käsin ratkaistaessa hankalampi kuin normaali liukupeli. Tämä ominaisuus saattaa tosiaan haitata sinun algoritmiasi merkittävästi.
Chiman kirjoitti:
Kuulostaa siltä, että pelitilanteiden paremmuuden arvioinnissa on puutteita. Taidat siis sulkea 54 siirron ratkaisun pois jo aiemmin, koska jokin muu siirtosarja näyttää algoritmisi mielestä lupaavammalta laskettaessa 15 siirtoa eteenpäin. Tuttu tilanne :)
Olen yrittänyt vaihdella tuota pisteytystä eri tavoin. Parhaimpaan tulokseen olen päässyt Manhattan-etäisyyden neliön summalla. Eli Manhattan-etäisyys on montako askelta yksi palikka liikkuu yhteensä pysty- ja sivusuunnassa päästäkseen oikeaan kohtaan mennäkseen oikeaan paikkaan (jos edessä ei olisi muita palikoita). Lasken jokaisen palikan Manhattan-etäisyyden, jonka neliöin. Neliöt summaan yhteen. Mitä suurempi luku, sitä huonompi tilanne.
Ennen neliöintiä kokeilin kaksinkertaistaa luvun, jos palikan oikea kohta oli jommalla kummalla sivulla ja nelinkertaistaa jos oikea kohta oli kulmassa. Tällä yritin, että reunat ja kulmat hoidettaisiin ensin. Sillä taisi olla myönteinen vaikutus tulokseen.
Neliöinnillä pyrin yleensä siihen, että parempi että kaksi palikkaa on etäisyydellä 2 oikeasta paikasta kuin yksi etäisyydellä 1 ja toinen etäisyydellä 3. Tälläkin oli myönteinen vaikutus.
Kokeilin myös pythagorealaista etäisyyttä, mutta tulos huononi. Palikkahan ei voi siirtyä vinoittain.
Ehkä osittainen spoilaaminen sallitaan, kun tehtävä on ollut näkyvillä jo 1,5 kk...
jutti kirjoitti:
Parhaimpaan tulokseen olen päässyt Manhattan-etäisyyden neliön summalla.
Tuo etäisyys saattaa olla paras pisteyttämistapa, mutta siinäkään tuskin kannattaa seurata vain yhtä, parhaalta näyttävää siirtosarjaa.
Itse toteutin pisteytyksen painottamalla oikeilla paikoilla olevia palasia sopivasti. Tuo oli erittäin kevyt laskennallisesti, kun keskittyi vain siirtyneeseen palaseen. Tosin jälkikäteen keksin yhtä kevyen tavan laskea tuo etäisyys. Et kai sinäkään laske kaikkien palojen etäisyyksiä joka askeleella? :)
Aihe on jo aika vanha, joten et voi enää vastata siihen.