Tuli mainittua tuolla eräässä säikeessä shakkitietokoneen pelialgoritmin suorittamisen mahdottomuus nykyaikaisella kotikäyttoon suunnitelulla mikrotietokoneella/läppärillä.
Onko täällä putkalaisilla ollut joskus jotain omia viritelmiä shakin pelailuun liityvissä algoritmeissä. Itse olen lähinnä olio-pohjaisesta lähestymistavasta lähestynyt asiaa ja alkeellisilla pelien pelaamiseen liittyvillä algoritmeillä tullen siihen, miten tietokonevastustaja tekee päätoksen seuraavasta siirrosta.
1. Lauta -tietotyyppi.
2. Jokaiselle pelinappulalle oma tietotyypin ohjelmointi, jossa on ohjelmoituna lailliset siirrot ja säännot.
3. Siirto - tietotyyppi, joka lähinnä on siirtohistorian arkistointia varten.
pelitilanne pitäisi jossain säilyttää, ja sitten pitäisi olla perillä enemmän koneoppimisesta, kun nykytietokone kotikäyttoon suunnitellut mikrotietokoneet eivät kykene siedettävässä ajassa laskemaan kaikkia mahdollisia pelitilanteita joka siirron jälkeen, kun lukumäärä on niin mahdottoman suuri, niin olen käyttänyt pelien pelaamiseen liittyvää min-max-tekniikkaa perustana jonkinlaisen shakkitietokoneen aikaansaamiseksi.
Min-max -tekniikka, jos se ei ole jollekulle tuttu, niin siinähän kaikki mahdolliset seuraavat siirrot pisteytetään ja sitten lasketaan erotus, ja siitä saadaan paras seuraava siirto, mutta se ei oikein shakissa ole kovin älykästä kun oma shakkitietokone -pelaa algoritmissä tietokone ei osaa ajatella, kuin seuraavan siirron eteenpäin, kun shakissa pitäisi ajatella pidemmälle.
4. Tietokoneelle pitäisi "opettaa" tiettyjä pelitilanne-kaavioita "patterns", joissa pelitilanteen tullessa eteen tietokone kykenisi tekemään päätoksen useamman siirron eteenpäin "ajatellen", mikä laajentaisi tuota min-max -tekniikan yhden päähän siirtoa ajattelua.
Minimaxissa voi määrittää, miten syvälle pelinkulkuja käydään läpi, eli ei ole rajoitusta, että voisi tarkastaa vain seuraavan siirron. Mitä syvemmälle siirtoja tutkitaan, sitä hitaammin algoritmi toimii.
Jere Sumell kirjoitti:
shakkitietokoneen pelialgoritmin suorittamisen mahdottomuus nykyaikaisella kotikäyttoon suunnitelulla mikrotietokoneella/läppärillä.
Miten niin mahdotonta?
Jo alkuperäiselle 4,7MHz 8088 perus-PC:lle oli muistaakseni shakkiohjelmia, joissa tietokoneella oli jonkinlainen pelialgoritmi. Jos nykyiset kotikäyttöön suunnitellut mikrot/läppärit on noin miljoona kertaa sitä nopeampia, niin miksi se nyt olisi mahdotonta?
Grez kirjoitti:
Jo alkuperäiselle 4,7MHz 8088 perus-PC:lle oli muistaakseni shakkiohjelmia, joissa tietokoneella oli jonkinlainen pelialgoritmi. Jos nykyiset kotikäyttöön suunnitellut mikrot/läppärit on noin miljoona kertaa sitä nopeampia, niin miksi se nyt olisi mahdotonta?
"Jonkinlainen", nimenomaan "jonkinlainen". Pelasin 80286 ekaa kertaa Chessmaster 2000 Level 9:issä ja voitin sen jo teini-iässä.
Jos sä mietit, että Shakissa on 10^120 erilaista peliä, tai 10^43 erilaista tilannetta pelilaudalla, ni ei edes IBM Think Blue, mikä pelasi sen aikaista huippupelaajaa Garry Kasparovia vastaan shakkia IBM:n supertietokoneen voimalla, niin kyennyt kuin yhteen tasapeliin, yhteen tappioon ja voittoon vai miten ne meni, mutta ihminen oli yhä etevämpi, sen hetken ihmisen historian taitavimpana venäjältä tulevaa shakkimestaria vastaan sitä, ja siitäkin on salaliittoteorioita jonkin dokumentin näin televisiossa, että siellä olisi jotkin IBM:n tietokoneinsinöörit keskeyttäneet suljettujen ovien takana algoritmin, kun kone olisi tehnyt ihmisaivoja huonompaa siirtoa. Ei sekään käynyt läpi 100% analyysia kaikista seuraavista siirroista, koska suoritusaika ei ole siedettävä edes IBM:n supertietokoneilla.
No,mulla on shakkikavereita oikeassa elämässä, ja mut on kutsuttu Turun Työväen shakkikerhon jäseneksi, mutta Korona hidastanut sitä osallistumista, enkä ole salaliittoteorioiden ystävä, vaikka jotain niitä seuraankin reaalielämän ilmentymien suhteen, mutta jos sä kuvittelet noiden pelitilanteiden lukumäärän, kun algoritmin aikaratkeavuus on syötekoko pahimmassa tapauksessa, niin eihän se ole kelvollista toimintaa nyky-kotitietokoneille, kun ei ole järjellisessä ajassa ratkaistavissa vielä supertietokoneillakaan.
Kyllähän niitä on varmaan 8080-arkkitehtuurin ajoista ollut jonkinlaisia shakkiohjelmia, ja itsekin aloitin Chessmaster 2000 pelaamisen 80286 -PC -tietokoneella, mutta eihän ne mitään 100% käy kaikkia pelitilanteita läpi joka siirron osalta.
Chess.com -sivustolla ne kerää big dataa kaikkien pelaajien peleistä, ja epäilen, että ne kehittää sitä CPU-pelin tietokonevastustajaa koneoppimisen algoritmin keinoin pohjaten big dataan louhien kaikista peleistä sitä dataa, jota käytetään perusteena päätöksiin tietokonesiirtoihin.
Antti Laaksonen kirjoitti:
Minimaxissa voi määrittää, miten syvälle pelinkulkuja käydään läpi, eli ei ole rajoitusta, että voisi tarkastaa vain seuraavan siirron. Mitä syvemmälle siirtoja tutkitaan, sitä hitaammin algoritmi toimii.
Rekursiotahan siinä tulee, kun lähtee seuraavasta siirron pelitilanteista pohtimaan sitä seuraavaa siirtoa.
Oppisin ton minmaxin 9 ruudun ristinollasta, joka vielä jotakuinkin helppo ymmärtää, mutta shakkialgoritmissa ajattelee kaikkien tilanteiden kompleksista kokonaisuutta seuraavaa siirtoa pohtiessa, ja ajattelee jotain leveyshakua, jossa käytettävällä heuristiikalla ei ole niinkään merkitystä, niin tulee äitiä ikävä algoritmiä ajettaessa nyky-kotimikrotietokoneilla/läppäreillä, vaikka nämä nyt verrattain ihan käypiä pelejä tssä kotioloissa siinä, mihin me ihmiset tarvitsemme näitä arkikäytössä.
Todellisuudessa epäilen, että shakkitietokoneissa jossain IBM -think Bluessa tai vastaavissa käytetään ajankulun vähentämiseksi syvyyshakua, joka ei sitten käy läpi koko hakuavaruutta, ja sitten siinäkin on se heuristiikka, joka säädetään, niin päätetään ennen siirtopohdintaa valmiiden jo koneelle opetettujen tai reaaliajassa suhteessa vastustajan patterns, tilannekaavioihin.
Voi olla, että IBM on tolla Think Blue -tietokoneella aluksi brute-forcettanut kaikki mahdolliset tilanteet kaikessa hiljaisuudessa, ja sittenhän sen jälkeen seuraavien siirtojen louhinta big datasta nopeutuu, kun ei tarvitse kaikkea enää laskea nollasta.
Jere Sumell kirjoitti:
Chess.com -sivustolla ne kerää big dataa kaikkien pelaajien peleistä, ja epäilen, että ne kehittää sitä CPU-pelin tietokonevastustajaa koneoppimisen algoritmin keinoin pohjaten big dataan louhien kaikista peleistä sitä dataa, jota käytetään perusteena päätöksiin tietokonesiirtoihin.
Samainen shakkisivusto myös jäljittää pelihuijareita vertaamalla heidän siirtojaan (siirtojen sarjoja) tunnettujen shakkirobottien siirtovalikoimiin. Näin siksi, että robotin siirtoja kopioimalla on helppo voittaa jopa shakin mestaripelaajia, koska tietokonealgoritmit ovat ylivertaisia.
Jere Sumell kirjoitti:
ajattelee jotain leveyshakua, jossa käytettävällä heuristiikalla ei ole niinkään merkitystä, niin tulee äitiä ikävä
Min max voidaan tehdä myös syvyyshaulla ja/tai rajata heuristiikalla tai ohjata välissä siirtosarjoilla useamman tason yli. Selviä rajauksia ovat esimerkiksi, että ei peruta edellisiä siirtoja ja ei jatketa merkittäviin menetyksiin johtavia hakuja.
Miten tuon min-max-tekniikan voisi soveltaa syvyyshaulla shakissa?
Helpoiten alkuun pääsee varmaan minimaxilla ja evaluointiin käyttää materiaa (solttu = 1, lähetti/ratsu = 3, torni = 5, kuningatar = 9). Lisäksi, noissa shakkisoftissa yleensä käytetään AB-heuristiikkaa jossa tiettyä oksaa ei evaluoida pitemmälle, jos on jo löydetty parempi.
Jere Sumell kirjoitti:
Miten tuon min-max-tekniikan voisi soveltaa syvyyshaulla shakissa?
Pikemminkin kysyisin, miten olisit tehnyt sen leveyshaulla.
Minimax (min-max, MinMax, ...) yleensä toimii selvimmin juuri syvyyshaulla tähän tyyliin:
minimax(syvyys, vuoro, tilanne):
jos syvyys on maksimi tai peli on päättynyt:
pisteet = arvio tilanteen pistearvosta
muuten:
jatkopisteet = minimax(syvyys + 1, käännä vuoro, jatko) jokaiselle jatkolle
pisteet = vuorossa olevan kannalta parhaat jatkopisteetAlgoritmin nimen min ja max tapahtuvat varsinaisesti tuossa kohdassa ”itselle parhaat pisteet”: jos pelitilanteet pisteytetään pelaajan 1 näkökulmasta, pelaaja 1 yrittää maksimoida pisteet ja pelaaja 2 yrittää minimoida pisteet.
Tässä voi siis jättää osan pelitilanteista käsittelemättä, eli ”tutki jokainen jatkotilanne” muuttuukin muotoon ”tutki jatkotilanteet, joissa ehto X toteutuu” tai ”tutki jatkotilanteet, jotka saadaan näillä siirtovaihtoehdoilla” tai vaikka ”tutki satunnaisesti 10 jatkotilannetta”.
Varsinainen ”shakkitietokone” tuosta tulee vasta, kun jatkotilanteiden käsittelyä rajataan merkittävästi jollain shakkiin liittyvällä lisätiedolla. Itse en osaa shakkitaktiikoita, mutta isolla ruudukolla pelattavan 5 riviin -ristinollan tapauksessa hakuvaihtoehtoja voi rajata esimerkiksi näillä: Uudet merkit laitetaan vain lähelle vanhoja (ei mihinkään monen ruudun päähän). Selvästi tunnistettavat umpikujat hylätään heti alkuun. Tietyistä kuvioista voidaan tunnistaa välitön voiton (tai häviön) mahdollisuus, ääriesimerkkinä jos on jo 4 rivissä, seuraava siirto on pakko tehdä sen rivin päähän.
Metabolix kirjoitti:
ääriesimerkkinä jos on jo 4 rivissä, seuraava siirto on pakko tehdä sen rivin päähän.
Eikös se ole jo 3 jälkeen, jos molemmat päät on muuten vapaat, eikä itsellä ole mahdollisuutta voittaa 2 vuorolla.
Metabolix kirjoitti:
Pikemminkin kysyisin, miten olisit tehnyt sen leveyshaulla.
Molemmissa hauissa tietokoneohjelma pitää valjastaa ymmärtämään, mikä siirroista lopulta on edullisin tehdä seuraavaksi, ja erityisesti syvyyshaussa myös se, mistä tilanteesta ja strategisesta näkökulmasta lähdetään siihen pinoon niitä seuraavan siirron mahdollisuuksia lisäämään.
Leveyshaku löytää ratkaisun varmasti, kun sehän käy koko hakuavarauuden läpi, mutta shakin katlaisessa pelissä kun jokainen siirto ei todellakaan ole yhtä hyvä on parempia siirtoja ja huonompia siirtoja, niin tuossa leveyshaussa sitä käyttämällä voidaan säästää aikaa, jos ollaan määritelty ensin se, mikä seuraavan siirron tavoite on.
Kuten Metabolix -totesit, shakkitietokoneessa valmiiksi määritellyiden strategioiden osuus on tärkeä, ja myös aloitukset ja vastustajan vasta-aloitus riippuen siitä sitten, pelaako tietokone valkeilla vai mustilla. Ohjelman pitäisi myös mukautua pelitilanteeseen ja tarvittaessa osata vaihtaa strategiaa, esimerkiksi strategiaa pitää pystyä vaihtamaan, jos joutuu alakynteen hyökkäysasemista.
Aloitussiirroista kokoemukseni mukaan ihmispelaajilla on tuo uraus kuningattarelle E2-E4, siinähän uraus tapahtuu myös lähettiläälle, ja aika usein vasta-siirto eli vastustajan aloitus on moukku vastaan sieltä mustista.
Yksi ja sitten sellainen huomio, että vaikka pelin tavoite on tehdä vastustajasta shakki-matti, niin pelin lopetukseen kanssa pitäisi olla tietokoneelle ymmärrettävät mallit, ja jos jossain vaiheessa näyttää että mattia ei tule saamaan ilman totaalista vastustajan hoaksisiirtoa, tai käytettävissä olevilla nappuloilla shakkia ei saa, niin sitten kone osaisi ehdottaa tasapeliä tai luovuttaisi.
Vielä lisää shakkitermistöä. Uraus tulikin jo aloituksissa, mutta sitten uhraus-siirrot pitäisi ja valjastaa koneelle, että jossain tilanteessa samanarvoisen napin uhraus vastustajalta pelistä pois samalla itse menettäen uhrina sen, niin joskus voi olla lopputuloksen kannalta järkevää, aina ei.
Jatkan vielä vastaustani, kun pyörittelin vielä tätä aihetta kävelylenkilläni kun hain R-kioskilta punaisen minisikari-askin.
Helposti rivien välistä luettaessa edellisen vastaukseni saa sen johtopäätelmän helposti, että yritän hahmottaa shakkiohjelmaa tietokoneella strategioiden kautta, jolloin yksittäisellä siirrolla ei välttämättä ole suurta merkitystä.
Shakissahan on, mitä siihen ihan päivätöikseen paneutuvia tutkijoitakin akateemisessa maailmassa on, niin paljonkin tosiaan tunnettuja strategioita, ja niihin sitten vastine-siirtoja, kun tiedetään, mihin strategia pahimmillaan tai parhaimmillaan johtaa ja sen mukaan ohjelma osaisi luovia siirtojaan itselle eduliisimalla tavalla.
Ongelmia tuossa omassa lähestymistavassani on vain se, jos strategia-vastastrategia -periaattella tietokone osaisi ajatella peliä ja pelata sitä, jos vastustajana on jokin sellainen ihmisvastustaja, joka pelaa jotenkin sellaisella strategialla, joka ei ole entuudestaan yleisesti tunnettu, tietokone-ohjelmahan ei tällöin kykenisi tunnistamaan sitä, eikä osaisi näin ollen tehdä vastasiirtoa. Siinä kohtaa päädytään helposti siihen, että pitäisi ajatella siirto siirrolta sitä pelin päättämiseen johtavaa siirtelyä.
Tuo Chess.com -sivusto mielekäs opetusmielessä, ja vaikka olen pelannut siellä joidenkin reaalimaailman shakkikavereideni kanssa tietokoneella shakkia, niin tuo tietokonepelaaja on aika haastava, täytyy myöntää, että en ole voittanut vaikeusasteeltaan vitostasosta ylöspäin kertaakaan tietokonetta. Fysiikan laitoksen opiskelija-ainejärjestössä joku kertoi minulle kerran, että on yltänyt 7-tason voittamaan, mutta hänkään ei ollut kuullut ketään, ketä olisi voittanut tuolla maksimi-vaikeusasteella tuota chess.comin tietokonepelaajaa. Varmaan monikin on, itse en ole keskiverto harrastepelaajaa ihmeempi shakin pelaaja.
Shakissakin, jos ottaisi asiaksi ja paneutuisi peliin ja käyttäisi aikaa siihen paljon ottaa haltuun syvemmin kyseistä peliä, niin voisi kehittyä paremmaksi pelaajaksi, ja siinäkin auttaa vertaistuki jonkun saman henkisen pelaajan kanssa, joka mahdollisesti on kokeneempi pelaaja, kuin itse. Jokin tuollainen shakkikerhon jäsenyys voi olla sellainen väylä löytää sellaisia kavereita oikeassa elämässä.
Jere Sumell kirjoitti:
Leveyshaku löytää ratkaisun varmasti, kun sehän käy koko hakuavarauuden läpi,
Yritinkin kysyä, miten olisit tehnyt minimax-algoritmin leveyshaulla, kun minimax ideansa puolesta toimii rekursion kautta eli syvyyshaulla.
Metabolix kirjoitti:
Jere Sumell kirjoitti:
Leveyshaku löytää ratkaisun varmasti, kun sehän käy koko hakuavarauuden läpi,
Yritinkin kysyä, miten olisit tehnyt minimax-algoritmin leveyshaulla, kun minimax ideansa puolesta toimii rekursion kautta eli syvyyshaulla.
Tuossahan leveyshaussa on tietorakenteena jono, johon lisätään ne seuraavat reitit. Ongelmallista on, jos tuo hakuavaruus tulisi lisätä jonoon kokonaisuudessaan joka siirron osalta, kun mahdollisten pelitilanteiden lukumäärä niin suuri.
Jos tietokoneelle valjastaisi jonkin tavoitteen seuraavalle siirrolle, että voisi todeta "riittävän hyvä":n siirron loydyttyä tietokone tekisi päätoksen.
Jonoon kun lisää niitä seuraavia siirtokandidaatteja, niin voisi olla edullista, että jono, mikä on tietokoneohjelmassa myos taulukkona toteutattivssa, niin jos sen järjestäisi sen mukaan, miten edullisia siirrot tuon min-max-tekniikan osalta on. Käyttäisi jotain nopeaa lajittelualgoritmiä.
Leveyshaku min-max -tekniikalla mielenkiintoinen.
1. Määrittele siirron tavoite
2. Valitse leveyshaun aloitusalkio jostain sellaisesta nykytilanteen nappulasta, joka voidaan olettaa edulliseksi itselle.
3. Lopeta siirtojen jonoon lisääminen siinä kohtaa, kun tavoite on saavutettu, loppupiste.
4. Lajittele pisteytetty siirto-jono suuruusjärjestykseen sopivalla lajittelualgoritmilla.
5. Tee siirto.
Sittenhän kun siirron tavoite on selvä, mihin pelitilanteeseen tietokoneohjelman haluaa pelin siirtyvän, niin sittenhän kaikkia pelitilanne-mahdollisuuksia ei tarvitse käydä läpi, jolloin aikaa säästyisi.
Mutta voi olla aika ongelmallista tuo siirron tavoite määritellä.
Sittenkin voisi saada siedettäviä siirron "miettimisaikoja" -tietokonepelaajalle, jos rajaisi sen alueen siedettävän kokoiseksi, kuinka monta siirtoa eteenpäin niitä siirtokandidaatti-alkioita tuohon jonoon -taulukkorakenteeseen lisätää ennen sen lajittelua. Ihmismielihän shakkia pelatessa on rajallinen, eikä ihminenkään koko loppupeliä välttämättä kykene käymään ennakolta läpi.
Jere Sumell kirjoitti:
Leveyshaku min-max -tekniikalla mielenkiintoinen. – –
Harmi vain, että kuvailemasi algoritmi ei ole Minimax-algoritmi vaan ihan pelkkä leveyshaku tai enintään A*-tyyppinen heuristinen reitinhaku. Tuollainen haku johtaa väärään lopputulokseen, koska vastustaja voi pelata tekemääsi ”oletusta” paremmin tai ylipäänsä voi tehdä sattumalta siirron, joka estää hakemasi ”tavoitteen”.
Minimax on tuo aiemmin kuvaamani algoritmi, jossa reitinhaku huomioi, että vastustaja valitsee aina vastakkaisen vaihtoehdon. Minimaxissa jokaisen valinnan hyvyyttä arvioidaan sen perusteella, mihin tilanteeseen se pahimmillaan johtaa myöhemmissä siirroissa, ja tähän tarvitaan se syvyyshaku, joka tutkii myöhemmät siirrot saman tien. Leveyshaku käsittelee myöhemmät tilanteet vasta viimeiseksi eikä pysty algoritmin aikana rajaamaan hakua niiden mukaan.
Jere Sumell kirjoitti:
Jonoon kun lisää niitä seuraavia siirtokandidaatteja, niin voisi olla edullista, että jono, mikä on tietokoneohjelmassa myos taulukkona toteutattivssa, niin jos sen järjestäisi sen mukaan, miten edullisia siirrot tuon min-max-tekniikan osalta on. Käyttäisi jotain nopeaa lajittelualgoritmiä.
Ensinnäkin, kuvaamasi leveyshaun yhdistelmä ei taida antaa lisäarvoa pelkkään Minimaxiin nähden. Toiseksi, jos halutaan vain ”järjestetty jono”, koko listan järjestäminen on turhaa ja oikea ratkaisu on prioriteettijono eli keko, jossa lisäys ja poisto ovat logaritmisia ja paras löytyy aina kärjestä.
Hyviä huomioita!
Tiedostan itsekin ongelmani tuossa esityksessäni. Onhan niitä. Tämä shakin pelaaminen yksi pienimmistä ongelmistani elämässäni.
Breadth search min max -loytyy jonkin verran resursseja netistä, AI -tekoälyn ohjelmointii liittyvistä algoritmeistä minulla ei ole tarpeeksi tietoa, eikä kone-oppimiseen liittyen, joten en osaa ottaa kantaa sen kummemmin tämän osalta tai ainakaan mitään lisä-arvoa tuottavaa keskusteluun tuoda toistaiseksi.
pitänee opiskella lisää.
Jere Sumell kirjoitti:
pitänee opiskella lisää.
Onneksi netistä löytyy shakkiohjelmointiin ihan oma wiki ja kovimmat botit ovat avointa lähdekoodia.
Leela Chess Zero on avoin toteutus Alpha Zerosta, joka käyttää Monte Carlo -puuhakua ja neuroverkkoja.
Vielä muutama vuosi sitten Stockfish perustui perinteisiin haku- ja evaluaatiomenetelmiin, mutta viime vuonna sekin siirtyi nykyaikaan.
Noissa esittämässäsi resursseissa puhutaan neuraaliverkoista. Onko ne jotenkin nouseva trendi tällä hetkellä, kun totesit, että tuo Stockfishkin viime vuonna siirtynyt "nykyaikaan". Neuraaliverkot on jokseenkin vieraita itselleni, joskin nuo graafiesitykset tutumpia.
Shakin pelaaminen voidaan yleisesti nykytiedossa luokitella kelvottomaksi ongelmaksi, johon ei toistaiseksi ole loydetty polynomaalisessa ajassa suoriutuvaa ratkaisualgoritmia. Lähimmäksi taidetaan päästä käyttämällä likimääräis-algoritmeja.
Tuo Graafi-esitys tulee yliopisto-opinnoissa tietojenkäsittelyssä käsitellään noiden perinteisten leveys- ja syvyyshakujen yhteydessä, ja sitten se termisto tulee tutuksi joitain lentoreittejä tarkastelemalla ja sitten jokin shakin lisäksi kelvottomalla ongelmalla, matkustavan kauppamiehen ongelma, johon siihenkään ei ole loydetty varmaan vielä ratkaisua. Vieko neuraaliverkkojen maailmassa esitetyt mallit ja hypoteesien ympärillä vellova keskustelu eteenpäin tätä käsitystä, vai onko se jo todella vanhentunutta tavaraa.
En tiedä, tuleeko opinnoissani vastaan millään kurssilla muuta kuin pintapuolisesti neuraaliverkot, kun taas jatkuu ensi syksynä.
Jere Sumell kirjoitti:
Noissa esittämässäsi resursseissa puhutaan neuraaliverkoista. Onko ne jotenkin nouseva trendi tällä hetkellä, kun totesit, että tuo Stockfishkin viime vuonna siirtynyt "nykyaikaan".
Oletko kuullut AlphaGosta? Se oli ensimmäinen tekoäly, joka ohitti ihmisten pelitason gossa. Tämä tapahtui vasta 2016, paljon myöhemmin kuin shakissa.
Perinteiset syvyyshaut eivät koskaan pärjänneet kovin hyvin gossa, koska hakupuu haarautuu paljon nopeammin kuin shakissa. Ensimmäinen läpimurto gossa oli Monte Carlo -puuhaku eli MCTS, joka julkaistiin 2006. Se ei kuitenkaan yksinään riittänyt voittamaan parhaita ihmispelaajia. AlphaGo käyttää MCTS:n lisäksi neuroverkkoja, jotka nostivat pelitason ihan omaan luokkaansa.
AlphaGon jälkeen näitä ideoita sovellettiin muihinkin (lauta)peleihin. Tuloksena oli mm. AlphaZero, joka oli hetken aikaa ehkä maailman vahvin shakkitekoäly, ja tuo vapaan lähdekoodin toteutus jonka mainitsin.
Stockfishin ja AlphaZeron väliset pelit ovat todella mielenkiintoisia. Kannattaa katsoa vaikka YouTubesta analyysejä, jos shakki kiinnostaa.
Jere Sumell kirjoitti:
Shakin pelaaminen voidaan yleisesti nykytiedossa luokitella kelvottomaksi ongelmaksi, johon ei toistaiseksi ole loydetty polynomaalisessa ajassa suoriutuvaa ratkaisualgoritmia.
Onko jotain syytä olettaa, että polynomiaikainan ratkaisu (suhteessa laudan kokoon?) olisi olemassa?
Wikipedian mukaan jokin shakin yleistetty versio on EXPTIME-complete: https://en.wikipedia.org/wiki/Game_complexity#Complexities_of_some_well-known_games
jlaire kirjoitti:
Onko jotain syytä olettaa, että polynomiaikainan ratkaisu (suhteessa laudan kokoon?) olisi olemassa?
No nykytiedon valossa shakin pelaaminen liittyy expotentiaalisen aikavaativuuden algoritmiin, ja voihan hypoteesin asettaa "Shakin pelaamisen ongelman ei tarvitse olla expotentiaalisen aikamääreen omaavan algoritmin ratkaisu, vaan se on lähempänä polynomaalista", mutta itse en osaa argumentoida tuohon, varmaan jos olisi olemassa jotain ratkaisuja, ne olisi jo tiedossa. Ei se ainakaan näillä perinteisillä syvyys- ja leveyshaun käytöllä, sama mitä heuristiikkaa käyttää ja vaikka soveltaa min-maxia, kuten totesit, neuroverkko-malleja soveltavat peliohjelmat ovat tehokkaampia, täytyy varmaan haarautua syvenemään niihin enemmän?
Kysyin, mitä mielestäsi pitäisi pitää algoritmin syötteenä. Jos pelipuun kokoa, sysvyyshaku on jo polynomiaikainen. Jos syötteenä on pelilaudan koko, en nää mitään järkeä olettaa, että tehokasta algoritmiä on olemassa.
Mutta jos nyt puhutaan pelkästään 8x8-laudalla pelattavasta normaalista shakista, pelin ratkaisemisen aikavaativuus on triviaalisti O(1) koska syöte on vakio.
Lisäys: Pelkästään muutaman nappulan loppupelit ovat jo erittäin vaikeita, eikä niihin ole tiedossa mitään yleispätevää taikatemppua. Niitä ratkaistaan käymällä kaikki asemat läpi. Seitsemän nappulan asemia voi tutkia täällä: https://syzygy-tables.info/
Jos keksit tehokkaan tavan ratkaista edes 4 nappulan asemat optimaalisesti ilman hakua tai isoa lookup-taulua tai suurta määrää käsinkirjoitettua purkkaa, se olisi iso saavutus.
jlaire kirjoitti:
Kysyin, mitä mielestäsi pitäisi pitää algoritmin syötteenä. Jos pelipuun kokoa, sysvyyshaku on jo polynomiaikainen. Jos syötteenä on pelilaudan koko, en nää mitään järkeä olettaa, että tehokasta algoritmiä on olemassa.
Takaisin siitä, mistä lähdin tämän keskustelusäikeen avausviestissä liikenteeseen hypoteesina: "Nykyaikaisella mikrotietokoneella (2021) tai supertietokoneella ei voi pelata sellaisella algoritmilla shakkia, joka tekisi 100% -analyysin joka siirron jälkeen ja pohjaisi siirron sitten itselle edullisimpaan siirtoon". Käytän nyt pahinta tilannetta tuossa algoritmin syötekokona, eli pelitilanteiden lukumäärää laudalla kaikki mahdollisuudet 10^43. Kaikki olemassa olevat ihmisen ohjelmoimat shakkitietokoneet hyödyntävät likimääräis-algoritmejä nykyään, joissa on täytynyt tinkiä jostain jonkun toisen resurssin kustannuksella.
Aika metkaa, jos miettii, että tällaisen ratkaisun joku joskus kykenisi esittämään, että olisi mahdollista pelata tuollaista tietokoneshakkia, niin sitten kun tietokone voittaa 100% varmuudella ihmisen, niin herää kysymys, onko tietokone sittenkään "viisampi" kuin ihminen, kun tietokoneohjelma on kuitenkin ihmisen aivotyösketelyn tulosta ja lähdekoodin laatiminen on käsityötä, ohjelmointiprosessia ei voi automatisoida, tietokonetta ei voi valjastaa ohjelmoimaan itseään noin niinkuin yleisesti.
Se, että ihminen omalla toiminnallaan ohjelmoi jotain, niin minkälaisia seurauksia siitä on ylipäätään ihmisen reaalimaailmassa, niin jos ajattelee jotain sotateollisuuden sovelluksia, niin pahimmassa tapauksessa ihminen voi saada jossain vaiheessa tekoälyn kehittyessä suurtakin tuhoa aikaan, ja pahimpana skenaariota voidaan pitää ihmisen häviämistä sukupuuttoon lopulta.
Jere Sumell kirjoitti:
[...] niin sitten kun tietokone voittaa 100% varmuudella ihmisen [...]
1) Täydellinen peli ei takaa 100% varmaa voittoa. Ihminenkin voi teoriassa pelata täydellisesti.
2) Todennäköisyys on käytännössä ollut jo pitkään 100%.
Minusta alkaa tuntua, ettet ole lainkaan kiinnostunut shakkitekoälyistä vaan pelkästään filosofisesta jaarittelusta.
"Valtavan hakuavaruuden läpikäyminen vaatii paljon aikaa" ei ole kovin syvällinen havainto.
jlaire kirjoitti:
Jere Sumell kirjoitti:
[...] niin sitten kun tietokone voittaa 100% varmuudella ihmisen [...]
1) Täydellinen peli ei takaa 100% varmaa voittoa. Ihminenkin voi teoriassa pelata täydellisesti.
Turhaa saivartelua, kun tässä oli tarkoitus sanoa ettei voi hävitä ihmiselle. Shakissa myös tasapeli on mahdollinen tulos. Jere ei taida olla mikään shakkiekspertti, mikä vähentää tämän "pohdiskelun" mielekkyyttä entisestään.
jlaire kirjoitti:
2) Todennäköisyys on käytännössä ollut jo pitkään 100%.
Minusta alkaa tuntua, ettet ole lainkaan kiinnostunut shakkitekoälyistä vaan pelkästään filosofisesta jaarittelusta.
"Valtavan hakuavaruuden läpikäyminen vaatii paljon aikaa" ei ole kovin syvällinen havainto.
En nyt tiedä filosofisesta jaarittelusta, korkeintaan maallikkofilosofi -tasolla.
Kyllä olen kiinnostunut shakkitekoälystä, muttta tietämykseni siihen liittyvistä aiheista ei vie enää tätä keskustelua tämän pidemmälle, mitä olen tuonut esiin täällä.
muuskanuikku kirjoitti:
Jere ei taida olla mikään shakkiekspertti, mikä vähentää tämän "pohdiskelun" mielekkyyttä entisestään.
On totta, että en ole mikään shakkiekspertti, kuten aiemmin todettua, olen keskivertoa harrastepelaajaan tasoa, enkä pelaa edes päivittäin tai viikottainkaan ottelua.
Kuten edellisessä postauksessa totesin, tietämykseni tästä shakkitekoäly-kehitysasiasta ei vie enää tätä pidemmälle tätä keskustelua, mitä tässä nyt olen tuonut esiin, nyt on joidenkin muiden vuoro jatkaa keskustelua, ja siirryn kuuntelu-oppilaaksi tämän aiheen tiimoilta, jos vaikka oppisin jotain uutta.
Aihe on jo aika vanha, joten et voi enää vastata siihen.