Shakista

Seuraa 
Viestejä45973
Liittynyt3.9.2015

Joo, Suomi voitti, hyvä niin. Tuon ensimmäisen shakkialgoritmini väänsin joskus C64:n assemblerilla, ja se oli jo melko kovatasoinen pelaaja. Sitten shakin olemusta on tullut fundeerattua joku vuosikymmen, ja suppeni lopulta yhdelle A4-arkille.

Sanotaan, että yksinkertaisuus on kaunista, niin myös shakissa. Jokaisen nappulan arvo on tasan nolla, paitsi jos se pystyy liikkumaan yhden ruudun, sen arvo on heti kokonaiset yksi. Elon laskuopilla voidaan havaita, että tyhjällä laudalla daami voi parhaimmillaan liikkua 27 ruutuun. Edelleen torni voi liikkua 14 ruutuun, etc.

Ratkaisu on kaksoisrekursio, valkea kutsuu mustan siirtoa, musta kutsuu valkean siirtoa, jne. Vertailun vuoksi maailman parhaat shakkimestarit kykenevät ajattelemaan tätä litaniaa parhaimmillaan 16-18 puolisiirtoa eteenpäin. Kuitenkin sillä rajoituksella, että ihmisen mieli ja intuitio karsii muunnelmasta kaikki älyttömyydet pois, vaikka jokin käsittämättömän typerältä näyttävä uhraus saattaisikin johtaa pikkuhiljaa vastustajan saattohoitoon.

Karkeana pseudokoodina kaksoisrekursio on suunnilleen seuraavanlainen:

[code:2iz2jxpk]int mustan siirto(syvyys, lopetussyvyys, laudan asema, siirot *muunnelma)
{
plaraa kaikki mustan siirrot taulukkoon
jos (valkean Kaarle lyötiin) palauta mustan voitto
jos (syvyys = lopetussyvyys)
{
palauta mustan siirtovaihtoehdot - valkean siirtovaihtoehdot
}
int aseman arvo = tosi hyvä
for (laskuri=0; laskuri < kaikki siirrot; laskuri++)
{
tee siirto(siirrot[laskuri], laudan asema)
int uuden aseman arvo = valkean siirto(syvyys+1, lopetussyvyys, laudan asema)
jos (uuden aseman arvo < aseman arvo)
{
aseman arvo = uuden aseman arvo
muunnelma[syvyys] = siirrot[laskuri]
}
palauta asema ennalleen(siirrot[laskuri], laudan asema)
}
palauta asema arvo
}

int valkean siirto(syvyys, lopetussyvyys, laudan asema, siirot *muunnelma)
{
plaraa kaikki valkean siirrot taulukkoon
jos (mustan Kaarle lyötiin) palauta valkean voitto
jos (syvyys = lopetussyvyys)
{
palauta valkean siirtovaihtoehdot - mustan siirtovaihtoehdot
}
int aseman arvo = tosi huono
for (laskuri=0; laskuri < kaikki siirrot; laskuri++)
{
tee siirto(siirrot[laskuri], laudan asema)
int uuden aseman arvo = mustan siirto(syvyys+1, lopetussyvyys, laudan asema)
jos (uuden aseman arvo > aseman arvo)
{
aseman arvo = uuden aseman arvo
muunnelma[syvyys] = siirrot[laskuri]
}
palauta asema ennalleen(siirrot[laskuri], laudan asema)
}
palauta asema arvo
}[/code:2iz2jxpk]
Minkään valtakunnan tekoäly ei tule koskaan lyömään tällaista BruteForcea, koska se kiristää silmukkaa hitaasti mutta varmasti. Jos optimointirahkeita riittää, 24 puolisiirron lopetussyvyydellä kaikki maailman shakkimestarit saavat lyödä viisaat päät yhteen, vaikka se kaikki onkin vain yhdellä mitättömältä vaikuttavalla A4-paperiarkilla.

Sivut

Kommentit (92)

Neutroni
Seuraa 
Viestejä26890
Liittynyt16.3.2005
_jone_
Minkään valtakunnan tekoäly ei tule koskaan lyömään tällaista BruteForcea, koska se kiristää silmukkaa hitaasti mutta varmasti. Jos optimointirahkeita riittää, 24 puolisiirron lopetussyvyydellä kaikki maailman shakkimestarit saavat lyödä viisaat päät yhteen, vaikka se kaikki onkin vain yhdellä mitättömältä vaikuttavalla A4-paperiarkilla.




Brute force on tietysti paperilla idioottivarma. Shakkipelissä (ja varmaan kaikissa muissakin lautapeleissä) on äärellinen määrä mahdollisia tilanteita ja pelinkulkuja, ja niinpä BF:llä voidaan aina laskea siirtosarja jolla ei voi hävitä (jos pelin säännöt mahdollistavat tilanteessa sellaisen), mutta BF:n viemä aika riippuu eksponentiaalisesti lopetussyvyydestä, ja räjähtää helposti kosmisiin mittasuhteisiin. Harva kaveri optimoi tuon laskemaan 24 puolisiirtoa C64:n assemblerilla.

Vierailija

Näin on, mutta käytännössä tuo eksponentiaalisuus räjähtää samojen asemien toistosta. Tempolla on suuri merkitys, jonka vuoksi asemien toisto on eliminoitava niin, että tempon efektiivisyys säilyy. On edelleen aito ja alkuperäistä vastaava BruteForce, mutta vähän tehokkaammalla seulonnalla. (Harrastuksen alla on maksimissaan 64 puolisiirron = likimain 64-klusterin optimointipläjäys, jota työkiireiden vuoksi rakentelen vähän vähemmällä tempolla.)

Vierailija

Vaikuttaa todella mahtavalta. Pseudokoodin saa kyllä tiiviiksi kun sanojen taakse kätkeytyy melkoisesti toimintaa. Rekursio myös tiivistää. Montakohan sivua koodia on sitten lopullisessa toimivassa ohjelmassa?

Pertinax
Seuraa 
Viestejä1782
Liittynyt13.9.2006

Paras shakkimoottori
Rybka is a computer chess engine created by International Master Vasik Rajlich. As of November 2007, Rybka is top-rated in all notable chess engine rating lists[1] and has won many official Computer Chess Tournaments including the 2007 World Computer-Chess Championship. Rybka supports both single processor and symmetric multiprocessing (SMP) systems.

http://en.wikipedia.org/wiki/Rybka

Vierailija
korant
Montakohan sivua koodia on sitten lopullisessa toimivassa ohjelmassa?

No likimain mainittu A4. Itse olen ikäni ihaillut yksinkertaisuutta ja sitä myötä pyrkinyt aina entistä tiiviimpiin ja efektiivisimpiin algoritmeihin. C:llä saman sonnan voi jaaritella pitemmin tai lyhemmin. C:n vahvuutena on kuitenkin suora tuki logiikan juurille eli Boolen algebralle.

MaKo71
Seuraa 
Viestejä1467
Liittynyt15.11.2006

Joo, teehän algoritmi vaan valmiiksi ja ei kun kokeilemaan. Shakki on siitä hyvä peli tietokoneella pelattavaksi, ettei tarvitse tyytyä vain subjektiiviseen näkemykseen algoritmin hyvyydestä, vaan pääsee koettelemaan voimiaan muiden tekemiä algoritmeja vastaan.

EDIT: Itse algoritmista muuten sen verran, että kyllä, tuollainen "mobiliteetti" (jota voidaan arvioida vaikkapa siirtojen määrällä) on havaittu yhdeksi monen pelin voiton avaimia.

...Ja tuon sanomisen jälkeen luin itse pseudokoodin ja jäin ihmettelemään, että tuohan näyttää päälle päin minimax-algoritmilta, jossa staattisena evaluaattorina käytetään siirtojen määrää? Miten tuo eroaa siitä?

Vierailija

Tähän väliin on kysyttävä, että tietääkö joku tietokoneella pelattavaa shakkia täydelliselle amatöörille? Shakin säännöt osaan kyllä, mutta itse pelissä häviän lähes aina kavereilleni, jotka ovat myös amatöörejä. Joten lisäharjoittelua tarvitaan ruohonjuuritasolla hyvin helpon shakkivastustajan parissa.

Pertinax
Seuraa 
Viestejä1782
Liittynyt13.9.2006
tyson
Tähän väliin on kysyttävä, että tietääkö joku tietokoneella pelattavaa shakkia täydelliselle amatöörille? Shakin säännöt osaan kyllä, mutta itse pelissä häviän lähes aina kavereilleni, jotka ovat myös amatöörejä. Joten lisäharjoittelua tarvitaan ruohonjuuritasolla hyvin helpon shakkivastustajan parissa.



http://www.playwitharena.com/

http://www.playwitharena.com/download/a ... setup3.exe

Neutroni
Seuraa 
Viestejä26890
Liittynyt16.3.2005
Armitage
Mites jos pistää tuon algoritmin ottelemaan pöydän kummallekin puolelle? Onko tulos aina sama? Kumpi voittaa?



Yleensä tuollaisissa vuoropohjaisissa peleissä etu on joko aloittajalla tai sitä ei ole. Shakkia ei käsittääkseni ole ratkottu täydellisesti, joten ei tiedetä kumpaan ryhmään se kuuluu. Käytännössä ensimmäisessä tapauksessa valkoisilla pelaava voisi tiettyä algortimia käyttäen aina voittaa pelin riippumatta siitä mitä musta tekee, ja jälkimmäisessä tapauksessa mustalla on mahdollisuus saavuttaa tasapeli. Tuollainen täydellinen pelialgoritmi tekisi siten koko pelistä mielettömän, ainakin tietokonetta vastaan.

MaKo71
Seuraa 
Viestejä1467
Liittynyt15.11.2006

Neutronin selitykseen lisättäköön vielä se, että usein tietokoneet pelaavat pelejä siten, että aika (tai muistin käyttö) on rajoitettu eli käytetään progressiivista hakupuun syventämistä, koska muuten pelaamisessa ei ole mitään mieltä (s.o. algoritmi nyhjää ajasta äärettömyyteen tai sitten kaatuu muistin loppumiseen). Tällöin peleihin tulee jonkin verran satunnaisuutta mukaan ja useissa peleissä algoritmi päätyy 50%-50% -voittosuhteeseen pelatessaan itseään vastaan (toki algoritmista riippuen).

Jos satunnaistekijät poistetaan rajaamalla vaikkapa hakusyvyys, niin algoritmit saattavat "suosia" jomman kumman puolen pelaamista, jolloin algoritmin pelatessa itseään vastaan se voittaa aina jommalla kummalla puolella (siis voittaa joko aina valkoisilla, tai aina mustilla).

Vierailija

Joo, rajoitukset ja ajasta ikuisuuteen plaraaminen on paljon kiinni myös siitä, kuin paljon ko. asiaa on viitsinyt tutkia. Hyvässä lykyssä tuo samojen asemien toisto lähes äärettömän monta kertaa hiukan eri siirtojärjestyksillä on (oli) ehkä ratkaistavissa, mutta toisin kuin luulet.

Oletkos koskaan optimoinut sadantuhannen tuntemattoman yhtälöryhmiä. Vaikuttaa aluksi melko aikaa vievältä algoritmilta, mutta jos asiaa viitsii tutkia riittävästi, se pyhä yksinkertaisuus löytyy, ja sen jälkeen ratkaisu singahtaa valonnopeudella.

Voihan sitä käydä erilaisia huuhaa-kouluja ja lässyttää sitten suu vaahdossa tietävänsä asiasta jotain, vaikka todellisuudessa ei ole uhrannut ehkä sekuntiakaan asian tutkimiseen.

MaKo71
Seuraa 
Viestejä1467
Liittynyt15.11.2006
_jone_

Joo, rajoitukset ja ajasta ikuisuuteen plaraaminen on paljon kiinni myös siitä, kuin paljon ko. asiaa on viitsinyt tutkia. Hyvässä lykyssä tuo samojen asemien toisto lähes äärettömän monta kertaa hiukan eri siirtojärjestyksillä on (oli) ehkä ratkaistavissa, ...



No, ihan puhtaassa BF:ssä voidaan käyttää sitä shakin sääntöä, että jos sama asema toistuu kolme kertaa, peli on tasapeli. Muitakin keinoja on, useimmissa algoritmeissa tallennetaan tilannetiedot muistiin hash:lla haettavaksi, jottei samaa tilannetta tarvitse toistamiseen evaluoida.

_jone_

...mutta toisin kuin luulet.



Jään mielenkiinnolla odottamaan.

_jone_

Oletkos koskaan optimoinut sadantuhannen tuntemattoman yhtälöryhmiä. Vaikuttaa aluksi melko aikaa vievältä algoritmilta, mutta jos asiaa viitsii tutkia riittävästi, se pyhä yksinkertaisuus löytyy, ja sen jälkeen ratkaisu singahtaa valonnopeudella.



En ole optimoinut. Moniin ongelmiin kuitenkin löydetään - ja on löydetty - yksinkertaisia tietokoneen ajamaksi soveltuvia algoritmeja.

_jone_

Voihan sitä käydä erilaisia huuhaa-kouluja ja lässyttää sitten suu vaahdossa tietävänsä asiasta jotain, vaikka todellisuudessa ei ole uhrannut ehkä sekuntiakaan asian tutkimiseen.



Eivät suuret sanat suuta halkaise. Voi myös olla käymättä kouluja ja selittää sitten suu vaahdossa keksineensä asioita, jotka on keksitty jo aika päivää sitten.

Pseudokoodin perusteella keksimäsi algoritmi näyttää kömpelösti toteutetulta minimax-algoritmilta. Käytät staattisena evaluaattorina siirtomäärän laskemista, joka on jonkinlainen approksimaatio pelitilanteen mobiliteetille. 50 vuotta sitten olisit voinut tehdä asiasta ehkä jopa tieteellisen artikkelin.

Jotta sun ei tarvitse uhrata hirveästi aikaa turhanpäiväiseen, niin kerron sulle muutamia hyviksi havaittuja keinoja minimax-algoritmin toteutukselle:

- Yleensä pelitilanteen evaluaatio on symmetrinen, ts. tilanne on yhtä hyvä valkoiselle kuin se on heikko mustalle ==> voit käyttää samaa evaluaatiofunktiota molemmin puolin, tuloksen etumerkki pitää vain kääntää toisella puolella (s.o. jos lasket valkoisen aseman hyvyyden, saat mustan aseman hyvyyden vaihtamalla etumerkin).

- Et tarvitse kahta funktiota (toinen mustalle, toinen valkoiselle); voit yhdistää ne joko pistämällä funktion argumenttina sisälle siirtovuoron, mutta vielä elegantimmin kirjoittamalla minimax-algoritmin negamax-algoritmiksi.

- Minimax:iin kannattaa aina liittää alfabeta-karsinta

- Tavallisesti staattista evaluaatiota ei minimax:ssa tarvitse tehdä kuin lehtisolmuille. Alfabeta toimii kuitenkin sitä paremmin, mitä aikaisemmassa vaiheessa oikeasti hyvät pelitilanteet avataan ==> solmut kannattaa järjestää jonkinlaisen staattisesti arvioidun hyvyyden mukaan.

- Alfabetaa voidaan kehittää "ikkunoinnilla" (windowing); pelitilanneavaruuden "luotaamiseen" (probing) ja sitä kautta tehokkaampaan karsintaan on kehitetty sellaisia menetelmiä kuin PVS (Principal Variation Search), sen kehittyneempi versio NegaScout, MTD(f) ja monta muuta.

- Nuo mainitut karsintamenetelmät ovat nk. backward pruning -karsintamenetelmiä, eivätkä ne vaikuta siihen, kuinka algoritmi valitsee siirron eli algoritmi valitsee saman siirron riippumatta siitä, onko karsinta käytössä vai ei, mutta karsinnalla se valitsee siirtonsa nopeammin ja vähemmällä työllä.

- vielä parempiin tuloksiin päästään forward-pruningilla (esim. ProbCut), mutta niiden haitta on usein se, että ne sitten vaikuttavat kovastikin siihen, minkä siirron algoritmi valitsee.

- Nk. "Quiescence Search" -variaatioilla kohdennetaan hakupuun syventäminen niihin tilanteisiin, joissa on "tilanne päällä" eli aktiivinen pelitapahtuma menossa; shakissa usein lehtisolmussa oleva nappulan syöminen evaluoidaan askel eteenpäin eikä luoteta staattisen evaluaattorin antamaan tulokseen.

Toivottavasti tästä on apua & iloa ja pääset algoritmisi kanssa nopeammin eteenpäin.

EDIT: Sun ei siis tarvitse kuin syöttää noita sanoja googleen ja pääset käsiksi kyseisen algoritmin/variaation/laajennuksen toteutuksiin.

Lisä-EDIT: Huomaathan, että nuo kaikki ovat voimassa vain silloin, kun aika tai muisti on rajoitettua. Jos peli on tarpeeksi yksinkertainen tai aika/muistirajoituksia ei ole, niin silloin turvaudutaan hakualgoritmeihin. Käytettävissä olevan tiedon perusteella analyyttisia menetelmiä ovat mm. Depth First, Breadth First, Hill-Climbing tai A*. Jos hakuavaruus on suuri ja myös suboptimaaliset ratkaisut kelpaavat, algoritmeja ja erityisesti karsintamenetelmiä löytyy moninverroin enemmän sovellusalueesta riippuen.

Esimerkiksi perus-3x3-ristinolla kannattaa ratkaista A*-haulla eikä minimaxilla.

Vierailija

Ööh...itse olen sellainen kohtalainen shakinpelaaja, ja lyön kaikki kaverini mennen, tullen ja palatessa. Ohjelmointitaitoni lienee myös tyydyttävä, koska teen työtä ohjelmistojen parissa. Minimax tuo pseudokoodisi on, kuten se ketjussa on jo todettukin.

Mutta minun mielestä tuon kaksoisrekursion lopetusehto on kaikkea muuta kuin shakillisen aseman kompromissi. Huomioon pitäisi ottaa myös nappuloiden arvot, uhkaukset, kiinnitykset, liikkuvuus, jne. Lopetusehtosi ei millään muotoa ota kantaa noihin shakkiaseman vähimmäisvaatimuksiin. Miten se silloin voisi palauttaa lopetusehdoksi oikean staattisen aseman?

-torstai

Vierailija
torstai
Huomioon pitäisi ottaa myös nappuloiden arvot, uhkaukset, kiinnitykset, liikkuvuus, jne. Lopetusehtosi ei millään muotoa ota kantaa noihin shakkiaseman vähimmäisvaatimuksiin. Miten se silloin voisi palauttaa lopetusehdoksi oikean staattisen aseman?

No toki se, että kysyy, on positiivista. Tämän foorumin konteksti ei kuitenkaan suoraan ole kysymyksiä, ja vastauksia kysymyksiin, vaan enemmänkin sellainen, jossa mielellään aiheista väitellään. Argumentteihin esitetään entistä kovempia vasta-argumentteja, jolloin jossain vaiheessa päädytään totuuteen tai se jää edelleen avoimeksi.

Jos haluat kysymyksiin vastauksia, suosittelen ohjelmointiputkaa. Se on täynnä ohjelmoinnin, matematiikan, fysiikan ja kemian guruja. Tyhjentävät vastaukset kaikkein kiperimpiinkin ongelmiin saat sieltä kuin apteekin hyllyltä.

Mutta viimeinen poikkeus, koska minulla on parempaakin tekemistä, kuin vastailla kysymyksiin. Olkoon tuo lopetussyvyys ensin vaikka kaksi puolisiirtoa. Siirron vahvuus ja järkevyys on silloin 2/2=1.

Haluat hiukan vahvemman siirron. Lopetussyvyydellä neljä siirron vahvuus normalisoituun referenssiin nähden on 4/2=2.

Ja näin tuo ihmeellinen 2^n löytää paikkansa myös shakissa. Mainittakoon, että parittomilla lopetussyvyyksillä saadaan äreästi hyökkäävä efekti, ja parillisilla vastaavasti äärimmäisen harkiten pelaava algoritmi. Voi tietysti käyttää mitä lopetussyvyyksiä hyvänsä, mutta asemien toiston eliminoinnin kannalta tuo jokin 2^n (tarvittaessa miinus yksi) antaa optimoinnin kannalta selkeästi tehokkaamman perustan.

Sivut

Uusimmat

Suosituimmat