Kysymys:
Mitä hankkeita on toteutettu shakin ratkaisemiseksi kokonaan?
shashank shekhar singh
2020-07-08 11:02:04 UTC
view on stackexchange narkive permalink

Shakki ei ole vielä täysin ratkaistu, mutta miten sen ratkaisemiseksi on pyritty? Onko HGP: n kaltaista suurta projektia ollut vai onko jotain sellaista edes syytä jatkaa? Mitä epäonnistuneita ponnisteluja on ollut jos mahdollista? Oletan, että Alpha Zero -hankkeessa on täytynyt ottaa joitain askelia kohti tätä päätä. kysymys. Mitä haluaisin tietää, onko olemassa tai onko ollut projekteja, jotka yrittävät ratkaista shakkia. Kuten se Moskovan yliopiston 7-osainen pöytäjalusta ja kaikki sellaiset ponnistelut. Se on selvästi kallis ongelma ratkaista, mutta kuka tekee sen ja mitä lähestymistapoja noudatetaan? Usein sanotaan, että shakkiyhdistelmiä on enemmän kuin atomeja maailmankaikkeudessa (luultavasti kyseisen mainoksen takia), mutta niin ovat myös todelliset luvut, mutta meillä on siitä rikas teoria. Tiedämme myös paljon maailmankaikkeudesta, mutta meidän piti yrittää kovasti päästä siihen pisteeseen. Onko shakkia kohdeltu samalla tavalla, olen kysymykseni.

Entä projektit, jotka osoittavat, että se on käytännössä ratkaisematon? Näytetään esimerkiksi PSPACE-täydellisyys. Tämä tulos viittaa siihen, että meidän ei pitäisi odottaa löytävänsä tarpeeksi lyhyttä ratkaisua laskettavaksi tässä maailmankaikkeudessa.
@usul kyllä ​​miksi ei. irrotus on myös hyödyllinen. mutta sen on oltava siellä.
[Tämä viesti] (https://math.stackexchange.com/a/1407631/7721) arvioi noin 10 ^ 44 mahdollista shakkiasemaa. Mikä on ~ 2 ^ 146, siis teoriassa tarvitaan 146 bittiä yhden shakkiaseman tallentamiseksi. Tarvitset [12 atomia vähän varastointiin] (https://qr.ae/pNKjJh) (-272 ° C: ssa). Tarvitset siis 146 * 12 * 10 ^ 44 = 1,75 * 10 ^ 48 atomia kaikkien sijaintien tallentamiseen. Maapallolla on 1,33 * 10 ^ 50 atomia, joten ainakin teoreettisesti on mahdollista rakentaa riittävän suuri muisti kaikkien shakkiasemien tallentamiseen, jos käytämme 1,31% maapallon atomista tähän pyrkimykseen.
@Ivella Väite paikkojen tallentamisesta on liioittelematta virheellinen. Pelin ratkaiseminen ei tarkoita sitä, että sinun on tallennettava kaikki mahdolliset sijainnit: se tarkoittaa, että on selvitettävä, onko olemassa ainakin yksi ratkaisu, jossa toinen puoli ei häviä väkisin - voit yhtä hyvin selata kaikkia mahdollisia asemia _ tallentamatta mitään_, kunnes löydä yksi. Olemme kaikki samaa mieltä siitä, että tämä vie valtavasti aikaa, mutta se on erilainen ongelma kuin mainitsitte.
Lisäksi ratkaiseminen ei välttämättä tarkoita raakaa pakottamista kaikkien kantojen läpi. Harkitse Nimia, joka voidaan tehdä mielivaltaisesti suureksi, mutta silti vahvasti ratkaistuksi. Aika-argumentit perustuvat shakkiin, jolla ei ole minkäänlaista abstraktia rakennetta, jota voidaan hyödyntää - mikä on oikeudenmukaista, on todennäköisesti täysin totta.
@gented: Tietojen tallentaminen on vain puolet ongelmasta. Sinun on myös selattava vähintään kaikki mahdolliset paikat, mikä edellyttää vähintään [yhden] (https://fi.wikipedia.org/wiki/Gray_code) bitin poistamista sijaintia kohti, mikä [maksaa vähän energiaa] ] (https://fi.wikipedia.org/wiki/Entropy_in_thermodynamics_and_information_theory#Negentropy), mutta kun kerrot sen sijaintien lukumäärällä, energiantarve voi olla melko suuri ...
"Mitä hankkeita on toteutettu shakin ratkaisemiseksi kokonaan?" - Ei mitään, siitä yksinkertaisesta syystä, että jokaisella, jolla on tekniset taidot hankkeen toteuttamiseen, olisi teknisiä taitoja ymmärtää, että projekti on todennäköisesti mahdoton.
@Kevin _ "... joka vaatii vähintään yhden bitin poistamisen paikkaa kohden" _, joka on täysin eri asia: sekoittamalla kaikki nämä asiat osoitat olennaisesti, että ymmärrät kysymyksen ja ongelman epämääräisesti.
@gented: Kuinka niin? Kieltätkö, että algoritmin täytyy kääntää vähintään yksi bitti per asema? Vai kiistätkö tällä merkitystä sen suhteen, onko fyysisesti mahdollista rakentaa tietokone, joka pystyy tekemään niin? Koska jälkimmäinen kuuluu termodynamiikan ja informaatioteorian piiriin.
@Kevin Vastustan väitettä, jonka mukaan _ "shakki ei ole ratkaistavissa, koska kaikkia sijainteja ei voi tallentaa" _ - koska niitä ei tarvitse varastoida itse asiassa (tai ehkä vain joitain). Onko olemassa muita vastalauseita, on eri asia, ja voimme keskustella siitä eri kysymyksessä. Tietueiden lukumäärästä riippumatta, kuinka monta bittiä se tarvitsee jokaisen shakkiasennon analysointiin, suurin osa shakkiasemista voidaan saada geometrisilla muunnoksilla toisistaan ​​(levyn käännökset, käännökset), joten sinun tarvitsee vain "tallentaa" yksi asema ja yksi muunnos. ..
... jotta voit rekonstruoida kaikki muut. Esimerkiksi sinun ei tarvitse analysoida kaikkia kuningas- ja sotilaspäätteitä, voit vain pienentää suurimman osan niistä arvoon K + 1 vs K sopivien muunnosten avulla. Samoin, vaikka nykyiset moottorit ovatkin melko kaukana pelin ratkaisemisesta, ne antavat hyvän osoituksen paikoista, jotka eivät ole voittaneet varmasti (suurin osa niistä), joten voit hylätä ne jo etukäteen. Joten argumenttien esittäminen atomien lukumäärään universumissa shakkiasemia vastaan ​​on todella harhaanjohtavaa.
@gented: Mutta * kysymys * ei koske minkään "tallentamista". Kyse on siitä, voidaanko shakki ratkaista ollenkaan. Se, että yksi tietty kommentti päätti keskittyä valitettavaan harhaan, ei rajoita kysymyksen laajuutta kokonaisuutena. Mitä tulee "geometrisiin muunnoksiin" - Se vähentää paikkojen määrää, mutta on silti hämmästyttävän suuri.
@Kevin En väitä mitään muistin sisäisistä esityksistä: Esitän väitteen, jonka mukaan shakin ratkaiseminen ei vaadi mitään tallentamista eikä "silmukointia" millään tavalla objektiivisesti (vaikka se voidaan silti tehdä). Jos ongelma on kuitenkin edelleen liian monimutkainen nykyisille ja tuleville tekniikoille, olen samaa mieltä, mutta sinun on esitettävä siihen perustuva syy, joka ei perustu maailmankaikkeuden atomien määrään tai vastaavaan :)
@gented: Voisin olla halukas hyväksymään sen, että parhaan tietoni mukaan kukaan ei ole esittänyt todistettavasti oikeaa algoritmia shakki- tai shakkimaisten pelien ratkaisemiseksi, johon ei liity pelipuun suuren osajoukon etsimistä. Joten pidän tätä päättelyä melko epäilyttävänä. Toki on * mahdollista *, että olemme unohtaneet erittäin halvan algoritmin monien alan asiantuntijoiden vuosikymmenien ponnisteluista huolimatta - mutta olen skeptinen.
Kymmenen vastused:
#1
+43
RemcoGerlich
2020-07-08 12:05:08 UTC
view on stackexchange narkive permalink

Endgame-pöytäpohjat voidaan nähdä sellaisena pyrkimyksenä, että aloitimme muutamasta kappaleesta ja olemme lisänneet määrää. Vuonna 2012 luotiin seitsemän kappaletta Moskovan valtionyliopistosta, joten shakki ratkaistaan ​​7 tai vähemmän kappaletta (kuninkaat mukaan lukien).

Ongelmana on, että 7-osainen pöytälevy vie noin 140 Tt: n varastotilaa. Kahdeksan kappaleen pöytälevyt vievät noin 10 petatavua tallennustilaa ja tietokone, jossa on 50 Tt RAM-muistia ( lähde), jotta hajautukset muistissa säilytetään kohtuullisessa ajassa (muutaman vuoden? Luulen, että se olisi mahdollista näinä päivinä, jos joku antaa miljoonia dollareita saataville. 9 näyttää olevan ulottumattomissa.

Joten kestää jonkin aikaa, ennen kuin saavutamme 32.

Tietenkin nämä ovat pyrkimyksiä ratkaista voimakkaasti shakki, mikä tarkoittaa, että voittostrategia tunnetaan kaikista mahdollisista palojen ja paikkojen yhdistelmistä pöydällä. Teoriassa shakin heikon ratkaisemisen pitäisi olla huomattavasti helpompaa, mikä tarkoittaa, että voittostrategia löytyy vain yhdestä lähtöasemasta.
@Brady Gilg * voittajastrategia löytyy vain yhdestä lähtökohdasta *. Voitteko selittää tämän? Ei ole olemassa yhtä voittavaa strategiaa. Se on säädettävä vastustajan liikkeiden mukaan. Jos sanot, että molemmat pelaajat pelaavat "optimaalisesti", joten peli väistämättä kulkee yhtä reittiä, se ei ole totta.
@chaslyfromUK Peliteoriassa "strategia" tarkoittaa joukkoa sääntöjä siitä, miten vastataan muiden pelaajien toimintaan. Voittavaa strategiaa ei tarvitse säätää vastustajan liikkeiden mukaan; "strategia" tarkoittaa sitä, että päättää mitä tehdä heidän liikkeidensa perusteella. Tietokoneessa voittava strategia olisi tietokoneohjelma, joka ei varmasti häviä.
@chaslyfromUK En tiedä mitä tarkoitat, strategiassa otetaan huomioon vastustajan mahdolliset liikkeet.
@BradyGilg: kyllä, teoreettisesti se olisi helpompaa. Mutta silti täysin mahdoton. Ja kysymys on siitä, mitä projekteja todella toteutettiin, en ole tietoinen yrityksistä ratkaista lähtökohta.
@ Kertyminen - olen täysin samaa mieltä. Pyysin yksinkertaisesti selvennystä. Jos "voittavalla strategialla" tarkoitetaan haaroittumisstrategiaa vastustajan jokaiselle mahdolliselle laskurille joka askeleella, olen siinä kunnossa. Tällaisen strategian löytäminen ei kuitenkaan välttämättä ole mahdollista! Ei voi olla avaamista, joka takaa voiton.
* "kestää jonkin aikaa, ennen kuin pääsemme 32: een" * on melko vähättelyä. Sisältyykö * "jonkin aikaa" * maailmankaikkeuden arvioitu ikä, vaikka jokainen atomi olisi tietokone?
Mikä olisi taloudellinen kannustin oikeuttamaan resurssien heittäminen tähän ongelmaan?
@DanDascalescu Samankaltainen tapa kuin IBM sai suuren julkisuuden tietokoneiden ohjelmoinnissa voittamaan parhaat ihmiset shakissa ja Jeopardy !:ssa, shakin täydellinen ratkaisu olisi maailmanlaajuinen uutinen. Se antaisi vastuuhenkilölle suuren potentiaalin maineelle ja asiakkaiden kiinnostukselle heidän todennäköisestä kyvystään soveltaa laskentatehoa ja hakualgoritmeja muihin erittäin vaikeisiin, mutta käytännöllisempiin ja kannattavampiin ongelmiin.
@chaslyfromUK Tällöin olemme ratkaisseet heikosti heikosti huomatessamme, että täydellisellä pelillä lähtöpaikka johtaa aina tasapeliin.
@Omegastick - Kyllä. Mikä oli osa syytä sille, että pyysin ensinnäkin selvitystä Brady Gilgiltä. On olemassa kolme mahdollisuutta: 1. Valkoinen pakottaa voiton, 2. Musta pakottaa voiton, 3. Peli päättyy tasapeliin. Se ei kuitenkaan peitä sitä kokonaan. Ei välttämättä ole yhtä strategiaa. Saattaa olla, että X voi pakottaa voiton monin eri tavoin käyttämällä erilaisia ​​aloitusliikkeitä. Huomaa, että en koskaan vastustanut termejä * heikosti * ja * voimakkaasti *
@BradyGilg "ottamalla huomioon vastustajan mahdolliset liikkeet" on terävästi mitä loppupelipöydät tekevät. He sanovat "jos olet tässä asennossa ja liikut X: ää, voitat." Tämän todistaa se, että jokaisesta Y: n liikkeestä, jonka vastustaja tekee, voit pysyä pöydissä. Todistaaksesi, että "ei häviä" -strategia on olemassa, todistat useimmiten, että vastustajasi ei voi koskaan päästä asemaan pelaamaan siirtoa X, ja "voittaminen" on vielä vaikeampaa todistaa kuin tämä.
@CortAmmon:: llä tarkoitetaan yksinkertaisesti sitä, että lähtöasennon tuloksen todistamiseksi on olemassa monia paikkoja, jotka melkein varmasti ohitat. Kuten lähtöasennossa, mutta tornit ja ritarit vaihdettu. 32 miehen pöytätietokone sisältäisi tämän, mutta on todennäköistä, että alfa-beeta-haun koko pelin ei koskaan tarvitse saavuttaa kyseistä sijaintia. Siinä kaikki.
@CortAmmon Kyllä ... mitä? Kukaan ei väitä toisin.
@RemcoGerlich - Pelkään, että jos sekä shakki että shakki, jossa on vankeja ja ritareita vaihdetaan, ovat piirtopelejä, on erittäin vaikeaa ennustaa, mitkä saavutettavat sijainnit saatetaan karsia alfa-beetalla. Esimerkki, jonka yhdistän Brady Gilgin kommenttiin helpommin, olisivat tornit ja piispat vaihdettu; muuten laillinen asema.
@JirkaHanika: Se oli vain esimerkki; on selvää, että _joukko_ kantoja karsitaan.
AilihrtulbCMT - OK
@RemcoGerlich Alpha-beeta -ohjelmaa voidaan käyttää "täysin" shakin ratkaisemisessa vain, jos sinulla on oraakeli, joka tunnistaa täydellisesti, mitkä sijainnit ovat parempia tai huonompia. On ehdottomasti pieni osa, joka on todistettavasti saavuttamaton, mutta useimmat ovat tavoitettavissa, ja on vaikea todistaa, etteivät ne ole paras liike, ennen kuin analysoit niitä.
@Cort Ammon:, että oraakkeli on matoa, tai piirtää jollakin keinolla tai pöydällä. En voi todistaa, että mikään asema ohitetaan (ja se riippuu järjestyksestä, jossa yrität niitä), mutta jotkut tulevat. Jos oletetaan, että tarkastuksia yritetään ensin, sijaintia 1.f3 e6 2.g4 e5 jälkeen ei tarvitse tarkistaa, koska 2 ... Qh4 # on jo voittamassa mustaa.
@CortAmmon: ** Ei **. Alfa-beeta ei ** saa ** väärää vastausta, ja sitä voidaan käyttää shakin täydelliseen ratkaisemiseen. Olet yksinkertaisesti väärässä väitteessäsi, että tarvitset oraakkelia.
@CortAmmon: Jos et tiedä alfa-beetan takana olevaa matematiikkaa, lue [tämä] (https://chess.stackexchange.com/a/29842/9192), joka hahmottaa todistuksen siitä, että alfa-beeta saa ** täsmälleen saman * * tulos täydellisenä negamax-hauna. RemcoGerlich antaa viimeisessä yllä olevassa kommentissaan esimerkin siitä, kuinka linjat ** hylätään oikein ** alfa-beetalla plus liikkumisjärjestyksellä, mutta hänen käyttämänsä termi "oraakkeli" on väärä. Kuten jo sanoin, minkäänlaista oraakkelia ei tarvita.
@user21820 Olen perehtynyt alfa-beeta-karsimiseen. Mitä toimintoa arvioit päättääksesi mitkä oksat karsitaan?
@RemcoGerlich Pidän loppupelitaulukoita kelvollisena oraakkelin muotona (tai pikemminkin funktio, joka antaa +1 voitetuille paikoille 0 piirretyille positioille ja -1 menetetyille sijaille olisi oraakkeli), koska niiden on tarkoitus antaa määritelty paras liike. Joten kyllä, jos sinulla on 6-osainen loppupelipöytä, pystyt arvioimaan useimmat 7-osaiset sijainnit paljon pienemmillä laskelmilla, joita muuten tarvittaisiin.
Voit todellakin pystyä poistamaan kourallisen mahdollisuuksia. Mutta [arvioitu] (https://fi.wikipedia.org/wiki/Shannon_number) $ 10 ^ 43 $ -asennoilla jopa löytää tapa sulkea pois 99.999% niistä jättää sinulle vielä $ 10 ^ 38 $ -asemia käsiteltäväksi.
@CortAmmon: Kommenttisi osoittaa selvästi, että et ole ** lainkaan ** perehtynyt alfa-beetan. Kuten sanoin, lue linkitetty viesti, joka hahmottaa ** todistuksen ** siitä, että alfa-beeta-karsinta johtaa ** täsmälleen samaan ** tulokseen kuin täydellinen negamax-haku. Heuristisella karsinnalla ei ole ** mitään tekemistä alfa-beeta-karsimisen kanssa. ** Kuten toisessa viestissä selitettiin **, alfa-beetan kanssa käytetty hyvä liikkeenjärjestysheuristiikka lähes puolittaa tehokkaan hakusyvyyden. Ei mitään tekemistä prosenttiosuuksien kanssa.
@user21820 Ja sekä alfa-beeta että negmax olettavat jonkinlaisen tavan mitata lehtisolmujen hyvyyttä hakusyvyytesi koko laajuudessa. Päivän lopussa tarvitset vielä pistemäärän hallituksen paikoista. Olemme melko varmoja siitä, että 1. h4 ei ole voittava liike. Se pisteet melko huonosti useimmilla heuristiikoilla. Mutta emme todellakaan ole todistaneet sen olevan voittamaton liike. Meillä on vain paljon itseluottamusta.
Kaikkien tällaisten algoritmien häivytys on sijainti, joka näyttää aivan kauhealta, mutta sillä on perämies yhdessä vain * yhdessä * kerroksessa horisontinsa ulkopuolella.
@CortAmmon: Riippumatta siitä, mitä sanot nyt, ei ole merkitystä ** tosiasialle **, että [ensimmäinen kommenttisi alfa-beetasta] (https://chess.stackexchange.com/posts/comments/48580) ("Alfa-beeta voi olla vain käytetään "täysin" shakin ratkaisemisessa, jos sinulla on oraakeli, joka pystyy täysin tunnistamaan, mitkä asemat ovat parempia tai huonompia. " Toiseksi alfa-beetalla ei ole ** mitään tekemistä ** sen kanssa, etsitkö pelipuun loppuun vai ei. Älä lopeta sellaisten hämmentyneiden lausuntojen esittämistä, jotka sekoittavat toisiinsa liittyviä asioita. Tämä ei ole ensimmäinen kerta, kun et myönnä virheitäsi.
Jatka [jatka tätä keskustelua chatissa] (https://chat.stackexchange.com/rooms/110478/discussion-between-cort-ammon-and-user21820).
Muiden lukijoiden vuoksi tässä on totuus: Alfa-beeta-karsimista ** voidaan ** soveltaa shakin täydelliseen ratkaisemiseen, ja kun sitä käytetään kohtuullisen hyvällä liikkumisjärjestysheuristisella tavalla, tuloksena on hakupuu, jolla on noin tehokas haarautumistekijä. verrannollinen keskimääräisen haarautumistekijän neliöjuurelle täydellisessä haussa ilman alfa-beetaa. Se, onko meillä laskentatehoa tehdä se tänään, ei muuta sitä tosiasiaa, että sitä voidaan käyttää, ja se on varmasti mukana, jos shakki ratkaistaan ​​tulevaisuudessa.
#2
+19
Allure
2020-07-08 12:00:09 UTC
view on stackexchange narkive permalink

7-osaiset loppupelipöydät valmistuivat vuonna 2012. Seuraava looginen vaihe on 8-osainen loppupelipöytäpohja. Tällä sivulla kerrotaan vähän siitä, miten he menevät (konteksti etsii pisin pakollista kaveria panttilainaamattomissa paikoissa):

Monet osoittavat kiinnostusta siihen, mitä odottaa [8-osaiset] päätteet ... Valitettavasti [8-osaisten pöytälevyjen] koko on 100 kertaa suurempi kuin [7-osaisten] pöytälevyjen koko. Niiden täydelliseksi laskemiseksi tarvitaan noin 10 PB (10000 TB) levytilaa ja 50 TB RAM-muistia. Vain kymmenen suurinta supertietokonetta pystyvät ratkaisemaan [8-osaisen] ongelman vuonna 2014. Älä siis pidä hengitystäsi odottaessasi uusia läpimurtoja liian pian - ensimmäistä 1000 siirron kaveria ei todennäköisesti löydetä vuoteen 2020 mennessä, jolloin osa TOP100-supertietokoneesta saattaa olla saa käyttää tämän tehtävän ratkaisemiseen.

Jos saamme yhtenä päivänä 8-osaiset pöytätasot ( jos saamme ne), se on seuraava askel ratkaisemaan shakkia, mutta emme odota saavamme heitä ainakin monien vuosien ajan. Vaikka ne olisikin luotu, ne vievät valtavan määrän levytilaa tallennukseen.

Shakki ratkaistaan ​​periaatteessa, kun meillä on 32-osaiset pöytälevyt, mutta jos 8-osaisia ​​pöytälevyjä on vaikea luoda , emme aio ratkaista shakkia lähitulevaisuudessa, AlphaZero vai ei.

Vuonna 2020 voit vuokrata 10PB levyä ja 50TB RAM-muistia (ja muutamia kymmeniä tuhansia suorittimen ytimiä edulliseen hintaan) ehkä 5 miljoonalla dollarilla vuodessa.
@hobbs Oikea, mutta luulen, että ihmisillä, jotka ovat valmiita käyttämään 5 miljoonaa dollaria vuodessa, on parempia sovelluksia siihen, kuten COVID-19: een liittyvä proteiinin taitto.
#3
+15
David
2020-07-08 11:52:58 UTC
view on stackexchange narkive permalink

AlphaZerolla ei ole aikomusta ratkaista shakkia. Se on vain moottori, joka pelaa upeasti. Paikkojen määrä, jotka sinun on arvioitava shakin ratkaisemiseksi, on suurempi kuin maailmankaikkeuden atomien määrä, joten vaikka pystytkin ratkaisemaan shakin (mikä ei ole läheskään kaikkien maapallon tietokoneiden nykyisten ominaisuuksien mahdollisuuksia yhdistettynä) ), et voi tallentaa koko ratkaisua mihinkään

Oletat, että sinun on tallennettava kaikki sijainnit. Voit varmasti hylätä "pahimmat" siirrot tallentamatta niitä tai koodata "lyhyen" algoritmin, joka toimii useista vastaavista paikoista, välttäen tarvetta tallentaa ne suoraan. Voit myös todeta, että mikä tahansa shakkipeli on ratkaisun varasto jokaiselle sijainnille, josta se voi voittaa, riippumatta siitä, onko hänellä a priori tietoa tästä asemasta vai ei.
@jpaugh tarkalleen. A0 ei "tallenna" kaikkia paikkoja, minkä vuoksi sanoin, että kyseinen projekti on erityisen mielenkiintoinen shakin ratkaisemisessa. jos pystyisimme seuraamaan A0: ta suurilla investoinneilla, se voi viedä meidät hyvin pitkälle kartoittamattomille alueille
@jpaugh shakin "ratkaisemiseksi" tarvitset ratkaisun jonnekin. Muuten sinulla ei olisi mitään tapaa tietää, ratkaisitko sen vai et.
Kuten mainitsin muualla, yleisen shakin PSAPCE-täydellisyyden kaltaiset tulokset viittaavat siihen, että meidän ei pitäisi odottaa pystyvän puristamaan ratkaisua galaksin alapuoliseen kokoon, jopa epäsuorasti kuten moottorin suolistossa. Tämä eroaa NP-täydellisistä ongelmista, joiden ratkaisuja voi olla vaikea löytää, mutta jotka ovat pieniä.
@David Nim, jolla on alkukokoisia kokoja {1,2, ..., 100}, on kelvollisempien sijaintien suurempi tila kuin shakki, mutta se on ratkaistu. Ratkaisu koostuu algoritmista, joka laskee liikkeen, joka antaa sijainnin, ja todistuksen siitä, että sen laskema liike on aina optimaalinen. Shakki on todennäköisesti vaikeampaa kuin Nim, mutta sijaintitilan koko ei sinänsä kerro paljoa.
@benrg varma, tallennustilaa koskevassa argumentissa oletetaan implisiittisesti, että sinun on tallennettava merkittävä osa sijainneista. Shakille ei kuitenkaan löydetty algoritmia, ja kun otetaan huomioon lukuisat yritykset löytää se, on todennäköistä, että toteutettavissa oleva on olemassa. Shakki-tietokoneyhteisö on varmasti luopunut sellaisen löytämisestä.
@David _ "shakin" ratkaisemiseksi ", sinun on pidettävä ratkaisu varastoituna jonnekin" _ - kyllä, sinun on tallennettava ratkaisu _, ei kaikkia muita ratkaisuihin kuulumattomia paikkoja, mikä tulee olennaisesti vain yhteen peliin shakki (pakottava ratkaisu).
@gented Se ei olisi ratkaisu. Ensimmäisen siirron yhteydessä sinulla on 20 erilaista vaihtoehtoa, jotka kaikki johtavat tasapeliin (siis vastaavat), ei riitä, että olet analysoinut yhden niistä.
Voit tallentaa sen mustaan ​​aukkoon :)
@David Sitä emme sanoneet (luetko edes kommentteja?). Analysoit kaikki ne, mutta * säilytät vain voitettavan.
@gented Miksi arvelet voittavan siirron olevan olemassa? Shakki on todennäköisesti tasapeli täydellisellä pelillä. Silloinkin kun olet tallentanut vain voittavan siirron (ehkä 1.e4), sinun on tallennettava vastaus kaikkiin Blackin 20 mahdolliseen vastaukseen, ja kun olet tallentanut, sinun on tallennettava voittoliike kaikkia yli 400 yhdistelmää ( vain siirtämällä kaksi!)
@David _ "Miksi luulet voittavan siirron olemassaolon?" _ En, se ei ole asia, josta keskustelemme, lue yllä olevat kommentit uudelleen. Sinun ei tarvitse tallentaa _ mitään_, se on täsmälleen asia : ratkaisun etsiminen EI vaadi hakuyritysten tallentamista. _Jos_ ja vain _Jos löydät vahingossa ratkaisun (saatat olla tai ei) _Sitten_ tallennat vain kyseisen ratkaisuun johtavan yhden shakkipelin (joka on vain yksi `.pgn`-tiedosto): kaikki edelliset yrityksesi, vaikka kuinka monta tahansa niitä ei tarvitse säilyttää missään.
@pented On vähän töykeä olettaa, että minulla on näkemykseni tietämättömyyteni tai ymmärryksen puuttumiseni vuoksi eikä mahdollisuudesta olla oikeassa. Ratkaisun on sisällettävä kaikki vastaukset häviäjän (tai molempien puolien, jos peli on tasapeli) vaihtoehtoisiin liikkeisiin. Toki voit tietysti tallentaa kaiken yhteen .pgn-tiedostoon! Ainoa .pgn-tiedoston koko TB: ssä on useita suuruusluokkia suurempi kuin havaittavissa olevan maailmankaikkeuden atomien määrä. Mutta varma, että se on edelleen yksi .pgn-tiedosto
#4
+6
DongKy
2020-07-08 20:36:01 UTC
view on stackexchange narkive permalink

On hauskaa, että nostat matematiikan ja maailmankaikkeuden asioiksi, joista tiedämme melko vähän. Kumpikaan näistä kentistä ei ole 'ratkaistu'. Kumpikaan ei voi koskaan olla.

Matematiikkaa ei voida koskaan täysin ratkaista Goedelin epätäydellisyyslauseiden vuoksi. Aina on totta tosiasioista luvuista, joista emme löydä todisteita.

Kuten maailmankaikkeudessa, emme voi koskaan tietää maailmankaikkeuden koko 'tilaa' (esim. Mitä jokainen atomi ja subatominen hiukkanen tekevät) nimenomaan Heisenbergin epävarmuusperiaatteen vuoksi. Emme voi koskaan toivoa kertovan, mitä havaittavan maailmankaikkeuden ulkopuolella tapahtuu suhteellisuusteorian takia.

Joten ne ovat jossain mielessä melko reilut vertailut shakkiin. Tiedämme paljon, mutta maailmankaikkeuden vuoksi, jossa elämme, emme koskaan tiedä kaikkea.

Parasta, mitä uskon shakin ratkaisemisessa voivamme toivoa, olisi erittäin heikko ratkaisu (johon mahdollisesti liittyy strategian varastaminen), joka osoittaa esim. pakotetun piirtämisen (tai paremman) valkoiselle lähtökohdasta ratkaisematta nimenomaisesti miten.

Saat mielenkiintoisen artikkelin loppupelitaulukoiden perusteista ja pelien ratkaisumenetelmistä, tarkista tämä. Tammi (PALJON yksinkertaisempi peli) ratkaistiin tasapeliksi yli vuosikymmen sitten.

MUOKKAA Häiriön poistamiseksi:

Kuten Näiden kolmen järjestelmän ratkaisemattomuus on valtavasti ja laadullisesti erilainen. Puutteellisuuslauseet johtuvat ensimmäisistä periaatteista ja ne pysyisivät voimassa KAIKESSA universumissa. Maailmankaikkeuden tilan ratkaisemattomuus perustuu sen henkilön fyysisiin lakeihin, jossa elämme. Shakin ratkaisemattomuus johtuu vain siitä, että maailmankaikkeus, jossa satutaan elämään, on liian pieni ja shakki on liian suuri ( vahva) liuos, jota pidetään sen sisällä. Syy siihen, miksi ne ovat tässä samanlaisia, ovat puhdas sattuma, yksinkertaisesti sivutuote maailmankaikkeudesta, jossa me kaikki sattuu asumaan

"Tiedämme paljon, mutta maailmankaikkeuden vuoksi, jossa elämme, emme koskaan tiedä kaikkea." No, se on minun mielipiteeni. kysyin erityisesti siitä, mitä vaiheita otamme "tietääksemme kaiken". se on loputon harjoittelu. On hämmästyttävää, kuinka niin monet lahjakkaat matemaatikot ovat ohittaneet shakin kuin vähäpätöinen asia, kuten he ohittivat taloustieteen, ehkä se onkin, mutta viime kädessä juuri shannon antoi oivalluksen. Kuvittele, mitä olisi tapahtunut, jos gauss, riemann olisi omistautunut jonkin aikaa shakkiin
Shakki on ratkaistavissa. Peano-aritmeettinen, siinä mielessä, että pystyy löytämään todistuksen jokaisesta tosi lausunnosta, ei ole. Kolme ensimmäistä kappalettasi on hölynpölyä matemaattisesta näkökulmasta.
Shakki on teoreettisesti ratkaistavissa kyllä. Mutta ei käytännössä ratkaistavissa. Joten inhimillisen tietämyksen osalta osittainen ratkaisu on paras, mitä voimme koskaan toivoa kaikissa kolmessa tapauksessa.
@DongKy, vastauksessasi sekoitetaan syy siihen, miksi shakki on ratkaisematon. Matematiikka ei ole ratkaistavissa ensimmäisten periaatteiden mukaan, maailmankaikkeus on ratkaisematon luonnon lakien asettamien muuttumattomien rajojen takia, mutta shakin tapauksessa kumpikaan syy ei päde, se on vain tilatilan koko, joka estää meitä ehtimästä sitä. Tämä tekee shakista todella mielenkiintoisemman, koska shakin tilatilan koko estää täydellisen ratkaisun, joten tutkimme enemmän likiarvojen ja epätäydellisten ratkaisujen tilaa, joista kumpikaan ei ole merkitystä matematiikan tai maailmankaikkeuden kannalta.
Fysiikkaa koskevasta kappaleestasi: Heisenbergin suhde ei estä meitä teoreettisesti tuntemasta koko maailmankaikkeuden kvanttitilaa, se vain kieltää meitä tuntemasta tiettyjen havaittavien arvojen arvoja samanaikaisesti. Tämä on oikeastaan ​​kysymys vain, jos on pakkomielle Newtonin määritelmälle "järjestelmän tila". Ymmärryksemme maailmankaikkeudesta ei johdu siitä, että emme tunne kaikkien hiukkasten impulssia ja asemaa samanaikaisesti, vaan siitä, että emme ymmärrä hallitsevia fyysisiä lakeja.
Tämä vastaus on täysin hölynpölyä. On pelejä, jotka on ratkaistu. Jos väität, että shakkia ei voida ratkaista, sinun on selitettävä, kuinka se eroaa peleistä, jotka voivat olla. Yleiset näkökohdat, kuten Godel ja Heisenberg, eivät voi kertoa tätä meille.
Kuten muut vastaukset ovat todenneet, tilatila on aivan liian iso. Se on suurempi kuin maailmankaikkeuden atomien määrä. Teoriassa se voidaan ehdottomasti ratkaista, koska se on rajallinen. Mutta käytännössä se ei voi.
[Menettävä shakki] (https://fi.wikipedia.org/wiki/Losing_chess) on ratkaistu kohtuullisen määritelmän mukaisesti, joten en ole varma, että nämä "tilatilan" argumentit pitävät vettä.
Shakin menettäminen on ratkaistu vain heikosti. Pakollisten sieppausten vuoksi sekä tilatila että haarautumistekijä ovat vähäisiä verrattuna normaaliin shakkiin. From http://magma.maths.usyd.edu.au/~watkins/LOSING_CHESS/ICGA2016.pdf "Lopullinen todistuskoko on noin 900 miljoonaa sijaintia." Vain 900 miljoonaa. Normaali shakki on monta, monta suuruusluokkaa enemmän asemia.
Käsitteellisesti on mahdollista, että shakki voitaisiin ratkaista pelipuulla, jolla on vain pieni osa laillisista valtioista. Sinulla voi olla kapea polku suuren tilatilan läpi. Olen samaa mieltä siitä, että tämä vastaus on järjetön (tosin mielenkiintoisella tavalla).
@JohnColeman Ehdotat jotain heikkoa muotoa ratkaisevaa shakkia. Myönnän, että se voi olla mahdollista. Mutta se ei ole sama kuin täydellinen vahva ratkaisu, jossa minkä tahansa oikeudellisen aseman W / L / D-tila tunnetaan
#5
+6
Kevin Wang
2020-07-08 23:39:20 UTC
view on stackexchange narkive permalink

En osaa vastata pääkysymykseesi, mutta alphazeroa koskevaan pisteeseen: minun näkökulmastani AlphaZero ei ole edes pieni askel kohti shakin ratkaisemista, vaikka se voi olla merkittävä askel ihmisten yli-inhimillisessä suorituksessa. >

jos voisimme seurata A0: ta suurilla investoinneilla, se voi viedä meidät hyvin kauas tuntemattomille alueille

En usko, että tämä on totta. Sen lähestymistavalla, joka on pelipuun tutkiminen poimimalla polkuja, joilla on suuri todennäköisyys olla hyvä, ei näytä olevan paljon merkityksiä shakin täydelliseen ratkaisemiseen. Vaikka shakissa voi olla erittäin hyvä olla erittäin hyvä, luulen, että tämä heuristinen lähestymistapa on vähemmän kannattava ratkaisemaan tarkasti shakkia kuin luulet.

Ollakseni erittäin hyväntekeväisyys, ehkä ... ja ehkä tarkoitan, että tämä on piirakka taivaalla -ajattelu, joka tuli juuri tyhmistä aivoistani ... ehkä AlphaZero-työ voisi joskus johtaa todisteeseen siitä, että harjoittelun myötä malli yhtyy malliin, joka pelaa oikein todennäköisyydellä 1 (ja 1 tässä tapauksessa on alias 99.999 ...%), mutta edes tätä ei voida pitää shakin "ratkaisuna", koska emme voi silti todistaa, että joku tosielämässä kouluttamamme malli tekee jokainen liike oikein.

".... Sen lähestymistapa, joka on pelipuun tutkiminen valitsemalla reittejä, joilla on suuri todennäköisyys olla hyvä" mitä vikaa tässä lähestymistavassa on?
@shashankshekharsingh En vain tiedä, miten se liittyy mahdollisuuteen ratkaista shakki kokonaan. Kuten sanoin, siinä ei ole mitään "vikaa" - se on erittäin hyvä pelaamaan pelejä paremmin kuin mitä olemme aiemmin nähneet, mutta en näe yhteyttä käsillä olevaan maaliin.
sanotaan hyvin, että on 10 ^ 40 [järkevää asentoa] (https://en.wikipedia.org/wiki/Shannon_number), a0 voi ainakin tuoda tämän luvun alaspäin tarvitsematta niitä suuria määriä tallennustilaa, koska se on paras shakki. ja sitten voidaan käyttää jotain muuta lähestymistapaa.
Käytetäänkö a0: ta edes shakin ratkaisemiseen, sanotaanko 8 kappaleen pöytäjalustat?
"Käytetäänkö a0: ta edes shakin ratkaisemiseen, sanotaanko 8 kappaleen pöytäjalustat?" Se on hyvä kysymys. En tiedä vastausta siihen.
@shashankshekharsingh Shakin ratkaiseminen vaatii todisteita. Suuri todennäköisyys ei ole sama kuin ratkaiseminen.
#6
+5
MattPutnam
2020-07-09 05:01:37 UTC
view on stackexchange narkive permalink

Muut ovat jo maininneet pöytäpohjat ja niiden kehityksen, mutta jotain, johon ei ole vielä puututtu, on shakin pelkkä avaruus monimutkaisuus.

Tarvitsemme funktion, jotta voimme sanoa, että shakki on ratkaistu. gameState -> move , ja tämä toiminto on määriteltävä kaikille pelin mahdollisille tiloille tai ainakin kaikille niille, joihin pelisäännöt ovat tavoitettavissa. Näitä on huomattavasti enemmän kuin havaittavissa olevassa universumissa on atomeja. Joten vaikka voimme jotenkin koodata jokaisen pelitilan ja sen vastaavan parhaan liikkeen yhdeksi atomiksi, aineessa ei ole tarpeeksi ainetta. maailmankaikkeudessa rakentaa palvelin, joka toimisi tietokannan kanssa.

Endgame-taulukon pohjat ovat mielenkiintoisia, mutta kukaan ei yritä vakavasti ratkaista shakkia.

Kuka sanoi, että funktion määrittelemiseksi kaikki mahdolliset tulot ja niiden lähdöt on tallennettava tietokantaan? Tällä argumentilla funktiota `f (x, y) = x + y` ei voida määritellä edes luonnollisille numeroille, koska luonnollisia lukuja on enemmän kuin universumissa on atomeja.
@LarsH-ratkaisua juuri tämä tarkoittaa tässä yhteydessä. Jos sanot, että se voi olla toiminto, jonka laskemme lennossa ... olemme palaamassa pelipuun hakuun.
@MattPutnam ".... mutta ei ole ketään, joka yrittää vakavasti ratkaista shakkia." No, se on varsinainen vastaus. :)
Matemaattinen todiste siitä, onko lähtökohta voitto vai pakotettu tasapeli, olisi eräänlainen shakin "ratkaisu" ilman, että se vaatii välttämättä raakavoiman tyhjentävää pöytäjalustaa.
@nanoman kyllä ​​tarkalleen. minua kiinnostaa enemmän tällainen ratkaisu kuin moottoripohjaiset raakavoimat. Shakiteoria on kehitettävä.
@Matt Ei välttämättä. Puunhaun lisäksi on monia tapoja, joilla toiminnot voidaan laskea lennossa.
#7
+2
Colin McDonagh
2020-07-10 16:05:12 UTC
view on stackexchange narkive permalink

Shirish Chinchalkarilla on paperi, joka laskee ylärajan ~ 10 ^ 46 shakin sijaintien lukumäärälle (eroaa ilmeisesti liikkeistä). Argumentit, joissa puhutaan atomien lukumäärästä maailmankaikkeudessa, ovat hyvin monimutkaisia ​​johtuen sijaintierojen käytöstä (voimme päästä vain toiseen paikkaan, joten miksi ei vain tallentaa liikkunutta kappaletta kokonaan uuden sijainnin sijasta?) Sekä puristus. IIRC, Syzygy-loppupelitaulukoissa, jokainen sijainti voidaan edustaa vähemmän kuin yhdellä bitillä, kun otetaan huomioon pakkaus.

Yksi asia, jota ihmettelen henkilökohtaisesti, ja voisin olla täysin väärin, onko tietyssä vaiheessa suhteellisen pieni monimutkaisuuden lasku n-> 32: na, koska aloitus solmuja on vähemmän.

Se on kuitenkin hämmästyttävä kysymys. Haluaisin nähdä sen (jopa heikosti) ratkaistun elämäni aikana.

Pika laskelma näyttää 3x10 ^ 23 mahdollista sijaintia, joista jotkut numerot eivät ole tavoitettavissa. Jokaiselle neliölle on 13 mahdollista tilaa - 6 kappaletta kummallakin puolella - sotilas, torni, ritari, piispa, kuningatar, kuningas ja yksi tyhjä tila. Neliöitä on 64 - joten 64 ^ 13 mahdollista paikkaa. Tämä näyttää paljon kohtuullisemmalta kuin 10 ^ 46, vaikka silti hyvin suuri määrä. sillä, että pelipuulla on 10 ^ 120 siirtoa (shannon-numero), ei ole merkitystä. sinun tarvitsee vain pitää 'yksi voitollinen liike' kullekin näistä 10 ^ 23 tilasta.
saavuttamattomissa valtioissa otettaisiin huomioon, että laudalla on aina vain 2 kuningasta, joissa on yhteensä 2048 paikkaa, enintään 64 kuninkaan sijasta. se rajoittaisi myös korkeintaan 8 sotilasta kukin (jälleen alas 64: stä), ja muilla kappaleilla olisi enimmäisrajat ylennyksen vuoksi - esimerkiksi 4 kuningattaret, 6 torni, 6 piispat ja 6 ritaria. matematiikkani on liian ruosteinen tämän laskemiseksi, mutta odotan, että mahdollisten kantojen suuruusluokitukset voidaan hylätä.
yksi viimeinen huomautus tavoittamattomista tiloista - tyhjiä välilyöntejä on oltava vähintään 32, enintään 61, joten kaikki tämän alueen ulkopuolella voidaan sulkea pois.
Hei Jim, se on oikeastaan ​​13 ^ 64 (~ 10 ^ 71) perustelusi mukaan. Joten antamiesi tietojen avulla voit vähentää niitä. Paikoissa otetaan kuitenkin huomioon myös se, onko valu mahdollista molemmille puolille ja onko kuljettajia. Katso täältä sijainti vs. kaavio: http://wismuth.com/chess/statistics-positions.html
Colin, se on noloa. kuten sanoin, matematiikkani on ruosteinen. mikä on väärän viestin etiketti? minun pitäisi poistaa se tai jättää se ylös? uskon, että seurantaviestit ovat kelvollisia. vielä yksi mielenkiintoinen rajoitin - kun 8 peliainetta rivillä 2, rivillä 1, 4 on vain 16 mahdollista tilaa kummallakin puolella, jolloin torni ja ritari voivat vaihtaa paikkaa tai ritaria ei ole siellä.
@Jim haha, älä huoli, me kaikki teemme virheitä. Olen tarkastellut tätä kaikkea aikaisemmin, joten kaikki alle 10 ^ 46 herätti epäilyksiäni. Jos olet liian hämmentynyt, voit poistaa sen, mutta mielestäni ei ole mitään syytä piilottaa virheitä. Joo, yksi ystäväni kirjoitti kerran pienen artikkelin samasta! Paljon pelinappulaita lähtöasennoissa todella rajoittaa kappaleiden mahdollisia sijainteja
@Jim Yritän tällä hetkellä julkaista pienen paperin sotilasasennoista. Lähetän sen tänne, jos se koskaan julkaistaan!
#8
+2
Federico Poloni
2020-07-11 10:54:16 UTC
view on stackexchange narkive permalink

Toinen hyökkäyslinja on vähentämässä ulottuvuutta: Gardnerin 5x5 minisekka on heikosti ratkaistu Mehdi Mhallan ja Frederic Prostin toimesta vuonna 2013. 3x3 ja 3x4 taulut ovat olleet voimakkaasti ratkaistu 2000-luvulla Kirill Kryukovin täydellisillä pöytälevyillä kullekin sijainnille, ja saman tekijän vuonna 2011 valmistuneet 9-miehen pöytäkannat 4x4-shakille.

#9
+1
Claus
2020-07-11 05:39:07 UTC
view on stackexchange narkive permalink

Luulen, että muut vastaukset ja kommentit ovat tehneet selväksi, että kyseessä on todella monimutkainen ongelma. Niin monimutkainen, ettei mikään klassinen tietokone tule koskaan sen lähelle.

Mutta olen esittänyt itselleni saman kysymyksen. Eikö shakki ole täydellinen esimerkki kvanttitietokoneen käytöstä? Vaikka kvanttitietokoneet eivät ole vielä täysin käyttövalmiita, on olemassa "ohjelmointikieliä", ja tällä tavalla kuvattuja kvanttitietokoneita varten on jo monia algoritmeja. Tosiasiassa on olemassa simulaattoreita näiden kvanttitietokoneiden "ohjelmien" ajamiseksi klassisissa tietokoneissa.

Mietin, kuinka mahdollista olisi kirjoittaa algoritmi shakin ratkaisemiseksi kvanttitietokoneella. Vai vaatisiko se niin monta qbitia, ettemme voi koskaan odottaa todellista kvanttitietokonetta, joka voisi käyttää tätä algoritmia? Mutta jos se olisi kerran olemassa, eikö sen pitäisi pystyä vastaamaan kysymykseen sekunnissa?

Pelkkä selvennys, koska mainitsin mahdollisuuden simuloida näitä algoritmeja klassisilla tietokoneilla. Tämä simulaatio tekee tietysti vain erittäin monimutkaisesta ongelmasta ratkaistun vielä vähemmän suorituskykyiseksi, joten näitä simulaattoreita voitiin käyttää vain algoritmin testaamiseen, ei todelliseen käyttöön.

todellisia kvanttitietokoneita ei tällä hetkellä ole, joten nuo algoritmit eivät tarkoita paljoakaan, koska et vieläkään saa kvanttitietokoneiden aikaetua. joten meidän on odotettava sitä
#10
-2
Richard Boone
2020-07-09 18:02:17 UTC
view on stackexchange narkive permalink

Luulen, että jokaisella täällä on hyvä ja välttämätön asia, kun shakin avaruuskompleksi on suurempi kuin havaittavissa olevan universumin atomien määrä. Luulen kuitenkin voivani lisätä siihen joitain lisäpisteitä.

  1. Kuten muut ovat huomauttaneet, "ratkaistun" määritelmä ei ole erittäin selkeä. Jos "ratkaistu" tarkoittaa "löytää optimaalinen siirtyminen mahdollisesta pelitilasta", shakin ratkaiseminen on mahdotonta. Jos kuitenkin pidämme ratkaisun tarkoittavana, että haluamme pelata vain yhtä "täydellistä" shakkipeliä, voimme ehkä vähentää avaruuden monimutkaisuutta.

  2. Ensimmäisen pisteen ongelma shakilla ei ole yhtä täydellistä peliä. Täydellinen shakkipeli tarkoittaa, että teet aina liikkeen, joka antaa sinulle suurimmat mahdollisuudet voittaa. Se tarkoittaa myös sitä, että olet kirjannut vastustajasi tekemään optimaalisia liikkeitä, koska muuten se ei olisi täydellinen peli (ja rikkaisi myös edelliset avaruuden monimutkaisuuteen liittyvät kysymykset). Shakki on kuitenkin tasapainoinen peli, ja kaikki täydellisesti pelatut pelit väistämättä päättyvät tasapeliin.

  3. On todennäköisesti lähes ääretön määrä optimaalisesti pelattuja pelejä, jotka päättyvät piirtää. Vaikka optimaalisten siirtojen määrä mistä tahansa asennosta on paljon pienempi kuin mahdollisten siirtojen lukumäärä, meillä on tänään parhaiden shakkimoottoreiden mukaan monia liikkeitä, joilla on lähes optimaaliset tulokset lähtöasennosta ja muutamalla ensimmäisellä liikkeellä. Koska minkä tahansa shakkipelin voittamiseksi tarvitaan merkittävä etu, monet näistä liikkeistä todennäköisesti sisällytetään "täydelliseen" tai ratkaistuun peliin.

  4. Lopuksi, miten todistaisit Omat vai väärät kohdat 2 ja 3? Et voi. Jälleen törmäät avaruuden monimutkaisuuteen. Jos haluat todistaa minkä tahansa sijainnin olevan joko voitettavissa tai voittamaton, jos molemmat pelaajat pelaavat optimaalisesti, sinun on piirrettävä kaavio jokaisesta mahdollisesta siirrosta tietystä sijainnista. Kuten olemme aiemmin osoittaneet, tämä on mahdotonta, ennen kuin olemme alle tietyn kappalemäärän.

En ole varma, ymmärrätkö mitä pelin "ratkaiseminen" tarkoittaa. Kun olet "ratkaissut" pelin, sinulla on strategia, jolla voitat aina (kuten nappuloiden kohdalla, mikä on ratkaistu), tai joissakin peleissä aina tasapeli (kuten tic-tac-toe). Se ei ole pelata vain "yhtä täydellistä peliä"
"On todennäköisesti lähes ääretön määrä optimaalisesti pelattuja pelejä, jotka päättyvät tasapeliin.": * Uskotaan *, että optimaalisesti pelattu shakkipeli on tasapeli. * todistaa * se olisi valtava askel kohti shakin ratkaisemista.
@KevinWells "Ratkaisun" määritelmää ei ole shakissa, joten se tekee keskustelusta vähemmän kiinnostavan. (Et voi pakottaa voittoa kaikilta mahdollisilta pelipaikoilta, eikä ole selvää, että voisit myöskään pakottaa voiton lähtökohdasta.)
@jpaugh Mitä muuta "ratkaisun" määritelmää käytät sitten? Tämän kysymyksen pääasia on, pystymmekö pääsemään kohti tätä päämäärää, ja jos on, mitä ponnisteluja tähän tehdään. Todellinen vastaus on, että shakin ratkaiseminen on tällä hetkellä varmasti ulottumattomissa, eikä se välttämättä koskaan ole tavoitettavissa, mutta yhä on pyrittävä parantamaan tietämystämme yhä monimutkaisempien lähtökohtien ratkaisemisesta
@KevinWells Entä jos voisit tietää minkä tahansa pelin lopputuloksen, kun otetaan huomioon lähtöasema, ja kaksi vastustajaa, jotka pelaavat täydellisesti? Shakin ratkaiseminen ei tarkoita * yksittäisen * pelin voittamista, vaan jokaisen pelin lopputuloksen ennustaminen riittävän hyvin, jotta saat parhaan mahdollisuuden voittaa.
@jpaugh Neljäs kohta vastasi kysymykseesi. Et voi tietää minkään pelin lopputulosta tietystä lähtöasemasta, koska se olisi monimutkaisuudeltaan sama kuin kaikkien mahdollisten pelattavien pelien lopputuloksen tunteminen. Kuten muissa vastauksissa on käsitelty, tämä on mahdotonta.
@jpaugh Jokaisen mahdollisen pelin ratkaiseminen lähtökohdasta on juuri se, mistä puhun. Sanoin jopa, että pelin ratkaiseminen ei ole yhden täydellisen pelin pelaamista, juuri sitä sanotkin, joten en ymmärrä kritiikkiäsi. Sanoit, että se on huono määritelmä, koska se ei ole shakin ulottuvilla, mutta se ei tee siitä huonoa määritelmää, se vain tekee vastauksesta ikävystyttävän


Tämä Q & A käännettiin automaattisesti englanniksi.Alkuperäinen sisältö on saatavilla stackexchange-palvelussa, jota kiitämme cc by-sa 4.0-lisenssistä, jolla sitä jaetaan.
Loading...