Aantal mogelijke schaakstellingen

[Verwijderd]

Ik heb net een 2 voor wiskunde-b2 teruggekregen dus ik vrees dat ik me even zal moeten terugtrekken in een sfeer van diepe mistroostigheid en zodoende niet in staat zal zijn je met dit wiskundige probleem je te helpen .

[Lord Daemon]

Dido schreef op 08 november 2002 @ 15:58:
Aangezien er (hoeveel dan ook) een beperkt aantal zetten is, is er een oplossing (de perfecte schaakpartij met altijd dezelfde uitkomst).

Het lijkt me uiterst onwaarschijnlijk dat er een unieke oplossing voor het schaakspel bestaat. De perfecte schaakpartij zal dan ook niet bestaan; ik vermoed dat er bijzonder veel manieren zijn waarop via perfect spelen remise bereikt wordt.

Verwijderd schreef op 11 November 2002 @ 02:45:
Shannon, de grondlegger van oa. het computerschaak zat met de zelfde vraag. De Groot hat al eerder vastgesteld dat er in een middenspelpositie gemiddeld 38 volgzetten zijn, Shannon berekende dergelijke gemiddelden ook voor openingen en eindspelen, en ging uit van een gemiddelde partijlengte van 40 zetten (ervaringswaarde uit het schaak, vandaar de 40-zetten regel). Zijn eindwaarde: 10¹²⁰ mogelijke varianten in het schaakspel. Dit is dus een gemiddelde waarde, maar dat is het beste wat je hier te bieden hebt.

Zoals ik in de vorige draad al beargumenteerde: hoewel de gemiddelde partij wellicht 40 zetten duurt (er is overigens gaan 40-zetten regel maar een 50-zetten regel), is het zinloos om dit te gebruiken om het aantal mogelijke partijen te berekenen. De meeste mogelijke partijen zullen veel langer zijn; een grotere lengte betekent immers meer mogelijke varianten. (Wanneer je in de buurt van het maximum aantal zetten komt wordt dit natuurlijk minder.)

[Verwijderd]

Gaarne zou ik mijn nederige instemming met bovenbezichtbare bijdrage betuigen .

[Verwijderd]

Lord Daemon schreef op 11 november 2002 @ 21:53:
Zoals ik in de vorige draad al beargumenteerde: hoewel de gemiddelde partij wellicht 40 zetten duurt (er is overigens gaan 40-zetten regel maar een 50-zetten regel), is het zinloos om dit te gebruiken om het aantal mogelijke partijen te berekenen. De meeste mogelijke partijen zullen veel langer zijn; een grotere lengte betekent immers meer mogelijke varianten. (Wanneer je in de buurt van het maximum aantal zetten komt wordt dit natuurlijk minder.)

Shannon houdt in zijn formule rekening met de combinatorische explosie, dus die vlieger gaat niet op. De partijlengte in het schaak is direct gerelateerd aan het talent van de spelers, twee beginners spelen makkelijk een partij van 80 zetten, twee grootmeesters halen meestal de onderbreking (bij 40 zetten) niet. Shannon houdt idd. geen rekening met beginnersfouten zoals het missen van een mat in 1 of een afgedwongen remise missen en vervolgens verliezen. Ook houdt hij geen rekening met opzettelijk tempoverlies zoals bv. het einde van een partij rekken door zetherhaling. Maw. Shannon probeert een cijfer te geven voor het aantal varianten in het schaak zoals het gespeeld wordt door intelligente spelers die spelen op winst of remise.

[Verwijderd]

Even half ontopic:

Hier het verhaal over Short en Fischer. Dat is een leuk verhaal door Mr chess himself Tim krabbe! Ook leuk voor mensen die niet kunnen schaken.

http://www.xs4all.nl/~timkr/admag/guest.htm


Even helemaal ontopic over het aantal schaakstellingen:

Hoe ga je om met al die stellingen die niet kunnen? Als je het absoluut aantal stellingen neemt die er mogelijk zijn, bestaan er ook stellingen waarbij de koning 10 x schaak staat. Echter dit bestaat niet. Hooguit 2x (en dat is al een uitzondering) met het fenomeen aftrekschaak.

Nog een voorbeeld: Al de stukken kunnen in principe naast elkaar staan behalve de koningen! Die mogen NOOIT naast elkaar staan. Als de witte koning op g1 staat, zijn er nog 58 posities over voor de zwarte koning! Koning op veld c3 betekent 55 posities mogelijk voor zwarte koning!! Koning op A1, betekent 60 mogelijkheden voor zwarte koning! Ga je dat allemaal uitrekenen??

Ik ben slecht in wiskunde:(, kan je dus niet helpen! Kan overigens wel schaken!

-----------------------------------------------------------------------------------------------------
edit: het is idd de 50 zetten regel. Voor de duidelijkheid: Dit is een regel die er voor zorgt dat een partij in theorie niet oneindig lang kan duren. Wat is de 50 zetten regel???

Wanneer er 50 zetten lang, geen enkel stuk is geslagen EN geen enkele pion verschoven, dan KAN 1 van beide spelers remise claimen. Kortom: compleet niet relevant voor deze discussie.

[Verwijderd]

De partijlengte lijkt me in ieder geval ook gerelateerd aan het krachtsverschil tussen de spelers. Dat partijen tussen betere schakers vaak korter dan 40 zetten zijn kan te maken hebben met de 'tactische remise' en met het feit dat sommige partijstellingen te oninteressant gevonden worden om er nog veel energie in te steken (onterecht natuurlijk, zoals de allergrootste schakers herhaaldelijk hebben bewezen). Je kunt er eigenlijk best van uitgaan dat een door twee partijen perfect gespeelde (en uitgespeelde) partij behoorlijk lang zal duren.
Om het aantal mogelijke schaakstellingen te bepalen lijkt me Shannons op de praktijk gebaseerde aanpak niet bruikbaar. Iedere schaker met enige ervaring begrijpt dat de hoeveelheid praktijkstellingen veel en veel kleiner is dan het aantal mogelijke stellingen. Wat is trouwens een 'combinatorische explosie' ?

[Verwijderd]

[quote]Verwijderd schreef op 08 november 2002 @ 13:08:
offtopic: d2-d4 is absoluut niet de beste openingszet

sorry hoor, maar wat een bullshit. Er bestaat helemaal niet zoiets als een beste openingzet.

laten we in ieder geval vaststellen dat de 2 meest gespeelde openingszetten e2-e4 en d2-d4 zijn. d2-d4 wordt de laatste tijd nog vaker gespeeld dan e2-e4 zelfs!

ps. kasparov speelt het ook zeer regelmatig! *punt is nu wel gescoord dacht ik zo*

[Verwijderd]

Diadem schreef op 09 November 2002 @ 18:43:Het exacte aantal legale schaakstellingen is eigenlijk onmogelijk te geven. Er zijn teveel dingen die meespelen.

Ik denk dat dat exacte aantal wel te geven is. Hoewel er superveel complexe factoren meespelen; dat aantal factoren is eindig. Ik denk wel dat er een computer voor nodig is (voor iedere stelling moet je bijvoorbeeld controleren of niet beide koningen schaak staan, en als je dat met de hand voor iedere stelling moet nagaan ben je nog wel een tijdje bezig ). Ook zal het jaren duren om een computerprogramma te schrijven dat al die standen kan berekenen, en ook nog eens jaren om dat computerprogramma het rekenwerk te laten doen. Maar het aantal stellingen is niet oneindig, dus IMHO berekenbaar.

jvdmeer schreef op 08 November 2002 @ 11:45:[droom]Het leek mij fantastisch om het hele spel van begin tot eind door te rekenen en zodra dat klaar was vanuit alle eindstellingen de hoeveelheid kans op winst te berekenen en dit noteren per stelling. Om zodoende terug te rekenen naar de beginstelling te gaan, en dan exact te weten dat D2-D4 absoluut de beste openingszet is.[/droom]

Ik vraag me af of je bij zo'n spel wel van kans kan spreken, omdat de manier waarop je tegenstander speelt niet willekeurig is. Misschien is de "kans" dat je met D2-D4 wint wel groter dan bij andere zetten, maar als die kans kleiner is dan 1 (of 100, in procenten), kan je tegenstander dus nog steeds winnen, zolang hij maar de goede zetten speelt.

[Terror]

betekent een eindig aantal stellingen ook per definitie dat het probleem oplosbaar is? heb laatst bij discrete wiskunde niet zo goed opgelet toen het over de complexiteit van een algoritme ging. Maar volgensmij ging die vlieger niet altijd op.

[Lord Daemon]

Terror schreef op 12 November 2002 @ 20:47:
betekent een eindig aantal stellingen ook per definitie dat het probleem oplosbaar is? heb laatst bij discrete wiskunde niet zo goed opgelet toen het over de complexiteit van een algoritme ging. Maar volgensmij ging die vlieger niet altijd op.

Niet als het oneindig lang kan kosten om een stelling te testen, maar dat geldt hier niet. Schaken is dus in principe oplosbaar. In de praktijk echter niet.

[FreeBee]

Ik kwam deze url tegen http://www.xs4all.nl/~timkr/admag/biljoen.htm. Volgens Tim Krabbé zijn er slechts 43600 verschillende zetten mogelijk. Heb het niet nagerekend hoor. Dit kan misschien helpen om het aantal stellingen te vinden.

[Terror]

Staat helaas niet bij waar die dat getal vandaan tovert.

Om met de eerste vraag te beginnen: na enig tellen en rekenen kwam ik op een totaal van 43660 verschillende schaakzetten. Daarbij heb ik alle zetten absoluut genomen; dat wil zeggen dat Pg1-f3 iets anders is dan Pb1-c3, en ook dan Pg8-f6 of Pg1-f3 van Zwart, en óók iets anders dan Pg1xf3, dat weer tien verschillende zetten kan zijn, afhankelijk van wie wat slaat - wPg1xTf3 is iets anders dan wPg1xLf3 of zPg1xLf3. De gevolgen van een zet (mat, pat, schaak, dubbelschaak) telde ik niet mee.

In deze alinea komt ie met dat getal en dat wrdt vervolgens nergens anders uitgewerkt.

Wat ik trouwens in dit topic niet uit elkaar kan halen is of het aantal mogelijke zetten of het aantal mogelijke partijen bedoeld wordt. in een partij kan een bepaalde zet meerdere keren voorkomen. Het aantal mogelijke zetten is dan veel minder. Maar ik zal mijn gedachte eens hier neer gooien.

Even een naar boven afgeschatte waarde. Die hoger uitkomt dan de waarde die we zoeken als we het over het aantal mogelijke zetten in een spel hebben:
Het stuk wat je op de meeste plaatsen op het word weg kan zetten vanuit het midden van het bord is de koniging. Stel deze staat op D3 (of D4 of C3 of C4) Deze kan dan op 4+4+4+4+3+3+3+3=28 mogelijke vakken weggezet worden (4 kanten diagonaal en 2 horizontaal en 2 verticaal). Deze situatie is het groots aantal mogelijkheden voor 1 stuk. Andere stukken hebben minder mogelijkheden.

Stel dat elk stuk overal kan staan. (kan in werkelijkheid niet dus antwoord zal naar boven afwijken) Elk stuk kan dus op 64 posities staan. Laten we er van uit gaan dat ze vanuit elk van die positie naar die 28 andere vakjes kunnen. (in werkelijkheid is dit minder dus antwoord zal weer hoger uitvallen). Het aantal mogelijke zetten zal dus minder zijn dan 28(=aantalmogelijke opties voor een stuk)x64(=aantalvakken waar die kan staan)x32(=aantalstukken)= 57344 mogelijke zetten als bovengrens. Dit is heel ruim en als Mister Tim dit op 43K schat vind ik dat ook goed

Laten we voor het gemak uitgaan van 40K mogelijke zetten, hoeveel unieke partijen kan je met deze zetten spelen? Dat ligt aan het aantal zetten wat je gebruikt. Stel alle partijen 120 zetten duren. Dan kies je 120 zetten uit die 40K mogelijke.

Dan krijg je 40K boven 120 ofzo. In bovenstaande kan natuurlijk een veel betere schatting gemaakt worden worden van het aantal mogelijke zetten. maar feit is dat het aantal mogelijke zetten het hele spel door variabel is. Stel we maken een bruut force programma dat alle stellingen mogelijk door rekent. Dan ga je alle 40K boven n mogelijkheden na waarbij n tot een aantal zetten nadert waarna er geen partijen meer zijn met meer mogelijke zetten. Juist!, Das die 40K die we net bepaald hebben.

Dus je krijgt de sommatie van n is 1 tot 40K van 40K boven n. Enige waar nu geen rekening mee wordt gehouden is dat een zet 2 keer voorkomt in een partij volgensmij. Kan iemand deze afschatting is door een wiskunde programma laten benaderen die wat power mag gebruiken? Maple doet hier 5 sec over 40K boven 2K en voor 10K boven 120 geeft ie een 1 voor terug wat niet klopt

voor n tot 500 komt er iig iets uit groter dan 10^1100 Denk zelfs dat de waarde die marcelio in gedachte had (zie openingspost) misschien zelfs aan de lage kant is.

[ Voor 0% gewijzigd door Terror op 13-11-2002 02:32 . Reden: Taal en rekenfouten er zoveel mogelijk uitgehaald en layout aangepast. ]

[Verwijderd]

Nog even een vraagje: Maakt het nog verschil uit of wit aan zet is of zwart? Ook als de stukken precies het zelfde staan?

Volgens mij kan het getal (dat het aantal mogelijke stellingen aangeeft) sowieso niet groter zijn dan 3,2 * 10 ^ 52 (daarbij ga ik er trouwens vanuit dat wit aan zet of zwart aan zet een verschil uit maakt). Er moeten namelijk sowieso 32 vakjes leeg zijn. Er zijn 64!/(32!*(64-32)!) manieren om 32 vakjes van de 64 leeg te laten. Verder moeten er van de 32 overige vakjes 2 koningen zijn. Om 2 koningen op 32 vakken te plaatsen zijn er 32!/(2!*(32-2)!) manieren. Voor de overige vakken zijn er per vak 13 mogelijkheden: 1) Pion wit 2) Pion zwart 3) Toren wit [...etc...] 11) vak is leeg (de koningen hadden we al, nog 5 stukken per speler over, en de mogelijkheid dat het vak leeg is). Daarvoor zijn nog eens 11^30 mogelijkheden. Dan moet de uitkomst ook nog met 2 worden vermenigvuldigd als je verschil maakt tussen wit aan zet/zwart aan zet (schaaktechnisch gezien kan dat het verschill tussen winst en verlies zijn). Alles bij elkaar vermenigvuldigd komen we op grofweg 3,2 * 10^52. (En ja, ik ben mij er van bewust dat waarschijnlijk meer dan 95% van deze stellingen gewoon helemaal niet kunnen)

[Verwijderd]

Terror schreef op 13 november 2002 @ 01:18:
Wat ik trouwens in dit topic niet uit elkaar kan halen is of het aantal mogelijke zetten of het aantal mogelijke partijen bedoeld wordt.

Geen van beide, dacht ik. Het gaat over het aantal stellingen, dus het aantal manieren om 32 of minder stukken op het schaakbord te plaatsen, op zo'n manier dat die stellingen in theorie allemaal tot stand zouden kunnen komen in een partij waar de regels in acht worden genomen.

[jvdmeer]

Verwijderd schreef op 13 November 2002 @ 09:13:
[...]

Geen van beide, dacht ik. Het gaat over het aantal stellingen, dus het aantal manieren om 32 of minder stukken op het schaakbord te plaatsen, op zo'n manier dat die stellingen in theorie allemaal tot stand zouden kunnen komen in een partij waar de regels in acht worden genomen.

Perfect samengevat... Niets aan toe te voegen.

[Verwijderd]

Krabbé zegt zelf toch duidelijk wat hij bedoelt:

Dit wierp een paar vragen op: hoeveel verschillende zetten zijn er eigenlijk; hoeveel zetten zijn er in totaal in de schaakgeschiedenis gespeeld; en welke zetten zijn misschien nog nooit gespeeld?

Het getal 43600 betreft de zet op zichzelf, dus ongeacht de stelling waarin deze wordt uitgevoerd. Vervolgens maakt hij een schatting van "[h]et totaal aantal gespeelde zetten sinds het schaakspel, eind 15e eeuw, zijn moderne regels kreeg". Hier heeft hij het dus over het aantal malen dat een speler een stuk opnam om een zet uit te voeren (volgens zijn schatting 1 biljoen keer). Beide getallen staan geheel los van stellingen waarin de zetten worden uitgevoerd, en zeggen dus ook niets over het aantal mogelijke stellingen.

[Diadem]

Zoals ik hierboven al eerder had gezegd is het aantal verschillende stellingen met dezelfde stukkenstand 160. (En dus niet 2 zoals sjoulibsky hierboven nog beweerd). Ik vond toevallig in die verzameling artikel van Tim Krabbe (waar al vaker naar is gelinkt in deze thread) een artikel wat daar over gaat. (Hij zegt 170, maar het omdraaien van het bord is natuurlijk niet relevant in dit geval. Dat is een andere stukkenstand, alleen niet herkenbaar van alleen een foto).

Naar Bobby Fishers exact uitspraak over God ben ik nog steeds op zoek, maar ik kan hem vreemd genoeg niet vinden.

Verwijderd schreef op 12 november 2002 @ 17:07:

Ik denk dat dat exacte aantal wel te geven is. Hoewel er superveel complexe factoren meespelen; dat aantal factoren is eindig. Ik denk wel dat er een computer voor nodig is (voor iedere stelling moet je bijvoorbeeld controleren of niet beide koningen schaak staan, en als je dat met de hand voor iedere stelling moet nagaan ben je nog wel een tijdje bezig ). Ook zal het jaren duren om een computerprogramma te schrijven dat al die standen kan berekenen, en ook nog eens jaren om dat computerprogramma het rekenwerk te laten doen. Maar het aantal stellingen is niet oneindig, dus IMHO berekenbaar.

Ik heb nooit gezegd dat het aantal stellingen niet eindig is. En ik heb nooit gezegd dat in principe het aantal exacte stellingen niet te berekenen zou zijn. Ik heb alleen gezegd dat het in praktijk niet te doen is. En dat is het ook niet.

Er zijn gewoon teveel variabelen waar je rekening mee moet houden. De bovengrens van ~ 10⁵⁰ is natuurlijk veel en veels te hoog, maar je zult niet ontkomen aan het doorrekenen op legaliteit van toch een aantal stellingen wat in de buurt van dat getal komt.

En dan rijst er nog de vraag of een stelling die niet in overtreding is van de spelregels (geen pionnen op de eerste tij, koningen naast elkaar, etc) maar nooit bereikt kan worden legaal is. Het zijn mogelijke schaakstellingen zoals een componist ze kan maken, maar in een partij kunnen ze niet voorkomen. Wil je alleen stellingen hebben die in een partij daadwerkelijk kunnen voorkomen, dan zul je wil je alle stellingen vinden of vanuit de beginpositie alle mogelijke stellingen (en dus partijen) door moeten rekenen, of een algoritme zien te vinden wat bij elke stelling binnen afzienbare tijd kan ontdekken of deze berijkt kan worden. Ga er maar aan staan.

En dan hebben we ook nog de praktijk. Zo zijn er partijen tussen grootmeesters bekend waarin wit twee keer rocheert (ja, echt waar), of waarin na afloop van de tijdnoodfase beide koningen schaak staan. Hierdoor ontstane stellingen zijn overduidelijk niet legaal, maar het feit dat ze in de praktijk voorkomen bewijst dat het mogelijke schaakstellingen zijn

[Diadem]

Verwijderd schreef op 13 November 2002 @ 08:54:
Nog even een vraagje: Maakt het nog verschil uit of wit aan zet is of zwart? Ook als de stukken precies het zelfde staan?

Volgens mij kan het getal (dat het aantal mogelijke stellingen aangeeft) sowieso niet groter zijn dan 3,2 * 10 ^ 52 (daarbij ga ik er trouwens vanuit dat wit aan zet of zwart aan zet een verschil uit maakt). Er moeten namelijk sowieso 32 vakjes leeg zijn. Er zijn 64!/(32!*(64-32)!) manieren om 32 vakjes van de 64 leeg te laten. Verder moeten er van de 32 overige vakjes 2 koningen zijn. Om 2 koningen op 32 vakken te plaatsen zijn er 32!/(2!*(32-2)!) manieren. Voor de overige vakken zijn er per vak 13 mogelijkheden: 1) Pion wit 2) Pion zwart 3) Toren wit [...etc...] 11) vak is leeg (de koningen hadden we al, nog 5 stukken per speler over, en de mogelijkheid dat het vak leeg is). Daarvoor zijn nog eens 11^30 mogelijkheden. Dan moet de uitkomst ook nog met 2 worden vermenigvuldigd als je verschil maakt tussen wit aan zet/zwart aan zet (schaaktechnisch gezien kan dat het verschill tussen winst en verlies zijn). Alles bij elkaar vermenigvuldigd komen we op grofweg 3,2 * 10^52. (En ja, ik ben mij er van bewust dat waarschijnlijk meer dan 95% van deze stellingen gewoon helemaal niet kunnen)

Voor het aantal mogelijke stukkenstellingen maak je exact dezelfde berekening als ik in die andere thread. Op een klein foutje na: "Om 2 koningen op 32 vakken te plaatsen zijn er 32!/(2!*(32-2)!) manieren." Dit klopt niet, want een witte koning is wat anders dan een zwarte, je smokkelt hier dus een factor twee.

Het correcte antwoord volgens deze methode luidt dus: 160 * 64!/(32!*(64-32)!) * 32! / 30! * 11³⁰ = 160 * 64! / (32! * 30!) * 11³⁰ = 5.1 * 10⁵⁴

[Verwijderd]

Diadem schreef op 13 November 2002 @ 10:31:
[...]


Voor het aantal mogelijke stukkenstellingen maak je exact dezelfde berekening als ik in die andere thread. Op een klein foutje na: "Om 2 koningen op 32 vakken te plaatsen zijn er 32!/(2!*(32-2)!) manieren." Dit klopt niet, want een witte koning is wat anders dan een zwarte, je smokkelt hier dus een factor twee.

Het correcte antwoord volgens deze methode luidt dus: 160 * 64!/(32!*(64-32)!) * 32! / 30! * 11³⁰ = 160 * 64! / (32! * 30!) * 11³⁰ = 5.1 * 10⁵⁴

Goh, du hast recht! .

Nu hoeven we alleen nog maar een computerprogrammatje te schrijven dat al die stellingen gaat toetsen aan een paar voorwaarden, waar 'ie een jaar of 80 mee bezig is .

[Terror]

jvdmeer schreef op 13 november 2002 @ 09:52:
[...]


Perfect samengevat... Niets aan toe te voegen.

Hehe, heb ik een lang verhaal voor niets geklust

[EXX]

Kun je niet met een recursief algoritme alle stellingen laten bepalen dmv backtracking en trail and error? Een beetje zoals het 8 koninginnen probleem. Je begint gewoon met de eerste mogelijke zet, borduurt daar op verder met weer de eerste mogelijke zet etc. Op een gegeven moment kun je niet meer zetten en dan ga je 1 stap terug en doet de tweede mogelijke zet. Je loopt als het ware 1 gigantische boomstructuur door. En dan maar tellen hoeveel branches je hebt.

Ik ben wel bang dat het lang gaat duren Misschien iets voor een Beowulf cluster. Lijkt me echt iets voor parallel computing.

[Terror]

EXX schreef op 13 november 2002 @ 12:01:
Kun je niet met een recursief algoritme alle stellingen laten bepalen dmv backtracking en trail and error? Een beetje zoals het 8 koninginnen probleem. Je begint gewoon met de eerste mogelijke zet, borduurt daar op verder met weer de eerste mogelijke zet etc. Op een gegeven moment kun je niet meer zetten en dan ga je 1 stap terug en doet de tweede mogelijke zet. Je loopt als het ware 1 gigantische boomstructuur door. En dan maar tellen hoeveel branches je hebt.

Ik ben wel bang dat het lang gaat duren Misschien iets voor een Beowulf cluster. Lijkt me echt iets voor parallel computing.

lijkt me heel reeeël maar is dan wel handig om een leuke afschatting te hebben wat je kan verwachten. Gewoon brute force beginnen aan iets wat een millennium aan computing power kost wil je niet. Je wil nu kunnen zeggen van. Als ik nu begin heb ik het antwoord binnen nu en 2 jaar. Maybe een leuke voor een distruebet T.net computer projectje? En dan een stellingen per dag rating

[Verwijderd]

EXX>> je kunt wel een recursief enumererend algoritme opstellen, maar zelfs met alle beowulf clusters ter wereld gaat het nog miljarden jaren duren. Het in de (computer)schaaktheorie algemeen aanvaarde cijfer van Shannon is nogal groot, en zelfs als je 1 biljoen varianten per seconde doorrekent zit je nog in de orde van 10⁸⁴ jaar voordat je klaar bent.

_{Over de mensen die tegen het cijfer van Shannon argumenteren: doe dat maar tegen de talloze schaaktheoretici die deze schatting publiceren; ik heb geen zin in argumenteren tegen beter weten in.}

[Diadem]

Verwijderd schreef op 13 november 2002 @ 12:33:

_{Over de mensen die tegen het cijfer van Shannon argumenteren: doe dat maar tegen de talloze schaaktheoretici die deze schatting publiceren; ik heb geen zin in argumenteren tegen beter weten in.}

Shannon's schatting staat niet ter discussie, maar deze thread gaat over een ander probleem. De topicvraag is naar het aantal verschillende schaakstellingen, Shannon's schatting gaat over het aantal mogelijke verschillende schaakpartijen. Dit is vanzelfsprekend een veel groter getal. Als ik mij niet vergis stelt Shannon dan ook nog eens de voorwaarde dat de schaakpartij niet alleen legaal is, maar ook nog min of meer niet absurdistisch, maw dat de spelers dus enigszins normaal spelen.

[jvdmeer]

EXX schreef op 13 november 2002 @ 12:01:
Kun je niet met een recursief algoritme alle stellingen laten bepalen dmv backtracking en trail and error? Een beetje zoals het 8 koninginnen probleem. Je begint gewoon met de eerste mogelijke zet, borduurt daar op verder met weer de eerste mogelijke zet etc.

Dit was inderdaad mijn idee, en daar had ik ook een kleine start meegemaakt... Ik ben begonnen op een 3x3 schaakbordje met alleen 6 pionnen. De winnaar werd bepaald aan het aantal pionnen dat de overkant haalde. Bij 3x3 leverde dat 27 mogelijke stellingen op.
Bij een bordje van 4x4 waren dat er al rond de 1000. En bij een bordje van 5x5 (nog steeds met alleen 2x5 pionnen waren er inmiddels ongeveer 27000 unieke stellingen.) Getallen doe ik nu even uit m'n hoofd, maar de orde van grootte klopt redelijk. Ondanks de 27000 stellingen, was de computer nog steeds nauwelijks belast. Dus ik vroeg me af in waar ik aan moet gaan denken met een compleet bord.

EXX schreef op 13 november 2002 @ 12:01:Op een gegeven moment kun je niet meer zetten en dan ga je 1 stap terug en doet de tweede mogelijke zet. Je loopt als het ware 1 gigantische boomstructuur door. En dan maar tellen hoeveel branches je hebt.

Zo'n boom genereert veel te veel branches. Zoals ik eerder vermeld zal 1. d4 d5 2. Pc3, dezelfde stelling geven als 1. Pc3 d5 2. d4. Op jouw manier volgen hier 2 branches uit met ieder weer miljarden antwoorden.

EXX schreef op 13 november 2002 @ 12:01:Ik ben wel bang dat het lang gaat duren Misschien iets voor een Beowulf cluster. Lijkt me echt iets voor parallel computing.

Met parallel-computing zou het eventueel kunnen, maar voor distributed computing is dit geen optie. Distributed computing is nuttig als een hoop data moet worden verwerkt waar weinig antwoorden uitvolgen. Hier is probleem dat het omgekeerd is: weinig data (1 stelling) geeft een hoop antwoorden (30 nieuwe stellingen). Er is dus echt sprake van: 1 gek kan meer vragen stellen dan 10 wijzen kunnen beantwoorden. Elke keer als een node een stelling heeft ontvangen kan hij er weer een ongelooflijk aantal terug sturen. De centrale node zou dus bezwijken onder nieuwe stellingen die uitgedeeld moeten worden.

[PrinsEdje80]

jvdmeer schreef op 08 November 2002 @ 13:32:
Wat ik zoek is een manier om alle stellingen uniek te nummeren in zo min mogelijk ruimte. nu zit ik dus op 256 bits. En volgens mij moet dat minder kunnen worden.

Iig kun je met 3x3bit af voor de locatie (a t/m h en 1 t/m 8 ) en je hebt dan maar 1 t/m 6 nodig voor het schaakstuk, maw nog 3 bit, in totaal 27 bit. Reducering van bijna 90%...

Maar dan heb je dus eigenlijk 4 byte nodig per positie.. Kost wat codeer werk, maar dan heb je ook wat...

[ Voor 0% gewijzigd door PrinsEdje80 op 13-11-2002 13:29 . Reden: 8) is vervelend en opmerking. ]

[EXX]

jvdmeer schreef op 13 november 2002 @ 13:20:
[...]
Zo'n boom genereert veel te veel branches. Zoals ik eerder vermeld zal 1. d4 d5 2. Pc3, dezelfde stelling geven als 1. Pc3 d5 2. d4. Op jouw manier volgen hier 2 branches uit met ieder weer miljarden antwoorden.

Eeeh, dat klopt idd. Je moet controleren af je de stelling al gehad hebt voordat je de branch verder vervolgt. Nog meer rekenwerk dus. Bovendien moet je dan alle gevonden stellingen gaat opslaan. Het doorzoeken van die database wordt op den duur een gigantische klus.

[bankrupcy]

En als je nu niet nagaat welk stuk waar staat, maar bekijkt of op een veld een bepaald stuk (kan) staan?

(Ik roep ook maar wat)

[jvdmeer]

PrinsEdje80 schreef op 13 November 2002 @ 13:28:
[...]


Iig kun je met 3x3bit af voor de locatie (a t/m h en 1 t/m 8 ) en je hebt dan maar 1 t/m 6 nodig voor het schaakstuk, maw nog 3 bit, in totaal 27 bit. Reducering van bijna 90%...

Maar dan heb je dus eigenlijk 4 byte nodig per positie.. Kost wat codeer werk, maar dan heb je ook wat...

Kan je bovenstaande toelichten? Jij wilt dus de positie van 32 schaakstukken opslaan in 27 bits? En op die manier 90% besparen

Je bedoelt het vast anders...

[Verwijderd]

Diadem>> Shannon's getal beschrijft het aantal mogelijke varianten, en dat is natuurlijk gelijk aan het aantal stellingen en niet aan het aantal partijen. (Anders zou hij geen gemiddelde partijlengte in zijn formule hebben zitten.)

jvdmeer>> het enumereren van alle mogelijke schaakstellingen is gewoon onbegonnen werk. Zelfs met alle computerpower die er op dit moment op de aarde aanwezig is zou het miljarden maal miljarden jaren duren, en je hebt er hoe dan ook niks aan, want je kunt al die stellingen niet opslaan: er zijn meer stellingen mogelijk dan er protonen in het universum zijn.

[Mx. Alba]

bankrupcy schreef op 13 November 2002 @ 13:52:
En als je nu niet nagaat welk stuk waar staat, maar bekijkt of op een veld een bepaald stuk (kan) staan?

(Ik roep ook maar wat)

Oké, dan gaan we het in bits verdelen...

1 bit : wit aan zet of zwart aan zet
4 bits : of roccade mogelijk is (wit lang en kort, zwart lang en kort)

En dan voor elk vlakje:

3 bits, namelijk 7 mogelijke stukken:
Koning
Dame
Loper
Paard
Toren
Pion
Pion die en passant geslagen kan worden

Je komt dan dus op 64x3 + 5 = 197.

Maar het kan ook slimmer gedaan worden. Immers, op veel vakjes staat niets. Je kan beter de vlakjes een ID geven. Je hebt dan dus voor elk stuk op het bord 6 bits voor het vak-ID, plus 3 bits voor het stuk, dus in totaal voor het bord 9x(aantal stukken) + 5, wat dus minimaal 23 bits (twee koningen), maximaal 293 bits.

Hmmm, dan denk ik toch dat die eerste methode met in alle gevallen 197 bits beter is?

Oh, en dan hebben we nog niet eens herhalingscounters erin zitten... Immers, een stelling waarin door een bepaalde zet een herhalingsremise volgt is anders dan die zelfde stelling onder normale voorwaarden... Hoe zou je dat op kunnen lossen?

[Diadem]

Verwijderd schreef op 13 November 2002 @ 14:21:

Diadem>> Shannon's getal beschrijft het aantal mogelijke varianten, en dat is natuurlijk gelijk aan het aantal stellingen en niet aan het aantal partijen. (Anders zou hij geen gemiddelde partijlengte in zijn formule hebben zitten.)

In het schaken betekent 'variant' in feite niets anders dan 'zettenreeks'. En dan meestal in de context van een niet gespeelde, maar wel mogelijke, zettenreeks. Als in "Ik had de variant met Pf3 niet gezien. Wat erg jammer is, want deze leidt na ... Dxf3. Tb5! tot stukwinst". Of je hebt het over openingsvarianten: "Welke variant van het Siciliaan speel jij? Ik speel draak".

In ieder geval betekent variant nooit stelling. Als je het hebt over het aantal mogelijke schaakvarianten bedoel je partijen, niet stellingen.

Dat het niet op stellingen slaat is ook logisch, want er is hier al een aantal keer bewezen dat het aantal mogelijke stellingen veel lager ligt dan 10¹²⁰.

[Oscar Mopperkont]

Is het niet mogelijk om dmv brute force een schaakpartij helemaal door te rekenen? En kijken waar je op uitkomt? Bijvoorbeeld dat wit altijd wint, of dat het altijd remise moet worden?
Dat is heel wat rekenwerk, maar daar zou dan kun je toch zo'n distributed manier voor gebruiken? net als RC-72 enzo? Of is zo'n probleem niet in stukjes te hakken?

[jvdmeer]

Mx. Alba schreef op 13 november 2002 @ 14:27:
[...]

1 bit : wit aan zet of zwart aan zet
4 bits : of roccade mogelijk is (wit lang en kort, zwart lang en kort)

[knip]

Je komt dan dus op 64x3 + 5 = 197.

Je vergeet de kleur per stuk, dus er komen nog 64 bits bij, is dus 261 bits.

Mx. Alba schreef op 13 november 2002 @ 14:27:Oh, en dan hebben we nog niet eens herhalingscounters erin zitten... Immers, een stelling waarin door een bepaalde zet een herhalingsremise volgt is anders dan die zelfde stelling onder normale voorwaarden... Hoe zou je dat op kunnen lossen?

Dit hoeft niet in de db opgeslagen worden, maar zou kunnen worden opgelost door de omliggende logica, die tijdens het spel de voorgaande zetten heeft onthouden.


Zelf zat ik nog te denken aan een vorm van compressie erin door elk stuk een extra bit te geven, dat er een stuk aankomt (altijd 1, en dan bij lege vakjes een 0)
Hierdoor kom je op 32*(1 kleur+3 stuk+1 bits)+32*(1 bit leeg vakje)=maximaal 192 bits. Maar dat moet nog beter kunnen. (hoop ik). Ik zat te denken aan het weglaten van de kleurinformatie en alleen een kleurwisseling aan te geven.
Maar het nadeel van compressie is dat records een ongelijke lengte krijgen, en als je snel wilt zoeken in een db zijn records van een gelijke lengte veel sneller te vinden.

Dus als iemand een nog kortere notatie heeft, dan graag.

PS: als stukken hanteer ik de volgende:

code:

1. pion             4. paard      7.dame
2. toren            5. loper      8. [nog te definiëren
3. toren (voor roc) 6. koning        evt. gebruik voor en-passant]

Bij de koning noteer ik roccade niet, want dat is ook te registreren door de beide torens terug te zetten van 3->2 te zetten. Over de oplossing voor het en-passant slaan zit ik nog te denken. Maar misschien gebruik daar de 8^e mogelijkheid nog voor.

[Diadem]

Oscar Mopperkont schreef op 13 november 2002 @ 15:52:
Is het niet mogelijk om dmv brute force een schaakpartij helemaal door te rekenen? En kijken waar je op uitkomt? Bijvoorbeeld dat wit altijd wint, of dat het altijd remise moet worden?
Dat is heel wat rekenwerk, maar daar zou dan kun je toch zo'n distributed manier voor gebruiken? net als RC-72 enzo? Of is zo'n probleem niet in stukjes te hakken?

Nee.

_{Sorry dat ik het zeg, maar lees de draad voor dat je blaat. Er wordt in deze thread al een aantal keer uitgelegd dat je dat niet gaat lukken.}

Als een huidige desktop 10 miljard stellingen per seconde kan doorrekenen, dan ben je met 10 miljard computers, die allemaal 10 miljard keer zo snel zijn dan de huidige, nog steeds nog steeds 200x zo lang bezig dan de huidige leeftijd van het heelal voordat je een antwoord hebt. Gossie...

Notabene: Als ik mij niet vergis kan Deep Fritz 2 miljoen stellingen per seconde evalueren. Nu gaat checken op legaliteit natuurlijk veel sneller dan evalueren, maar dan nog is 10 miljard stellingen per seconde aan de optimistische kant, zelfs voor een supercomputer.

Deep Fritz is de sterkste schaakcomputer op dit moment overigens. Hij heeft net gelijk gespeeld tegen de huidige 'wereldkampioen' Kramnik in een match van 4 partijen.

[TrailBlazer]

nog ff iets kleins waaschijnlijk de zwarte pionnen kunnen nooit op rij 3 staan terwijl alle witte pionnen op rij 4 staan. In deze variant zijn er nog vele mogelijk kortom bijzonder moeilijk realiseerbaar sommetje denk ik

[Verwijderd]

Diadem schreef op 13 november 2002 @ 14:57:
Dat het niet op stellingen slaat is ook logisch, want er is hier al een aantal keer bewezen dat het aantal mogelijke stellingen veel lager ligt dan 10¹²⁰.

Uitgaande van een partij van 40 zetten (80 plies):
• Hardy geeft voor het aantal mogelijke partijen 10^10^50.
• Shannon en Peterson geven voor het totaal aantal mogelijke varianten 10¹²⁰.
• Shannon geeft voor het aantal varianten met 16 pionnen in het spel 10⁴³. (=/= 64! / (32! * (8!)² * (2!)⁶))

edit:
Linkje:

http://mathworld.wolfram.com/Chess.html

[Verwijderd]

Wat er met variant bedoeld wordt is me tot nu toe niet duidelijk (het is zoals Diadem al zei iets anders dan normale schakers eronder verstaan). Wordt er misschien een mogelijk partijverloop, in dit geval tot de 40e zet, mee bedoeld?

[Diadem]

Het is mij nog steeds niet duidelijk wat ze met een variant bedoelen dan. In dat stuk van Wolfram (de makers van mathematica trouwens) hebben ze het simpelweg over: "In a game of 40 moves, the number of possible board positions is at least 10¹²⁰ according to Peterson (1996)."

Dat slaat dus op mogelijke stellingen. Maar dit getal is veel en veel te groot, want mijn bovengrens klopt gewoon. Ik zie er tenminste geen fouten in, en zo ingewikkelde wiskunde is het nu ook weer niet. Ik denk eerlijk gezegd dat Wolfram hier een beetje raar aan het blaten is.

Misschien bedoelen ze met varianten het aantal verschillende zetten wat theoretisch uitgevoerd kan worden. Hmm, nee, dat kan niet, dat zou betekenen dat er in de gemiddelde stelling 10⁷⁰ verschillende zetten gedaan kunnen worden. Nouja, dan weet ik het niet

[Verwijderd]

De kortst mogelijke variant is één halfzet (ply). In de nederlandse (computer)schaakliteratuur wordt meestaal van varianten gesproken, in de engelstalige meestal van "positions"; zoals in "de computer berekent een miljoen varianten per seconde" en niet "stellingen per seconde", het is gewoon op die manier ingeburgerd.

[PrinsEdje80]

jvdmeer schreef op 13 november 2002 @ 14:11:
[...]


Kan je bovenstaande toelichten? Jij wilt dus de positie van 32 schaakstukken opslaan in 27 bits? En op die manier 90% besparen

Je bedoelt het vast anders...

Precies zoals ik bedoel in de quote die jij meldt.
Op zich kun je zoals ik zeg het opslaan in 27 bits, maar dan heb je totaal geen informatie over het wel of niet mogen staan van een stuk op die locatie. Ga maar na dat je dan iig 2^27 (= 1.34 10^8) mogelijkheden hebt om alle LOCATIES van STUKKEN op te slaan incl welk stuk het is.
Je kunt dan idd niet opslaan of de koning aan roccade kan doen oid, maar ik had dan in gedachten dat je dat met functies test.

[Mx. Alba]

PrinsEdje80 schreef op 14 November 2002 @ 06:49:
Precies zoals ik bedoel in de quote die jij meldt.
Op zich kun je zoals ik zeg het opslaan in 27 bits, maar dan heb je totaal geen informatie over het wel of niet mogen staan van een stuk op die locatie. Ga maar na dat je dan iig 2^27 (= 1.34 10^8) mogelijkheden hebt om alle LOCATIES van STUKKEN op te slaan incl welk stuk het is.
Je kunt dan idd niet opslaan of de koning aan roccade kan doen oid, maar ik had dan in gedachten dat je dat met functies test.

Oké, laten we eens gaan rekenen.

Er zijn 6 stukken. Dat moet in 3 bits gecodeerd worden. Er zijn dan dus 2 "stukken" over. Stop daarin de speciale stukken "onbewogen toren" en "pion die en passant geslagen kan worden". En er is een 4e bit nodig om aan te geven of het stuk wit of zwart is.

4 bits dus voor het coderen van het stuk.

Verder zijn er 64 vakjes. Het vak-ID is dus de coderen in 5 bits.

Nu zijn er twee manieren om de stelling te coderen: De 1e is uitgaan van de stukken, de 2e is uitgaan van de vlakken.

Laten we eerst, zoals jij aangeeft, uitgaan van de stukken. Voor elk stuk zijn 9 bits nodig. Er zijn tussen 2 en 32 stukken op het bord. Totaal heb je dus tussen 18 en 288 bits nodig om een positie te coderen. Globaal is dan nog één bit extra nodig voor het coderen van de speler die aan zet is. Je komt dan dus op tussen de 19 en 289 bits.

Laten we dan eens uitgaan van de vlakken, en gewoon voor elk vlakje één voor één aangeven. Dan loop je tegen het "probleem" aan dat je een bit extra nodig hebt om aan te geven of er wel of niet een stuk staat, wat op te lossen is door het stuk "onbewogen toren" te laten vallen, de binaire stukcode 0000 te gebruiken voor "geen stuk", en globaal 4 bits toe te voegen om het roccaderecht bij te houden. Totaal kom je dan dus op 64x4+5 = 261 bits.

Het eerste systeem levert plaatswinst op, maar het tweede systeem levert door de records van gelijke lengte snelheidswinst op.

Hoe jij het in 27 bits kan doen is mij compleet onduidelijk...

[PrinsEdje80]

Mx. Alba schreef op 14 november 2002 @ 11:55:
Oké, laten we eens gaan rekenen.

Ik reken mee...

Er zijn 6 stukken. Dat moet in 3 bits gecodeerd worden. Er zijn dan dus 2 "stukken" over. Stop daarin de speciale stukken "onbewogen toren" en "pion die en passant geslagen kan worden". En er is een 4e bit nodig om aan te geven of het stuk wit of zwart is.

Oke, idd vergeten om zwart/wit aan te geven.
Die onbewogenheid kun je als extra bit nog aanvoeren, dus hier zelfs misschien 5 bits.

4 bits dus voor het coderen van het stuk.

Vandaag ben ik schappelijk dus 5

Verder zijn er 64 vakjes. Het vak-ID is dus de coderen in 5 bits.

Nu zijn er twee manieren om de stelling te coderen: De 1e is uitgaan van de stukken, de 2e is uitgaan van de vlakken.

Laten we eerst, zoals jij aangeeft, uitgaan van de stukken. Voor elk stuk zijn 9 bits nodig. Er zijn tussen 2 en 32 stukken op het bord. Totaal heb je dus tussen 18 en 288 bits nodig om een positie te coderen. Globaal is dan nog één bit extra nodig voor het coderen van de speler die aan zet is. Je komt dan dus op tussen de 19 en 289 bits.

Laten we dan eens uitgaan van de vlakken, en gewoon voor elk vlakje één voor één aangeven. Dan loop je tegen het "probleem" aan dat je een bit extra nodig hebt om aan te geven of er wel of niet een stuk staat, wat op te lossen is door het stuk "onbewogen toren" te laten vallen, de binaire stukcode 0000 te gebruiken voor "geen stuk", en globaal 4 bits toe te voegen om het roccaderecht bij te houden. Totaal kom je dan dus op 64x4+5 = 261 bits.

Het eerste systeem levert plaatswinst op, maar het tweede systeem levert door de records van gelijke lengte snelheidswinst op.

Hoe jij het in 27 bits kan doen is mij compleet onduidelijk...

Ghi, nu ik even meegerekend heb zie ik mijn/jouw fout: kwestie van een stukje miscommunicatie. Ik bedoelde nl PER STUK 27 bits... Mijn fout!

/me PrinsEdje80 gaat zich in een hoekje zitten schamen

[jvdmeer]

Mx. Alba schreef op 14 November 2002 @ 11:55:
Verder zijn er 64 vakjes. Het vak-ID is dus de coderen in 5 bits.

64 heeft 6 bits nodig, evt (1-8)=3 bits + (A-H)=3 bits totaal 6 bits

Mx. Alba schreef op 14 November 2002 @ 11:55:
Laten we eerst, zoals jij aangeeft, uitgaan van de stukken. Voor elk stuk zijn 910 bits nodig. Er zijn tussen 2 en 32 stukken op het bord. Totaal heb je dus tussen 1820 en 288320 bits nodig om een positie te coderen. Globaal is dan nog één bit extra nodig voor het coderen van de speler die aan zet is. Je komt dan dus op tussen de 1921 en 289321 bits.

[Mx. Alba]

jvdmeer schreef op 14 november 2002 @ 13:29:
64 heeft 6 bits nodig, evt (1-8)=3 bits + (A-H)=3 bits totaal 6 bits

Neehoor, je nummert ze gewoon sequentieel.

A1 = 0
B1 = 1
etc...
H1 = 7
A2 = 8
B2 = 9
etc...
H8 = 63

voilà, 5 bits.

Om een stuk een stap vooruit te zetten tel je dus 8 op, om een stap achteruit te doen trek je 8 af. Stap naar rechts 1 erbij, stap naar links 1 eraf.

En dat 5e bit voor de stukcodering is ook niet nodig. Of ze bewogen hebben, is namelijk alleen interessant voor de torens. Stel dat de koning beweegt, dan zet je gewoon dat beide torens hebben bewogen, en voilà, geen roccade meer mogelijk.

Scheelt je op een bord met 32 stukken toch 64 bits zo!

[Dido]

Mx. Alba schreef op 14 November 2002 @ 13:55:
voilà, 5 bits.

Toch 6

offtopic:
hele verhaal maar wat ingekort, anders overleeft iemands botte kop het straks niet...

[ Voor 0% gewijzigd door Dido op 14-11-2002 14:24 . Reden: bescherm RE's botte kop ]

[Mx. Alba]

* Mx. Alba slaat zichzelf voor zijn botte kop

[Diadem]

[edit]
Ik had perongeluk al op verstuur bericht geclicked toen m'n bericht nog half af was. Dat was deze dus

mods, please delete

[Diadem]

Ok, laten we eens terug naar het oorspronkelijke topic gaan, en een zo intelligent mogelijke schatting geven van het aantal stellingen.

Om te beginnen is er de witte koning. Deze kan op 64 velden staan. Vervolgens is er nog een zwarte koning, die ook ergens moet staan. Koningen mogen niet naast elkaar, maar laten we voordat we daar naar gaan kijken eerst nog het rochade recht meenemen.

Als de witte koning op e1 staat, dan kan hij bewogen hebben of niet. We coderen dit simpelweg als een ander veld, en hebben nu 65 velden voor de koning. Maar wacht, als de koning niet bewogen heeft kunnen de torens dat wel gedaan hebben. We kunnen de positie van de torens opvatten als elk 65 mogelijkheden, maar dat wordt heel complex, dus in plaats daarvan gooien we nog een extra mogelijkheid bij de koning in. De witte koning kan dus op 66 velden staan, de zwarte ook.

4 van deze velden zijn hoekvelden, met 60+2 mogelijkheden voor de zwarte koning dan. 24+2 randvelden hebben we, met 58+2 mogelijkheden voor de zwarte koning (in feite iets minder, staat de witte koning op e8 heeft zwart geen rochade recht, maar we houden het simpel). 36 centrumvelden, met 55+2 mogelijkheden voor de zwarte koning.

De 2 koningen kunnen dus op 4*(60+2) + (24+2)*(58+2)*36*(55+2) = 3860 mogelijke manieren op het bord gezet worden, waarbij rochade recht al is verwerkt.

Dan de overige stukken. Het verwerken van schaak is lastig, eigenlijk onmogelijk. Alleen voor pionnen en paarden is dit te doen, maar we zullen dit maar laten, in het kader van de simpelheid.

We beginnen met pionnen. Er zijn 9 verschillende mogelijkheden voor het aantal witte pionnen, en 9 voor het aantal zwarte. Totaal 81 verschillende mogelijke aantallen pionnen, en bij elk van deze kunnen we een aantal manieren geven waarop ze op een schaakbord kunnen staan.

Merk op dat pionnen nooit op de 1e of 8e rij kunnen staan. Omdat koningen daar wel kunnen staan wordt het te complex om rekening te houden met het feit dat we die al op het bord hadden. Dat doen we dus niet. We krijgen nu een hele simpele matrix voor het aantal mogelijkheden.

Met nul witten pionnen zijn er 48 boven 0 = 1 mogelijkheden. Met 1 witte pion zijn er 48 boven 1 = 48 mogelijkheden, etc. Met 1 witte en 1 zwarte pion 48 boven 1 * 47 boven 1. 1w2z: 48 boven 1 * 47 boven 2. 2w1z: 48 boven 2 * 46 boven 1, etc, etc.

We pakken mathematica: 49095495585283107

En geen stelling minder

0, 1, 2 witte paarden, op 62 velden, en 0,1,2 zwarte paarden, op 62 velden. Zelfde procedure, alleen de 48 wordt een 62, en we hebben een 3x3 matrix ipv een 9x9.

mathematica zegt: 3581679

dit zelfde getal geldt voor de torens en lopers. Voor de damers komen we op 3907.

Merk op dat we rochade al verwerkt hebben. Voor en passant en zetkleur hebben een factor 10 nodig.

Totaal aantal schaakstellingen: 10 * 3860 * 49095495585283107 * 3581679³ * 3907

Mathematica: 340198462038278865737898674212386044664084600

3.4 * 10⁴⁴ dus

In deze schatting zit nog een fout, wie ziet hem?

[jvdmeer]

Diadem schreef op 14 november 2002 @ 21:38:In deze schatting zit nog een fout, wie ziet hem?

Ik zie er zo snel twee:

• de koning heeft in jouw redenering 1 plekje te weinig:
64+1 (linkertoren kan rocceren) +1(rechtertoren kan rocceren) +1 (linker- en rechtertoren kunnen rocceren) = 67 ipv 66

• je hebt geen rekening gehouden met promoties.

Jouw antwoord van 340.198.462.038.278.865.737.898.674.212.386.044.664.084.600 is te noteren in (²log 3.4*10⁴⁴=147.9) = 148 bits. Mijn benadering van het aantal bits om een schaakstelling te noteren kwam op 192 bits. De werkelijke maximale waarde moet hier dus tussenin liggen, we komen dus op een getal wat ligt tussen:

3.4*10⁴⁴

en

6.2*10⁵⁷=2¹⁹²

[Diadem]

jvdmeer schreef op 15 November 2002 @ 08:29:

Ik zie er zo snel twee:

• de koning heeft in jouw redenering 1 plekje te weinig:
64+1 (linkertoren kan rocceren) +1(rechtertoren kan rocceren) +1 (linker- en rechtertoren kunnen rocceren) = 67 ipv 66

Dit is geen fout. Ik had het niet meer uitgewerkt in mijn post, maar ik had wel beredeneerd waarom dit klopte. Ik ben het inmiddels alleen weer vergeten, dus ik kan het nu even niet vertellen. Het had iets te maken met torens iig

Overigens is dit een te verwaarlozen verschil.

• je hebt geen rekening gehouden met promoties.

Goed zo. Helaas is het wel rekening houden met promoties niet triviaal. Niet als je het met een beetje nauwkeurigheid wilt doen. Koningen niet meetellend kunnen er maximaal 26 stukken op een schaakbord staan (een pion is geen stuk dus). De 14 stukken waarmee je begint, plus 12 gepromoveerde pionnen (niet alle 16 pionnen kunnen promoveren (tenzij er stukken geslagen worden) omdat ze elkaar niet kunnen passeren zonder te slaan. In dat geval heb je gegarandeerd geen pionnen meer. Wat je ook weet is dat je van elk stuk maximaal 10 hebt (verschillende kleuren = verschillende stukken), behalve van de dame, die heb je maximaal 9. Maar als er pionnen op het bord staan wordt dit minder, en je kunt niet van 2 verschillende stukken ieder 8 hebben ofzo.

Ik ga als ik tijd heb wel een keer proberen dit helemaal uit te werken in Mathematica.

Jouw antwoord van 340.198.462.038.278.865.737.898.674.212.386.044.664.084.600 is te noteren in (²log 3.4*10⁴⁴=147.9) = 148 bits. Mijn benadering van het aantal bits om een schaakstelling te noteren kwam op 192 bits. De werkelijke maximale waarde moet hier dus tussenin liggen, we komen dus op een getal wat ligt tussen:

3.4*10⁴⁴

en

6.2*10⁵⁷=2¹⁹²

Maar mijn antwoord is dus te laag, en ik ben bang dat het rekening houden met promoties best in de papieren kan lopen, qua aantal stellingen. In het weekend hoop ik je meer te kunnen vertellen.

Hoe kwam je ook alweer aan 192? Ik snapte dat verhaal niet helemaal eigenlijk.

[jvdmeer]

Diadem schreef op 15 November 2002 @ 12:32:
Hoe kwam je ook alweer aan 192? Ik snapte dat verhaal niet helemaal eigenlijk.

offtopic:
Stel ik ben op zoek naar het maximaal aantal goede 6-letterwoorden, dan kan ik volgens jouw (zeer goede) benadering gaan rekenen, en aantal combinaties/klinkers/medeklinkers enz. gaan uitrekenen: en dan uitkomen op bv: (geheel willekeurig genomen maar op juiste manier onderbouwd: 330382099

Op mijn manier bereken ik het maximale aantal door te kijken door te kijken in hoeveel bits ik de info moet opslaan, bijv: 6 letters(26 stuks dus 5 bits) is in totaal 6*5 bits is 30 bits.

Mijn benadering levert dus een maximum op van: 2³⁰=1073741824
Jouw benadering levert in ieder geval een minimum op van: 330382099

En de waarheid bevindt zich er tussen in.

Jij hebt dus een voorlopig minimum vastgesteld (waarbij promoties niet zijn meegeteld, en ik heb een voorlopig maximum opgesteld. Dit maximum deed ik hier:

jvdmeer schreef op 13 November 2002 @ 16:12:
Zelf zat ik nog te denken aan een vorm van compressie erin door elk stuk een extra bit te geven, dat er een stuk aankomt (altijd 1, en dan bij lege vakjes een 0)
Hierdoor kom je op 32*(1 kleur+3 stuk+1 bits)+32*(1 bit leeg vakje)=maximaal 192 bits.

[Nadere uitleg]
Daarbij ga ik ervan uit, dat elk vakje 4 bits bevat (1 voor de kleur en 3 voor het stuk). Door nu een extra bitje er voor te plakken die aan geeft of er wel of geen stuk staat, kunnen we 4 bitjes besparen indien er geen stuk staat. Er komen er zo maar 64 bits bij. Omdat er altijd minimaal 32 lege vakjes zijn, besparen we minimaal 32*4 bits=128 bits. Het kost ons maar 64 bits. Dus de besparing is minimaal 128-64=64 bits
Een beginstelling met 32 stukken kost ons 64+32*4=192 bits
Indien er alleen maar 2 koningen staan, hebben we maar 64+2*4 bits nodig om het complete bord te noteren.

Terwijl ik dit zit te typen, bedenk ik me plotseling dat het nog gunstiger kan:
Door de kleuren te scheiden op twee virtuele borden, maken we de besparing nog groter:
Beginstelling=(64+16*(3 bits voor het soort stuk) )*2 (kleuren) =224 bits (shit, helaas is niet zuiniger )

[Mx. Alba]

jvdmeer schreef op 15 november 2002 @ 13:53:
Terwijl ik dit zit te typen, bedenk ik me plotseling dat het nog gunstiger kan:
Door de kleuren te scheiden op twee virtuele borden, maken we de besparing nog groter:
Beginstelling=(64+16*(3 bits voor het soort stuk) )*2 (kleuren) =224 bits (shit, helaas is niet zuiniger )

Klopt inderdaad. Je wint immers slechts 1 bit per stuk, maar je moet een heel tweede bord gaan opslaan...

192 bits is inderdaad een bovengrens, want er zit aardig wat loze informatie in, en je kan er ook "illegale" bordstanden mee coderen.

Stel dat je een moleculaire computer zou gebruiken met een ternair systeem (dus met 0, 1 en 2), zou je dan beter uitkomen?

Je hebt dan slechts twee tertsen nodig voor de stukcodering (6 stukken), een derde terts voor wit / zwart / geen stuk. Dat is dus 32x3 + 32x1 = 128 tertsen.

3^128 = 1,17*10^61
2^192 = 6,28*10^57

Hmmm, kom je toch in een binair systeem op minder uit. En nog wel een faktor ~5000. En dat terwijl in dat ternaire systeem nog niet eens het en passant slaan en roccaderecht waren meegerekend.

Conclusie: binair rules

[bankrupcy]

Er zijn 64 vakjes die we op 64! manieren kunnen rangschikken op een schaakbord.

Op een bord zijn 64 vakjes. De inhoud van elk vakje (bijv een witte pion) maak ik uniek en noem ik een item. Let op : 4832 items zijn dus leeg, en 8 items zijn witte pionnen,enz.... Er zijn dus 64 unieke items, + een nog te rocceren koning 4 te promoveren torens.= 68 items.

komen we dus op 64! * 68 = 65! mogelijkheden om items op een schaakbord te plaatsen.

Nu beperken:
4832 items zijn leeg
8 witte pionnen
8 zwarte pionnen
2 witte torens
2 zwarte torens
2 witte lopers
2 zwarte lopers
2 witte paarden
2 zwarte paarden
Kom ik tot het volgende resultaat:

(64!*68)/(4832!*8!*8!*2!*2!*2!*2!*2!*2!) is een bovengrens voor het aantal mogelijke stellingen. Wat dit is in bits kan ik even niet uitrekenen. (voelt iemand zich geroepen????)


De windows calculator komt op 63 bits, maar of dat klopt.......

[zeeg]

Mx. Alba schreef op 15 november 2002 @ 14:21:
[...]


En nog wel een factor ~2000. Conclusie: binair rules

Scheelt toch weer een factor 2,5

[Mx. Alba]

bankrupcy schreef op 15 November 2002 @ 14:51:
Er zijn 64 vakjes die we op 64! manieren kunnen rangschikken op een schaakbord.

Op een bord zijn 64 vakjes. De inhoud van elk vakje (bijv een witte pion) maak ik uniek en noem ik een item. Let op : 48 items zijn dus leeg, en 8 items zijn witte pionnen,enz.... Er zijn dus 64 unieke items, + een nog te rocceren koning.= 65 items.

komen we dus op 64! * 65 = 65! mogelijkheden om items op een schaakbord te plaatsen.

Nu beperken:
48 items zijn leeg
8 witte pionnen
8 zwarte pionnen
2 witte torens
2 zwarte torens
2 witte lopers
2 zwarte lopers
2 witte paarden
2 zwarte paarden
Kom ik tot het volgende resultaat:

65!/(48!*8!*8!*2!*2!*2!*2!*2!*2!) is een bovengrens voor het aantal mogelijke stellingen. Wat dit is in bits kan ik even niet uitrekenen. (voelt iemand zich geroepen????)


De windows calculator komt op 63 bits, maar of dat klopt.......

En wat dacht je van promotiestukken? Je kan door middel van promotie heel goed twee witte koninginen en drie zwarte paarden op het bord krijgen, bijvoorbeeld... En daar stort jouw systeempje in

[edit]

En hoe geef je in jouw systeem een bord aan met nog slechts twee koningen erop, bijvoorbeeld?

[joepP]

Waarom 3 bits gebruiken voor een stukrepresentatie, als er maar 6 stukken zijn? Je kan die bovengrens dus direct door 8/6 delen.

Je moet ook nog rekening houden met en-passent slaan. Dit past nog wel in de huidige notatie, je kan een witte (zwarte) pion op e1 (e8) zetten als ie en-passent geslagen mag worden.

Verder moet je nog de mogelijke rochade van wit/zwart bijhouden. Hiervoor zijn 9 mogelijkheden, dus je hebt nog een factor 9 extra nodig.

Tot slot moet je nog bijhouden wie aan zet is, nog een factor 2.

Totaal: 2¹⁹² * 6/8 * 9 *2.

[Mx. Alba]

joepP schreef op 15 november 2002 @ 15:27:
Totaal: 2¹⁹² * 6/8 * 9 *2.

6/8 * 9 * 2 = 13,5

Dus in plaats van 2^192 mogelijkheden heb je dan 13,5*2^192 =~ 2^196 mogelijkheden... Vreemd idee van besparing heb jij

[edit]

oh wacht, je had ook een bit toegevoegd voor wit of zwart aan zet, die bij de 2^192 nog niet meegerekend was.

Maar dan nog kom je met jouw bovengrens een factor 6,75 boven die andere.

Ipv bits te besparen, gebruik je juist 3 bits meer. In de informatica kom je wel vaker van die interessante dingen tegen, waar je denkt te besparen, maar uiteindelijk toch meer plek kwijt bent...

[joepP]

Mx. Alba schreef op 15 November 2002 @ 15:35:
[...]

Maar dan nog kom je met jouw bovengrens een factor 6,75 boven die andere.

Ipv bits te besparen, gebruik je juist 3 bits meer. In de informatica kom je wel vaker van die interessante dingen tegen, waar je denkt te besparen, maar uiteindelijk toch meer plek kwijt bent...

Ehm ja,

maar ik sla WEL op of er nog gerocheerd mag worden. Da's nogal van belang

[Mx. Alba]

joepP schreef op 15 November 2002 @ 15:41:
Ehm ja,

maar ik sla WEL op of er nog gerocheerd mag worden. Da's nogal van belang

In het originele systeem ook.

De 8 stukken zijn namelijk: De 6 standaarstukken, plus "onbewogen toren", plus "pion die en passant geslagen kan worden". Met die onbewogen torens kan je roccaderecht vaststellen - je mag immers allen met een onbewogen toren een roccade aangaan.

[joepP]

Mx. Alba schreef op 15 november 2002 @ 15:49:
[...]


In het originele systeem ook.

De 8 stukken zijn namelijk: De 6 standaarstukken, plus "onbewogen toren", plus "pion die en passant geslagen kan worden". Met die onbewogen torens kan je roccaderecht vaststellen - je mag immers allen met een onbewogen toren een roccade aangaan.

Je hebt gelijk.

Ik faal

[bankrupcy]

Hier stond onzin....

[jvdmeer]

Mx. Alba schreef op 15 november 2002 @ 14:21:
Stel dat je een moleculaire computer zou gebruiken met een ternair systeem (dus met 0, 1 en 2), zou je dan beter uitkomen?

Je hebt dan slechts twee tertsen nodig voor de stukcodering (6 stukken), een derde terts voor wit / zwart / geen stuk. Dat is dus 32x3 + 32x1 = 128 tertsen.

3^128 = 1,17*10^61
2^192 = 6,28*10^57

Hmmm, kom je toch in een binair systeem op minder uit. En nog wel een faktor ~5000. En dat terwijl in dat ternaire systeem nog niet eens het en passant slaan en roccaderecht waren meegerekend.

Conclusie: binair rules

Jij gaat de fout in met twee tertsen = 9 mogelijkheden waarvan er slechts 6 gebruikt worden. Dat is de verspilling.
Plus, bij een leegvakje gebruik je maar 1 van de drie optie's, ofwel je gooit 66% van de mogelijkheden weg, i.t.t. binair die maar 50% weggooit. In theorie moet dus de volgende het gunstigst uitkomen: compleet binair:
1e bit 0=geen stuk [END],1=wel stuk indien 0 dan einde
2e bit 0=wit, 1=zwart
3e bit 0=geen pion 1, pion [EIND]
4e bit 0=toren/loper/paard 1=koning/dame
5e bit 0=toren/cq koning[EIND] 1=loper/paard cq dame[EIND]
6e bit 0=toren onbewogen[EIND]/loper[EIND] 1=toren bewogen[EIND]/paard[EIND]

Hierdoor krijg je de volgende keuze lijst:

code:

0                 0 Leeg vakje
-----------
          0  100000 Zwarte onbewogen toren
        0 -
          1  100001 Zwarte bewogen toren
      0 ---
          0  100010 Zwarte loper
        1 -
          1  100011 Zwarte paard
    0 -----
        0     10010 Zwarte Koning
      1 ---
        1     10011 Zwarte dame
  0 -------
    1           101 Witte pion
1 ---------
          0  110000 Zwarte onbewogen toren
        0 -
          1  110001 Zwarte bewogen toren
      0 ---
          0  110010 Zwarte loper
        1 -
          1  110011 Zwarte paard
    0 -----
        0     11010 Zwarte Koning
      1 ---
        1     11011 Zwarte dame
  1 -------
    1           111 Zwarte pion

En de maximale hoeveelheid bits hierin is:

code:

32* 1=32  leeg vakje
  4* 6=24 toren (onbewogen/bewogen maakt niets uit)
  4* 6=24 paard
  4* 6=24loper
  2* 5=10 koning
  2* 5=10 dame
16* 3=16 pion
--    --
64   140

2¹⁴⁰=1,39*10⁴²

Hoewel ik nog niet 100% overtuigd ben dat tijdens het spel de code langer kan worden, is dit weer een aardige omlaag. We gaan tenslotte alweer 15 cijfers minder aan mogelijkheden.

[Mx. Alba]

jvdmeer schreef op 15 November 2002 @ 16:20:
Jij gaat de fout in met twee tertsen = 9 mogelijkheden waarvan er slechts 6 gebruikt worden. Dat is de verspilling.

Inderdaad...

Plus, bij een leegvakje gebruik je maar 1 van de drie optie's, ofwel je gooit 66% van de mogelijkheden weg, i.t.t. binair die maar 50% weggooit. In theorie moet dus de volgende het gunstigst uitkomen: compleet binair:

* Mx. Alba knikt instemmend.

[knip]

code:

32* 1=32  leeg vakje
  4* 6=24 toren (onbewogen/bewogen maakt niets uit)
  4* 6=24 paard
  4* 6=24loper
  2* 5=10 koning
  2* 5=10 dame
16* 3=16 pion
--    --
64   140

2¹⁴⁰=1,39*10⁴²

Hoewel ik nog niet 100% overtuigd ben dat tijdens het spel de code langer kan worden, is dit weer een aardige omlaag. We gaan tenslotte alweer 15 cijfers minder aan mogelijkheden.

140 bits in standaardsituatie, dat is niet slecht.

Maar het moeilijke is: promotiestukken. Wat als er acht torens op het bord staan door promotie?

[bankrupcy]

Stelling: elke promotie is het resultaat van het slaan van een stuk. Hierdoor komen er niet meer stukken op het bord, hooguit veranderd de samenstelling.

Kan iemand dit onderuit halen? De juistheid van deze stelling is van belang voor mijn berekening. (Die overigens grondig herzien moet worden.)

[Mx. Alba]

bankrupcy schreef op 15 November 2002 @ 16:46:
Stelling: elke promotie is het resultaat van het slaan van een stuk. Hierdoor komen er niet meer stukken op het bord, hooguit veranderd de samenstelling.

Kan iemand dit onderuit halen? De juistheid van deze stelling is van belang voor mijn berekening. (Die overigens grondig herzien moet worden.)

Er komen niet meer stukken op het bord, omdat bij een promotie altijd een pion verdwijnt. Maar het stuk dat je kiest is volledig "up to you". Er wordt na promotie regelmatig met aan één kant twee koninginnen gespeeld (er wordt dan meestal een toren op de kop als tweede koningin gebruikt). Zo zouden er ook zes paarden of acht lopers in het spel kunnen zijn door promoties.

In de praktijk worden bij promotie in het grootste deel van de gevallen koninginnen gehaald, maar er worden ook wel eens paarden gehaald - maar in principe zou je ook een loper of een toren kunnen halen, ook als je er al twee van hebt.

[Dido]

bankrupcy schreef op 15 November 2002 @ 16:46:
Stelling: elke promotie is het resultaat van het slaan van een stuk. Hierdoor komen er niet meer stukken op het bord, hooguit veranderd de samenstelling.

Kan iemand dit onderuit halen? De juistheid van deze stelling is van belang voor mijn berekening. (Die overigens grondig herzien moet worden.)

Er komen idd niet meer stukken op het bord, maar je aantal mogelijke stukken neemt toe.
Overigens zie ik niet waarom het perse het resultaat moet zijn van het slaan van een stuk? (Er moet wel minimaal een stuk ooit geslagen zijn voordat er ook maar 1 pion kan promoveren, bedoelde je dat? Er kunnen idd nooit meer dan 32 stukken op het bord staan, maar dat lukt sowieso al niet omdat een promotie en stuk vervangt, geen stuk toevoegt)

[Diadem]

jvdmeer schreef op 15 November 2002 @ 13:53:

[Nadere uitleg]
Daarbij ga ik ervan uit, dat elk vakje 4 bits bevat (1 voor de kleur en 3 voor het stuk). Door nu een extra bitje er voor te plakken die aan geeft of er wel of geen stuk staat, kunnen we 4 bitjes besparen indien er geen stuk staat. Er komen er zo maar 64 bits bij. Omdat er altijd minimaal 32 lege vakjes zijn, besparen we minimaal 32*4 bits=128 bits. Het kost ons maar 64 bits. Dus de besparing is minimaal 128-64=64 bits
Een beginstelling met 32 stukken kost ons 64+32*4=192 bits
Indien er alleen maar 2 koningen staan, hebben we maar 64+2*4 bits nodig om het complete bord te noteren.

Dus je geeft voor elk van de 64 vakjes op of er een stuk staat of niet. Dat kost je dus 64 bits. En vervolgens specifieer je voor elk van de vakjes waar je hebt aangegeven of er een stuk staat wat voor stuk er staat, pion, toren, onbewogen toren, loper, paard, koning, dame, en passant pion. Komt mooi uit, 8 mogelijkheden. En een bit voor kleur, dus 4 bits. Dus je hebt maximaal 4x32 + 64 bits nodig. 192 als bovengrens, dat vind ik behoorlijk netjes gedaan.

Je bent echter nog 1 ding vergeten. Je moet nog coderen wie er aan zet is.

193 bits dus. Blijft netjes.

[Diadem]

Ik verbaas mij er dus over dat je een hele efficiente en elegante codering kunt verzinnen die je toch maar 193 bits kost. Dat geeft een bovengrens op het aantal schaakstellingen van orde grote 10⁵⁸, wat maar heel weinig boven mijn bovengrens is, die een hele hoop rekenwerk heeft gekost.

Echt schaakstellingen worden trouwens heel anders gecodeerd. Het gebruik van aparte bits voor elk van de 4 rochadestelllingen is namelijk heel veel handiger voor rekenen. Codering van schaakstellingen is echter eigenlijk nauwelijks nodig. Waar je in geinteresseerd ben is het coderen van partijen. Moderne databases bevatten al gauw 1 a 2 miljoen partijen.

Gelukkig kun je zetten heel makkelijk opslaan in 12 bit (6 bit voor vertrek veld, 6 voor aankomst). Een gemiddelde partij (40 zetten) kost je dan 480 bit, oftewel 60 byte. Niet heel veel. In praktijk denk ik dat ze zelfs gewoon 2 byte gebruiken per zet. Bovendien wordt er vaak hele lappen tekst aan commentaar bij partijen gevoegd. Dus een cd-tje vul je al snel.

[FCA]

Diadem schreef op 15 November 2002 @ 20:43:
[...]


Dus je geeft voor elk van de 64 vakjes op of er een stuk staat of niet. Dat kost je dus 64 bits. En vervolgens specifieer je voor elk van de vakjes waar je hebt aangegeven of er een stuk staat wat voor stuk er staat, pion, toren, onbewogen toren, loper, paard, koning, dame, en passant pion. Komt mooi uit, 8 mogelijkheden. En een bit voor kleur, dus 4 bits. Dus je hebt maximaal 4x32 + 64 bits nodig. 192 als bovengrens, dat vind ik behoorlijk netjes gedaan.

Je bent echter nog 1 ding vergeten. Je moet nog coderen wie er aan zet is.

193 bits dus. Blijft netjes.

Verder moet je nog de onbewogen koning noteren. Dat is een extra mogelijkheid, en levert een extra bit per positie op, dus in totaal zo'n 32 bits. 5x32+64+1= 225 bits, dus helemaal niet zo netjes. Wat dan korter is om te noteren is een getal van te voren aangeven of er gerokeerd mag worden. Er zijn 3 mogelijkheden per kleur, dus dan ben je er met 4 extra bits vanaf. Kun je onbewogen toren ook nog weglaten.
4*32+64+1+4=197. Zoiets zou je ook voor de en-passant pionnen kunnen doen (voor elke rij aangeven of er een pion staat die en-passant mag worden geslagen = 2*8 bits mogelijkheden) is 4 extra bits, en zou je extra compressie kunnen toepassen op de inhoud van het schaakbord, aangezien je nu maar 6 mogelijkheden voor hebt (pion, paard, loper, toren, koningin en koning). Theoretisch gezien heb je nu nog maar 12^32 mogelijkheden wat ongeveer 115 bits is.
64 (wel of geen stuk)
115 (wat staat er op)
1 (wie is aan zet)
4 (wit/zwart wel of niet links/rechts rokeren)
16 (elke rij zwart/witte pion wel niet en-passant te slaan)
= 186
Misschien is er nog wel een bitje te winnen bij het en-passant slaan, maar niet veel denk ik.

edit:
Moet ik niet stom worden en niet meer kunnen rekenen...
Het getal hierboven klopt niet, de en-passant stukken heb ik te weinig voor genomen, waardoor het op 200 komt. Maar dit moet efficienter kunnen denk ik... Work in progress...

OK, En-passant kan ik niet verbeteren, dus:

2*64 mogelijkheden voor de koningen => 12 bits
62 bits voor de resterende velden
6 mogelijkheden per kleur voor stukken (pion, en-passant pionnen, paard, loper, toren, koningin) => (2*6)^30 mogelijkheden => 107.549 bits
1 bit voor wie aan zet is
4 bits voor wel of niet rokeren

12+62+108+1+4 = 187 bits. Aardige verbetering toch nog dus, door de koningen apart te nemen (er zijn altijd precies 2 koningen)

[Mx. Alba]

Nee, de onbewogen koning hoeft niet genoteerd te worden. Onbewogen torens worden immers al bijgehouden. En omdat je alleen roccades aan kunt gaan met onbewogen torens, kan je als de koning beweegt gewoon beide torens op "bewogen" zetten, en voilà, geen roccaderecht meer.

[Verwijderd]

Toch nog even wat opmerkingen over die "bitnotatie", want er worden toch een aantal dingen vergeten:
1) zetherhaling en 50-zetten regel. Als je stellingen uniek wilt identificeren (enumereren), zul je die gegevens moeten meenemen, wat meer dan 5 bits extra oplevert. (Voorkennis uit voorgaande stellingen mag je niet gebruiken tenzij je die bitlengtes van al die vorige stellingen erbij rekent).

edit:
2) was crap

[Verwijderd]

er zijn nog wel meer dingen die niet kloppen.. Van die 192 bits posities zijn er veel minder mogelijk in het echt, je kan bijvoorbeeld nooit meer dan 32 stukken op het bord hebben

[Mx. Alba]

Verwijderd schreef op 17 november 2002 @ 15:37:
er zijn nog wel meer dingen die niet kloppen.. Van die 192 bits posities zijn er veel minder mogelijk in het echt, je kan bijvoorbeeld nooit meer dan 32 stukken op het bord hebben

Die 192-bits-methode houdt daar ook rekening mee.

En het zijn trouwens 193 bits :

32 x 5 bits (de stukken)
32 x 1 bit (de lege vakjes)
1 bit (zwart of wit aan zet)

Voor de 50-zetten-regel (dat is toch dat er niet 50 zetten gedaan mogen worden zonder dat een stuk geslagen wordt of een pion verzet?) zou je inderdaad nog 5 bits toe moeten voegen, dus kom je op 198 bits. Maar eigenlijk is die informatie niet erg van belang voor de stelling. Wel voor het verloop van het spel, maar niet voor de stelling.

Kijk, in principe maakt het helemaal niets uit of er nou één, twee, drie, twintig of vijfendertig zetten gedaan zijn zonder te slaan. Pas boven de 40 gaat het voor het verdere verloop van het spel invloed hebben.

Daarbij komt dat de stelling eigenlijk het zelfde is, of die 'zetcounter' nou op 0 of op 49 staat.

Ik vind dus dat die zetcounter eigenlijk los staat van de stelling. Als je een schaakprogramma zou maken dat "brute force" werkt en van "ons" 193-bits stellingcodeermechanisme gebruik zou maken, dan zou ik de zetcounter, evenals het bijhouden van repeterende zetten, in het programma zelf bouwen, en dus niet in de "zettenboom".

[Verwijderd]

Mx. Alba schreef op 17 November 2002 @ 16:55:
[...]


Die 192-bits-methode houdt daar ook rekening mee.

En het zijn trouwens 193 bits :

32 x 5 bits (de stukken)
32 x 1 bit (de lege vakjes)
1 bit (zwart of wit aan zet)

dat werkt volgens mij niet zo, want je moet een regelmatig patroon hebben of van te voren weten waar alles staat..
Hiet staat eerst 32 x 5 bits... wat duid je met die 5 bits aan? het soort stuk ? dat kan in 4 bits (inclusief kleur). of de positie? maar dat moet in 6 bits..
Hier kan een computer niets mee.. Die weet niet wanneer hij een 5 bit patroon of een 1 bit patroon moet lezen
het is beter om 32* 6 bits patroon te hebben (32 * locatie van het stuk) en de volgorde van de stukken vantevoren af te spreken zodat de computer weet welk stuk waar staat.. maar dan kom je weer op 2^192 (193 voor wie aan zet is) aan..
en dat is dus veel meer dan wat er mogelijk is..

edit: hmm... het houd er dus WEL rekening mee... stom..

[jvdmeer]

Mx. Alba schreef op 15 november 2002 @ 16:40:
[...]


Inderdaad...


[...]


* jvdmeer knikt instemmend.


[...]


140 bits in standaardsituatie, dat is niet slecht.

Maar het moeilijke is: promotiestukken. Wat als er acht torens op het bord staan door promotie?

Ik hoop ook dat iemand kan bewijzen, dat dat 140 inderdaad een maximum aantal bits is. Misschien dat iemand in een schaakdatabase kan opzoeken wat het maximum aantal stukken is, wat nog op het bord staat, als de eerste promotie plaatsvindt.
(Dan hebben we het helaas over een praktijkmaximum, voor een theoretisch maximum is er nog wat denkwerk nodig...)
Maar als iemand me aan een theoretisch maximum kan helpen, dan graag. Want volgens mij kunnen alle 16 de pionnen promoveren, maar dan kost dat 8 dure stukken. (4 witte om de zwarte pionnen met z'n tweeen op een rij te krijgen en 4 zwarte om de witte pionnen achter elkaar te krijgen).
Wanneer zo alle 16 de pionnen zijn gepromoveerd, dan hebben we volgens mij:
140 bits (basisstelling)
-16*3 bits (16 pionnen minder, zijn gepromoveerd)
-8 *6 bits (8 "dure" stukken zijn geslagen)
+16*6 bits (16 "dure" stukken na promotie erbij)
====
140 bits

Dus volgens mij is 140 bits nog steeds het maximum voor het opslaan van een willekeurige schaakstelling (+evt 1. bit voor wit/zwart aan zet)

[Mx. Alba]

Verwijderd schreef op 18 November 2002 @ 17:13:
dat werkt volgens mij niet zo, want je moet een regelmatig patroon hebben of van te voren weten waar alles staat..
Hiet staat eerst 32 x 5 bits... wat duid je met die 5 bits aan? het soort stuk ? dat kan in 4 bits (inclusief kleur). of de positie? maar dat moet in 6 bits..
Hier kan een computer niets mee.. Die weet niet wanneer hij een 5 bit patroon of een 1 bit patroon moet lezen
het is beter om 32* 6 bits patroon te hebben (32 * locatie van het stuk) en de volgorde van de stukken vantevoren af te spreken zodat de computer weet welk stuk waar staat.. maar dan kom je weer op 2^192 (193 voor wie aan zet is) aan..
en dat is dus veel meer dan wat er mogelijk is..

edit: hmm... het houd er dus WEL rekening mee... stom..

Oké, een voorbeeld van de beginstelling van een bord. Stel eerst:

000 = zwarte pion
001 = zwarte loper
010 = zwarte toren
011 = zwart paard
100 = zwarte koningin
101 = zwarte koning
110 = zwarte pion die en passant geslagen kan worden
111 = zwarte onbewogen toren

Daarvoor één bit voor wit (0) of zwart (1)

Daarvoor één bit voor wel (1) of geen (0) stuk

Helemaal vooraan één bit voor wit (0) of zwart (0) aan zet

De beginstelling is dus:

code:

0                                                (beurt)
10111 10011 10001 10100 10101 10001 10011 10111  (A1-H1)
10000 10000 10000 10000 10000 10000 10000 10000  (A2-H2)
0     0     0     0     0     0     0     0      (A3-H3)
0     0     0     0     0     0     0     0      (A4-H4)
0     0     0     0     0     0     0     0      (A5-H5)
0     0     0     0     0     0     0     0      (A6-H6)
11000 11000 11000 11000 11000 11000 11000 11000  (A7-H7)
11111 11011 11001 11100 11101 11001 11011 11111  (A8-H8)

Of, als je de kolommen neemt:

code:

0                                (beurt)
10111 10000 0 0 0 0 11000 11111  (A1-A8)
10011 10000 0 0 0 0 11000 11011  (B1-B8)
10001 10000 0 0 0 0 11000 11001  (C1-C8)
10100 10000 0 0 0 0 11000 11100  (D1-D8)
10101 10000 0 0 0 0 11000 11101  (E1-E8)
10001 10000 0 0 0 0 11000 11001  (F1-F8)
10011 10000 0 0 0 0 11000 11011  (G1-G8)
10111 10000 0 0 0 0 11000 11111  (H1-H8)

Toch heel elegant?

En na de openingszet:

code:

1                                                (beurt)
10111 10011 10001 10100 10101 10001 10011 10111  (A1-H1)
10000 10000 10000 10000 0     10000 10000 10000  (A2-H2)
0     0     0     0     0     0     0     0      (A3-H3)
0     0     0     0     10110 0     0     0      (A4-H4)
0     0     0     0     0     0     0     0      (A5-H5)
0     0     0     0     0     0     0     0      (A6-H6)
11000 11000 11000 11000 11000 11000 11000 11000  (A7-H7)
11111 11011 11001 11100 11101 11001 11011 11111  (A8-H8)

of natuurlijk

code:

1                                (beurt)
10111 10000 0 0 0 0 11000 11111  (A1-A8)
10011 10000 0 0 0 0 11000 11011  (B1-B8)
10001 10000 0 0 0 0 11000 11001  (C1-C8)
10100 0 0 10110 0 0 11000 11100  (D1-D8)
10101 10000 0 0 0 0 11000 11101  (E1-E8)
10001 10000 0 0 0 0 11000 11001  (F1-F8)
10011 10000 0 0 0 0 11000 11011  (G1-G8)
10111 10000 0 0 0 0 11000 11111  (H1-H8)

[Verwijderd]

Mx. Alba schreef op 17 November 2002 @ 16:55:
Voor de 50-zetten-regel (dat is toch dat er niet 50 zetten gedaan mogen worden zonder dat een stuk geslagen wordt of een pion verzet?) zou je inderdaad nog 5 bits toe moeten voegen, dus kom je op 198 bits. Maar eigenlijk is die informatie niet erg van belang voor de stelling. Wel voor het verloop van het spel, maar niet voor de stelling.

Het is wel relevant voor de stelling, want net zoals bij zetherhaling (kost je nog een bit) verandert de stellingswaarde op het moment dat je 49 "zinloze" zetten cq. 2x de zelfde stelling bereikt hebt: wat een verloren stelling is zonder deze informatie, is een remise-stelling met die informatie. (Overigens is er wel kritiek op de 50-zettenregel omdat men dmv. eindspel-databases ontdekt heeft dat er stellingen zijn met bv. een mat in 71 en meer, terwijl de 50-zettenregel die stellingen tot remise maakt...)

[Mx. Alba]

Verwijderd schreef op 18 November 2002 @ 22:27:
Het is wel relevant voor de stelling, want net zoals bij zetherhaling (kost je nog een bit) verandert de stellingswaarde op het moment dat je 49 "zinloze" zetten cq. 2x de zelfde stelling bereikt hebt: wat een verloren stelling is zonder deze informatie, is een remise-stelling met die informatie. (Overigens is er wel kritiek op de 50-zettenregel omdat men dmv. eindspel-databases ontdekt heeft dat er stellingen zijn met bv. een mat in 71 en meer, terwijl de 50-zettenregel die stellingen tot remise maakt...)

Maar we hadden het eigenlijk over stellingen die in het licht van de herhalingsregel als verschillende stellingen worden gezien. Als je immers een toren nog niet bewogen hebt (en ook je koning niet), en je zet hem een stapje vooruit, waarna zwart een zet doet, je zet hem weer terug, waarna zwart ook zijn zet "terugneemt", dan heb je een ANDERE stelling, omdat er een roccademogelijkheid minder is.

Voor de herhalingsregel maakt het niets uit of er bij een bepaalde stelling 1 of 49 zetten zonder slag of pionzet zijn geweest... En dus zijn het in principe niet verschillende stellingen.

[Diadem]

De 50-zetten en zetherhaling regels zijn niet relevant voor het aantal verschillende schaakstellingen. Men is het er algemeen over eens dat twee stellingen hetzelfde zijn onafhankelijk van deze regels.

Deze regels gaan ook over partijverloop niet over de stelling op zich. Dit in tegenstelling tot rochaderegels, die wel over de stelling zelf gaan. Als je puur stellingen wilt coderen hoef je dus geen rekening te houden met de 50 zetten regel.

Verwijderd schreef op 18 november 2002 @ 22:27:

(Overigens is er wel kritiek op de 50-zettenregel omdat men dmv. eindspel-databases ontdekt heeft dat er stellingen zijn met bv. een mat in 71 en meer, terwijl de 50-zettenregel die stellingen tot remise maakt...)

71 is zelfs niet eens zo veel meer.



De korst mogelijke winstgang in deze stelling is als volgt:

1.Kd6 P6g4 2.Kd5 Pe3+ 3.Kd4 Pc2+ 4.Kc3 Pe3 5.Kd2 Pfg4 6.Kd3 Kg2 7.Ke4 Pc4 8.Kf4 Pge5 9.Ta7 Pd3+ 10.Ke4 Pf2+ 11.Kd4 Pd6 12.Kd5 Pb5 13.Ta5 Pd1 14.Kc5 Pbc3 15.Kc4 Pe2 16.Kd3 Pg3 17.Ta1 Pf2+ 18.Ke3 Pf1+ 19.Kd4 Pg3 20.Ta3 Pf5+ 21.Kd5 Pd1 22.Pc6 Pde3+ 23.Ke6 Pg7+ 24.Kf7 Pgf5 25.Kf6 Kf2 26.Ta2+ Kf3 27.Ke5 Kg4 28.Ke4 Pc4 29.Ta4 Kg5 30.Pd8 Pg3+ 31.Kd4 Pb6 32.Ta7 Pf5+ 33.Ke4 Pc4 34.Pe6+ Kf6 35.Ta6 Pg3+ 36.Kd4 Pd6 37.Kd5 Pde4 38.Ta3 Pf5 39.Pf8 Pf2 40.Tf3 Pg4 41.Ke4 Ph6 42.Tf2 Ke7 43.Pg6+ Ke6 44.Pf4+ Kf6 45.Pd3 Ke6 46.Pc5+ Kd6 47.Pb7+ Kc7 48.Pa5 Pd6+ 49.Kd5 Pg4 50.Td2 Pe3+ 51.Kd4 Pg4 52.Tg2 Kb6 53.Pb3 Pb5+ 54.Ke4 Pd6+ 55.Kf4 Ph6 56.Tc2 Pb5 57.Tc1 Pf7 58.Pd2 Pc7 59.Pc4+ Kb5 60.Ke4 Pg5+ 61.Kf5 Pge6 62.Pd6+ Kb6 63.Pc8+ Kb5 64.Ke5 Pc5 65.Tg1 Pb3 66.Tg7 Pa6 67.Tb7+ Kc4 68.Pd6+ Kc3 69.Tg7 Pa5 70.Tg4 Pc6+ 71.Ke4 Pa5 72.Ke3 Pb4 73.Pb5+ Kb3 74.Pd4+ Ka4 75.Th4 Pc4+ 76.Ke4 Pd6+ 77.Ke5 Pc4+ 78.Ke6 Pa3 79.Th8 Pbc2 80.Pf5 Kb5 81.Kd5 Pb4+ 82.Ke4 Pc4 83.Pd4+ Kb6 84.Th6+ Kc5 85.Th5+ Kd6 86.Pf5+ Kd7 87.Th7+ Kc6 88.Kd4 Kb5 89.Th5 Pa5 90.Pd6+ Kb6 91.Tg5 Kc7 92.Pf5 Kd7 93.Tg2 Ke6 94.Pg7+ Kd7 95.Th2 Pb7 96.Td2 Ke7 97.Tb2 Pd8 98.Kc4 Pbc6 99.Kd5 Kd7 100.Td2 Ke7 101.Ph5 Pb4+ 102.Kc5 Pa6+ 103.Kb6 Pb8 104.Pf4 Pf7 105.Kc7 Pa6+ 106.Kc6 Pb8+ 107.Kd5 Pd7 108.Te2+ Kf6 109.Tf2 Pb6+ 110.Kc6 Pc4 111.Pd5+ Kg5 112.Pe7 Ph6 113.Kd5 Pe5 114.Tf1 Pd7 115.Tg1+ Kf4 116.Pg6+ Kf5 117.Kd6 Pf6 118.Ph4+ Ke4 119.Te1+ Kd3 120.Ke5 Pd7+ 121.Ke6 Pc5+ 122.Kd5 Pd7 123.Td1+ Ke3 124.Tf1 Pb6+ 125.Ke6 Pc4 126.Pg2+ Ke2 127.Tf4 Pb2 128.Tb4 Pd1 129.Ke5 Pf7+ 130.Kf6 Pd8 131.Pf4+ Kf3 132.Pd5 Pc6 133.Tc4 Pa5 134.Ta4 Pc6 135.Ke6 Pb2 136.Th4 Pd3 137.Kf5 Ke2 138.Tc4 Pde5 139.Tc3 Kd2 140.Th3 Pc4 141.Kf4 Pd4 142.Ke4 Pe2 143.Th2 Kd1 144.Tf2 Ke1 145.Tg2 Kd1 146.Kd3 Pb2+ 147.Ke3 Pc4+ 148.Kf2 Pe5 149.Tg5 Pc4 150.Tg4 Pa3 151.Kf3 Pc2 152.Ke4 Kd2 153.Tg2 Pd4 154.Pf4 Kd1 155.Ph5 Pc2 156.Tf2 Pa3 157.Kd3 Pc1+ 158.Ke3 Pc2+ 159.Ke4 Pe2 160.Tf3 Pb4 161.Th3 Pc1 162.Th2 Pe2 163.Pg7 Pc3+ 164.Ke5 Pb1 165.Pe6 Pd2 166.Th3 Pc6+ 167.Kd6 Pb4 168.Kc5 Pa2 169.Kd4 Pc1 170.Th7 Ke2 171.Th2+ Kf3 172.Th5 Ke2 173.Te5+ Kd1 174.Tf5 Pe2+ 175.Kd3 Pc1+ 176.Ke3 Pc4+ 177.Kd4 Pb2 178.Tg5 Pbd3 179.Tg7 Ke2 180.Pg5 Pe1 181.Tf7 Kd1 182.Pe4 Pe2+ 183.Kc4 Pg2 184.Td7+ Ke1 185.Ta7 Kd1 186.Ta1+ Kc2 187.Ta2+ Kd1 188.Td2+ Ke1 189.Tb2 Kd1 190.Pg5 Pe1 191.Tb1+ Pc1 192.Kc3 Pd3 193.Pe4 Ke2 194.Kd4 Kd1 195.Tb8 Pe1 196.Td8 Ke2 197.Pc5 Kf3 198.Tf8+ Ke2 199.Tf7 Pa2 200.Te7+ Kd1 201.Pb3 Pb4 202.Te4 Pg2 203.Pa5 Pc2+ 204.Kd3 Pge3 205.Pb3 Pf1 206.Te8 Pe1+ 207.Kc3 Pf3 208.Pc5 Pg3 209.Kd3 Pe1+ 210.Ke3 Pc2+ 211.Kf2 Pf5 212.Td8+ Kc1 213.Ke2 Pg3+ 214.Kf3 Pf5 215.Td7 Pfd4+ 216.Ke4 Kb2 217.Kd3 Pc6 218.Td6 Pe5+ 219.Ke4 Pc4 220.Td3 Pa5 221.Pa4+ Ka2 222.Tc3 Pa1 223.Th3 P1b3 224.Kd3 Ka3 225.Th4 Pc6 226.Kc3 Pcd4 227.Pb6 Pe2+ 228.Kc2 Ped4+ 229.Kd3 Kb4 230.Pc8 Kb5 231.Kc3 Kc6 232.Th5 Kc7 233.Pe7 Kd6 234.Pd5 Kc5 235.Pb4+ Kd6 236.Td5+ Kc7 237.Kc4 Kc8 238.Pd3 Kb7 239.Td7+ Kc6 240.Pe5+ Kb6 241.Tf7 Pe6 242.Kxb3 Kc5 243.Td7 Pd4+ 244.Kc3 Pe2+ 245.Kd3 Pf4+ 246.Ke4 Pe6 247.Td5+ Kb4 248.Td6 Pc5+ 249.Kd5 Pa4 250.Kd4 Ka5 251.Td7 Ka6 252.Pc4 Kb5 253.Ta7 Kc6 254.Txa4 Kd7 255.Ta6 Ke8 256.Ta7 Kd8 257.Tb7 Kc8 258.Tg7 Kd8 259.Pb6 Ke8 260.Ke5 Kf8 261.Kf6 Ke8 262.Tg8 mat

Er worden hier 242 zetten gedaan zonder dat een stuk wordt geslagen, of een pion gezet.

[Verwijderd]

Diadem schreef op 19 November 2002 @ 12:45:
De 50-zetten en zetherhaling regels zijn niet relevant voor het aantal verschillende schaakstellingen. Men is het er algemeen over eens dat twee stellingen hetzelfde zijn onafhankelijk van deze regels.

Deze regels gaan ook over partijverloop niet over de stelling op zich. Dit in tegenstelling tot rochaderegels, die wel over de stelling zelf gaan. Als je puur stellingen wilt coderen hoef je dus geen rekening te houden met de 50 zetten regel.

/me zucht

Denk er aub. toch even over na. We weten dat een partij remise is bij 50 loze zetten. Dat betekent dat we in een stelling waarin 49 loze zetten gedaan zijn, eenvoudig remise kunnen bereiken door een 50ste loze zet te doen. Dit maakt die stelling dus tot een remise-stelling. Zonder die gegevens zou het zeer wel kunnen dat je die partij wint (na nog 193 zetten bv. ) of verliest. De 50-zettenregel verandert dus niet alleen het spelverloop, hij verandert ook de waardering van individuele stellingen (zonder 50-zettenregel is het een winst- of verlies-stelling, met 50-zettenregel is het een remise-stelling). Net als met de regel voor zetherhaling.

edit:
Als we dus twee stellingen hebben waarbij alle stukken op de zelfde positie staan en de zelfde speler aan zet is, dan zijn die stellingen toch verschillend als het aantal loze zetten dat gespeeld is om die stelling te bereiken verschilt. Daardoor is dit aantal loze zetten dus nodig om tot een unieke stellingsdescriptor te komen.

[Mx. Alba]

Verwijderd schreef op 19 november 2002 @ 15:07:
/me zucht

Denk er aub. toch even over na. We weten dat een partij remise is bij 50 loze zetten. Dat betekent dat we in een stelling waarin 49 loze zetten gedaan zijn, eenvoudig remise kunnen bereiken door een 50ste loze zet te doen. Dit maakt die stelling dus tot een remise-stelling. Zonder die gegevens zou het zeer wel kunnen dat je die partij wint (na nog 193 zetten bv. ) of verliest. De 50-zettenregel verandert dus niet alleen het spelverloop, hij verandert ook de waardering van individuele stellingen (zonder 50-zettenregel is het een winst- of verlies-stelling, met 50-zettenregel is het een remise-stelling). Net als met de regel voor zetherhaling.

edit:
Als we dus twee stellingen hebben waarbij alle stukken op de zelfde positie staan en de zelfde speler aan zet is, dan zijn die stellingen toch verschillend als het aantal loze zetten dat gespeeld is om die stelling te bereiken verschilt. Daardoor is dit aantal loze zetten dus nodig om tot een unieke stellingsdescriptor te komen.

* Mx. Alba zucht

Denk er aub. toch even over na. Het gaat daar helemaal niet over in het gestelde vraagstuk. Waar het over gaat, is om een bovengrens te berekenen voor het aantal mogelijke verschillende schaakstellingen, met "verschillende stellingen" gedefiniëerd zoals dat voor de herhalingsregel gedefiniëerd wordt. Daarnaast is een vraag opgekomen hoe je een schaakstelling in zo min mogelijk bits kunt weergeven.

Er werd ook expliciet bij gezegd dat we niet geïnteresseerd zijn in het spelverloop, maar slechts in de stellingen. De 50-zetten-regel (en ook de herhalingsregel) hebben te maken met het spelverloop, en daar zijn we dus expliciet niet in geïnteresseerd.

_{Onder het motto, topics lezen en flamen moet je ook maar kunnen...}

^{(No hard feelings...)}

[Verwijderd]

Mx. Alba schreef op 18 November 2002 @ 19:30:
[...]
Elegant voorbeeld

Thanks, het is me nu wel duidelijk. Dan lijkt 193 me idd wel een aardige bovengrens

[Verwijderd]

Mx. Alba schreef op 19 november 2002 @ 15:22:
Denk er aub. toch even over na. Het gaat daar helemaal niet over in het gestelde vraagstuk. Waar het over gaat, is om een bovengrens te berekenen voor het aantal mogelijke verschillende schaakstellingen, met "verschillende stellingen" gedefiniëerd zoals dat voor de herhalingsregel gedefiniëerd wordt. Daarnaast is een vraag opgekomen hoe je een schaakstelling in zo min mogelijk bits kunt weergeven.

Is hen nu nog niet duidelijk dat het spelverloop invloed heeft op het aantal mogelijke stellingen? Is het nu zo moeilijk te begrijpen dat als er een regel is die de spelduur verkort, die regel óók het aantal mogelijke stellingen reduceert? En als dat zo is, dat die regel dan ook opgenomen moet worden in een unieke stellingsdescriptor?

[jvdmeer]

Verwijderd schreef op 20 November 2002 @ 12:20:
[...]

Is hen nu nog niet duidelijk dat het spelverloop invloed heeft op het aantal mogelijke stellingen? Is het nu zo moeilijk te begrijpen dat als er een regel is die de spelduur verkort, die regel óók het aantal mogelijke stellingen reduceert? En als dat zo is, dat die regel dan ook opgenomen moet worden in een unieke stellingsdescriptor?

Zoals ik al in een post een tijd geleden heb gemeld, wil ik zowel de herhalingsregel als de 50-zetten regel in de programmalogica opnemen, en NIET in de stelling.
Als, in jouw voorbeeld van 273 zetten, zwart een niet-perfecte zet doet, dan wordt de 273 zetten ingekort tot (veel) minder zetten. Waardoor dezelfde eindstelling zich veel eerder voordoet. Moet ik dan een stelling 30x in een database opnemen, omdat hij op verschillende manieren bereikt kan worden, met steeds een ander aantal "passieve" (geen pion-zet/geen slagzet) zetten?
Het lijkt mij handiger om tijdens het spelverloop dit aantal "passieve" zetten bij te houden, en dan evt. het spel wel/niet af te kappen met remise. Zo is in het voorbeeld ook bewust de 50-zettenregel genegeerd, want die gaat tot 273 zetten.
Als een witte toren een twee rondjes gaat lopen op een bijna leeg bord, a1, a8, h8, h1 en de zwarte loopt er steeds achteraan, dan krijg ik dus elke stelling 2x erin omdat er in het 2e geval 4 zetten meer zijn verstreken.

[jvdmeer]

Verwijderd schreef op 20 november 2002 @ 12:17:
[...]

Thanks, het is me nu wel duidelijk. Dan lijkt 193 me idd wel een aardige bovengrens

Ik zat inmiddels te wachten op iemand die mijn 140 bits omver kon argumenteren. Want ik wil met de keuzelijst die ik eerder noemde:

code:

     0 Leeg vakje
100000 Zwarte onbewogen toren
100001 Zwarte bewogen toren
100010 Zwarte loper
100011 Zwarte paard
 10010 Zwarte Koning
 10011 Zwarte dame
   101 Witte pion
110000 Zwarte onbewogen toren
110001 Zwarte bewogen toren
110010 Zwarte loper
110011 Zwarte paard
 11010 Zwarte Koning
 11011 Zwarte dame
   111 Zwarte pion

Dan kom ik op de volgenste stelling (hopelijk even elegant):

code:

0                             beurt
100000 101 0 0 0 0 111 110000 a1..a8
100011 101 0 0 0 0 111 110011 b1..b8
100010 101 0 0 0 0 111 110010 c1..c8
 10011 101 0 0 0 0 111  11011 d1..d8
 10010 101 0 0 0 0 111  11010 e1..e8
100010 101 0 0 0 0 111 110010 f1..f8
100011 101 0 0 0 0 111 110011 g1..g8
100000 101 0 0 0 0 111 110000 h1..h8

Is er iemand die deze 141 bits omver kan lullen, dat het perse meer moet zijn?

[Mx. Alba]

Verwijderd schreef op 20 November 2002 @ 12:20:
Is hen nu nog niet duidelijk dat het spelverloop invloed heeft op het aantal mogelijke stellingen? Is het nu zo moeilijk te begrijpen dat als er een regel is die de spelduur verkort, die regel óók het aantal mogelijke stellingen reduceert? En als dat zo is, dat die regel dan ook opgenomen moet worden in een unieke stellingsdescriptor?

Ik zie wel in hoe de 50-zetten-regel invloed heeft op de spelduur, maar niet hoe die regel invloed heeft op het aantal mogelijke stellingen.

Neem een willekeurige stelling die te bereiken is na 100 zetten zonder slag of pionzet. Die stelling kan ook bereikt worden na minder dan 50 zetten zonder slag of pionzet, of zelfs in 0 zetten zonder slag of pionzet (als de laatste zet dus een slag of een pionzet was).

De 50-zetten-regel heeft GEEN invloed op het TOTAAL aantal MOGELIJKE schaakstellingen. En daarom is de 50-zetten-regel voor ons dus NIET interessant.

[Verwijderd]

Mx. Alba schreef op 20 november 2002 @ 14:02:
Ik zie wel in hoe de 50-zetten-regel invloed heeft op de spelduur, maar niet hoe die regel invloed heeft op het aantal mogelijke stellingen.

Dan zit er een flink gat in je speltheoretische logica. Speltheoretisch moet elke spelregel zijn weerslag vinden in een positie-notatie (ookal laat je een deel door de "progamma-logica" telkens opnieuw berekenen en slaat dat deel niet expliciet bij de stelling op). Laat je regels weg dan zijn er twee mogelijkheden of een combinatie daarvan: of je identificeert je geen unieke spelposities (stellingen) en/of je beschrijft spelposities die illegaal zijn volgens de regels.

Neem een willekeurige stelling die te bereiken is na 100 zetten zonder slag of pionzet. Die stelling kan ook bereikt worden na minder dan 50 zetten zonder slag of pionzet, of zelfs in 0 zetten zonder slag of pionzet (als de laatste zet dus een slag of een pionzet was).

En gezien het feit dat het resultaat van de partij anders is als die stelling bereikt wordt bij x < 50 zetten dan bij x = 50 zetten, geeft dat dus aan dat die stellingen niet identiek zijn: de afstand tot remise door de 50-zettenregel wordt steeds kleiner. Houd je geen rekening met die kleiner wordende remise-afstand, dan ga je onherroepelijk illegale stellingen beschrijven (en dus meerekenen): stellingen die bereikt worden met x > 50.

[Diadem]

Verwijderd schreef op 20 november 2002 @ 12:20:
[...]

Is hen nu nog niet duidelijk dat het spelverloop invloed heeft op het aantal mogelijke stellingen? Is het nu zo moeilijk te begrijpen dat als er een regel is die de spelduur verkort, die regel óók het aantal mogelijke stellingen reduceert? En als dat zo is, dat die regel dan ook opgenomen moet worden in een unieke stellingsdescriptor?

Zoals jij redeneert zou je ook nooit remise hebben door zetherhaling, omdat elke keer dat een stelling terugkomt er een ander aantal normale (niet pion of slagzetten) gedaan is.

Zo werkt het dus niet.

De herhalings- en 50-zetten regel zijn niet relevant voor het aantal mogelijke stellingen. En dus ook niet voor hoeveel bits je nodig hebt om een stelling te coderen. Deze regels gaan over partijverloop en niet over stellingen.

Je kunt dan net zo goed de sterkte van de spelers ook gaan invoeren. Een goede speler zal een KLPK eindspel winnen, een slechte speler niet. Is het dan een andere stelling afhankelijk van wie er speelt?

[itsme]

Geen idee of jullie er iets aan hebben, maar wat als je nu een andersom rekent?

Dus hoeveel mogelijke schaakmatten zijn er mogelijk?

[Mx. Alba]

Mietje, ik ben het volledig met je eens, maar dat ligt buiten de discussie die hier gevoerd wordt.

Immers, de twee vraagstellingen die hier naar boven komen zijn:

1) Wat is de bovengrens van het aantal mogelijke verschillende schaakstellingen, met "verschillende schaakstellingen" gedefinieerd zoals in de herhalingsregel.

2) In hoeveel bits kan je alle verschillende schaakstellingen coderen, met ook voor "verschillende schaakstellingen" dezelfde definitie als in de herhalingsregel.

De 50-zetten-regel is irrelevant voor de herhalingsregel. Voor de herhalingsregel zijn twee stellingen met de zelfde stukkenverdeling, de zelfde persoon die aan de beurt is, en dezelfde roccaderechten, de zelfde stelling, ongeacht of er nou 0, 12 of 49 zetten gedaan zijn zonder stukslag of pionzet. Voor onze vraagstukken geldt dus het zelfde.

Ook is in beide vraagstukken de herhalingsregel ook irrelevant. Weliswaar wordt de definitie van "verschillende stelling" uit de herhalingsregel gehaald, maar in de herhalingsregel wordt niet opnieuw gerefereerd naar de herhalingsregel. Net zoals de 50-zetten-regel, is dus ook de herhalingsregel irrelevant voor onze vraagstukken.

[Mx. Alba]

its_me schreef op 20 november 2002 @ 16:16:
Dus hoeveel mogelijke schaakmatten zijn er mogelijk?

Allemaal.

[Verwijderd]

Mx. Alba schreef op 20 november 2002 @ 16:17:
Ook is in beide vraagstukken de herhalingsregel ook irrelevant. Weliswaar wordt de definitie van "verschillende stelling" uit de herhalingsregel gehaald, maar in de herhalingsregel wordt niet opnieuw gerefereerd naar de herhalingsregel. Net zoals de 50-zetten-regel, is dus ook de herhalingsregel irrelevant voor onze vraagstukken.

En wat ik probeer aan te geven is dat daarmee het hele vraagstuk irrelevant wordt: je hebt het immers niet meer over schaken volgens de regels, maar over "een soort schaken zonder zetherhaling en 50-zettenregel". Je kunt net zo goed argumenteren dat rochades of promotiezetten ook niet belangrijk zijn voor je vraagstuk. Dat kan wel zijn, maar dan gaat je vraagstuk niet (meer) over schaken

[Mx. Alba]

Verwijderd schreef op 20 November 2002 @ 16:30:
En wat ik probeer aan te geven is dat daarmee het hele vraagstuk irrelevant wordt: je hebt het immers niet meer over schaken volgens de regels, maar over "een soort schaken zonder zetherhaling en 50-zettenregel". Je kunt net zo goed argumenteren dat rochades of promotiezetten ook niet belangrijk zijn voor je vraagstuk. Dat kan wel zijn, maar dan gaat je vraagstuk niet (meer) over schaken

Oké, we hebben allebei gelijk, goed?

Sjeesj, de een is nog hardhoofdiger dan de ander... (Hier heb ik het over mietje en mezelf )

[joepP]

Verwijderd schreef op 20 November 2002 @ 16:30:
[...]

En wat ik probeer aan te geven is dat daarmee het hele vraagstuk irrelevant wordt: je hebt het immers niet meer over schaken volgens de regels, maar over "een soort schaken zonder zetherhaling en 50-zettenregel". Je kunt net zo goed argumenteren dat rochades of promotiezetten ook niet belangrijk zijn voor je vraagstuk. Dat kan wel zijn, maar dan gaat je vraagstuk niet (meer) over schaken

Het is na 3x dezelfde stelling niet automatisch remise. Dat is het pas als een van de spelers het opeist. Hetzelfde geldt voor de 50-zettenregel.

[Diadem]

Verwijderd schreef op 20 november 2002 @ 16:30:
[...]

En wat ik probeer aan te geven is dat daarmee het hele vraagstuk irrelevant wordt: je hebt het immers niet meer over schaken volgens de regels, maar over "een soort schaken zonder zetherhaling en 50-zettenregel". Je kunt net zo goed argumenteren dat rochades of promotiezetten ook niet belangrijk zijn voor je vraagstuk. Dat kan wel zijn, maar dan gaat je vraagstuk niet (meer) over schaken

Je bent echt gruwelijk eigenwijs he?

God zeg, ik heb meer dan de helft van mijn leven dagelijks geschaakt. Er zijn tijden geweest dat ik de spelregels, inclusief aanhangsels betreffende zwitserse indeling, bijna uit mijn hoofd kende. Ik heb in mijn leven duizenden, zo niet tienduizenden, verschillende schakers ontmoet, in niveau verschillend van beginners tot absolute wereldtop.

Ik ben er nog nooit, maar dan ook nooit, 1 tegengekomen die een schaakstelling definieert zoals jij het doet.

Eigenwijs is een goede eigenschap. Maar jij bent het op het absurde af, en dan verliest het zijn waarde.

Je hebt gewoon ongelijk. Punt.

[Verwijderd]

Diadem schreef op 20 November 2002 @ 17:12:
Je bent echt gruwelijk eigenwijs he?

Yep.

God zeg, ik heb meer dan de helft van mijn leven dagelijks geschaakt. Er zijn tijden geweest dat ik de spelregels, inclusief aanhangsels betreffende zwitserse indeling, bijna uit mijn hoofd kende. Ik heb in mijn leven duizenden, zo niet tienduizenden, verschillende schakers ontmoet, in niveau verschillend van beginners tot absolute wereldtop.

Hoewel ik de laatste jaren minder regelmatig schaak kan ik beweren dat ik 20 jaar dagelijks geschaakt heb. Daarnaast heb ik voor mijn afstudeeropdracht nog een schaakprogramma geschreven dat evalueert via een neurologisch netwerk. (Dick-length contests rulen )

Ik ben er nog nooit, maar dan ook nooit, 1 tegengekomen die een schaakstelling definieert zoals jij het doet.

Het punt is dat jullie een onzuivere definitie hanteren: jullie spreken over unieke stellingen terwijl jullie (niet-unieke) stukposities bedoelen. Als je het over posities hebt, hebben jullie gelijk, maar dan hoef je ook niet te coderen voor en passant- en rochade-zetten, dat heeft ook niets met de stukposities te maken. Het is dus of het een en je codeert alle regels, of het ander en je codeert geen regels, maar niet half/half.

edit:
Uit een stelling kun je dus de volledige context van een partij schaak halen, uit alleen de stukposities niet.

[Mx. Alba]

Verwijderd schreef op 20 november 2002 @ 17:58:
Het punt is dat jullie een onzuivere definitie hanteren: jullie spreken over unieke stellingen terwijl jullie (niet-unieke) stukposities bedoelen. Als je het over posities hebt, hebben jullie gelijk, maar dan hoef je ook niet te coderen voor en passant- en rochade-zetten, dat heeft ook niets met de stukposities te maken. Het is dus of het een en je codeert alle regels, of het ander en je codeert geen regels, maar niet half/half.

Maar die definitie die we gebruiken komt rechtstreeks uit de herhalingsregel. Dus volgens jou is de herhalingsregel ook onzuiver?

edit:
Uit een stelling kun je dus de volledige context van een partij schaak halen, uit alleen de stukposities niet.

Dat is nu duidelijk, bedankt voor de uitleg.

[Diadem]

Verwijderd schreef op 20 November 2002 @ 17:58:

Het punt is dat jullie een onzuivere definitie hanteren: jullie spreken over unieke stellingen terwijl jullie (niet-unieke) stukposities bedoelen. Als je het over posities hebt, hebben jullie gelijk, maar dan hoef je ook niet te coderen voor en passant- en rochade-zetten, dat heeft ook niets met de stukposities te maken. Het is dus of het een en je codeert alle regels, of het ander en je codeert geen regels, maar niet half/half.

edit:
Uit een stelling kun je dus de volledige context van een partij schaak halen, uit alleen de stukposities niet.

Nee. Dat is dus niet waar. Rochaderecht heeft wel met stukposities te maken. Dat is een eigenschap van de stelling, en wordt ook zo erkend in de fide regels.

Zoals jij redeneert zou je voor het opslaan van een enkele stelling ook moeten opslaan hoe vaak elke andere mogelijke stelling al op het bord is geweest. Immers een winstvariant kan onmogelijk worden doordat je een stelling die al 2x eerder is langsgeweest voor de derde keer langskomt. En je zou ook moeten noteren of een van de spelers gedurende de huidige zet, of de zet daarvoor, een remiseaanbod heeft gedaan, dat is dan immers ook relevant.

Dat kan wel, en dat wordt ook gedaan. Maar dan noemen we het geen schaakstelling, dan noemen we het een schaakpartij.

Een stukpositie is heel wat anders. Een stukpositie is de letterlijke stand van de stukken. Hierbij houdt je dus geen rekening met en-passant en rochade. Dit is dus geen stelling.

Het is niet half/half. De rochade regel en de 50 zetten regel zijn 2 essensieel verschillende beesten.

[Verwijderd]

Diadem schreef op 20 november 2002 @ 21:08:
Een stukpositie is heel wat anders. Een stukpositie is de letterlijke stand van de stukken. Hierbij houdt je dus geen rekening met en-passant en rochade. Dit is dus geen stelling.

a) Ben je het met me eens dat die 16-pionnen formule van Shannon die ik eerder quote stukposities berekent en geen stellingen?
b) Ben je het ook met me eens dat er meer stellingen zijn dan er stukposities zijn?

Als je op alletwee ja antwoordt, zou je eigenlijk mijn argumentatie moeten ondersteunen en niet bestrijden. Hoe je het beest ook noemt, het heeft geen zin om een waarde voor het aantal mogelijkheden in het schaak te berekenen, als die mogelijkheden die je berekent niet uniek zijn; je komt dan gewoon op te lage waardes uit.

(Ik begin overigens steeds beter te begrijpen waarom Jaap vd. Herik zo aandringt op het gebruik van de term variant ipv. stelling in dit soort situaties... )