Aantal mogelijke schaakstellingen

[jvdmeer]

Naar aanleiding van de subdiscussie die is ontstaan in Hoogste getal, lijkt mij het zinnig om deze discussie apart voort te zetten. ik heb voor het aantal mogelijke stellingen nu de volgende getallen zien voorbij komen:

• Zoijar 10⁶⁰⁰
• Rey_Nema 3,56¹¹⁵⁵⁹~4,4*10⁶³⁷⁸
• Marchello_E 10^53.683
• Diadem 1.3 * 10⁵⁶
• Lord Daemon 8.2 * 10⁷⁷

Omdat ik ooit (jaren geleden) eens met het idee rondliep om het hele schaakspel in kaart te brengen. Hiervoor ben ik vorig jaar eens gaan rekenen...

ik kwam op de volgende hoeveelheid stellingen:
de 16 pionnen kunnen op 48 vakjes staan (1e rij kunnen ze niet staan en laatste rij promoveren en kunnen ze dus ook niet staan)
de 2 koningen kunnen op 64 vakjes staan
de 2 koningen (voor roccade) kunnen op 2 vakjes staan
de 4 torens kunnen op 64 vakjes staan
de 4 koningen (voor roccade) kunnen op 4 vakjes staan
de 2 dames kunnen op 64 vakjes staan
de 4 lopers kunnen op 64 vakjes staan
de 4 paarden kunnen op 64 vakjes staan

Als je dit zooitje even opnieuw indeelt, kom je op de volgende opsomming:
6 vakjes waar koningen en torens kunnen staan voor roccade
48 vakjes waar pionnen kunnen staan
64 vakjes waar koningen, torens, dames, lopers en paarden kunnen staan

Nog een keer door elkaar husselen levert op:
• 6 vakjes waar alle stukken kunnen staan behalve pionnen (toren (voor roccade en na roccade) wit en zwart, loper wit en zwart, paard wit en zwart, dame wit en zwart en koning (voor roccade en na roccade) wit en zwart) = totaal 14 verschillende stukken +1 (leeg vakje)
• 13 vakjes waar alle stukken kunnen staan na roccade behalve pionnen (toren wit en zwart, loper wit en zwart, paard wit en zwart, dame wit en zwart en koning wit en zwart) = totaal 12 verschillende stukken +1 (leeg vakje)
• 48 vakjes waar alle stukken kunnen staan na roccade(toren wit en zwart, loper wit en zwart, paard wit en zwart, dame wit en zwart en koning wit en zwart) en pion wit zwart = totaal 14 verschillende stukken +1 (leeg vakje)

Dit opgeteld geeft 6¹⁵*13¹³*48¹⁵ = ca. 2,356*10⁵¹ stellingen

Deze berekening heb ik toen uitgevoerd om te bepalen hoe ik op zo'n kort mogelijke manier elke unieke schaakstelling kon noteren. Ik kwam toen uit op 64 vakjes * 4 bits (maximaal aantal stukken + leeg = 15 (past in 4 bits)) = 256 bits of wel 32 bytes.

Mijn doel was dus uiteindelijk een database te maken met daarin de volgende data (huidige stelling, beste volgende stelling als wit heeft gezet en beste volgende stelling als zwart heeft gezet). Elk record bevatte dus 3 velden maal 32 bytes=96 bytes.

De totale db zou dus uitkomen op 2,106*10⁴⁴ GByte.
Ondanks het feit dat er nog een hoop stellingen teveel in zitten ( geen dubbele, maar wel stellingen met meer dan 18 dames bijv.), ben ik op dit punt dus maar gestopt met mijn gedachtengang

[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]

[Verwijderd]

Even een opmerking:

Bedoel je met : "4 lopers kunnen op 64 vakjes staan" dat elke loper op 64 vakjes kan staan.

Zo ja: heb je er wel aan gedacht dat een loper op maar enkel op zijn 'eigen kleur kan lopen' en aangezien er 32 witte en 32 zwarte vlakken zijn betekend dit dus dat elke loper maar op 32 vakjes kan staan en niet op 64!!!

Hopelijk is dit niet een nachtmerrie voor je...

[Mx. Alba]

Denk wel dat een pion niet op 64 vakjes kan staan - zelfs niet op 6x8=48 vakjes... Ze moeten immers altijd naar voren lopen! De 2 middelste pionnen kunnen op 32 vakjes staan, alle andere pionnen op minder! Totaal voor de pionnen kom je dus op:

4 pionnen die op 32 plaatsen kunnen staan,
4 pionnen die op 30 plaatsen kunnen staan,
4 pionnen die op 26 plaatsen kunnen staan, en
4 pionnen die op 21 plaatsen kunnen staan.

De 4 lopers kunnen ieder slechts op 32 vakjes staan.

In principe maakt voor het aantal mogelijke schaakstanden de vraag of de koning wel of niet een roccade heeft aangegaan niet uit. (Wel voor het spel dat daarna zou kunnen volgen, maar daar gaat het niet om!)

Verder moet je rekening houden met promoverende pionnen. Door promoverende pionnen kunnen maximaal 12 willekeurige stukken in het spel komen (door pionslagen kunnen per 2 rijen maximaal 3 pionnen promoveren), die elk de volledige beweginsvrijheid van 64 vlakken hebben, tenzij het natuurlijk lopers worden...

Maarja, het ligt eraan wat je wilt berekenen. Als je echt precies wilt berekenen hoeveel mogelijke standen er zijn, ben je tot Sint Juttemis bezig met alle mogelijke uitzonderingen. Als je een bovengrens wil hebben, dan bereken je simpelweg:

24 x 64 vlakken (2x6 stukken + 12 door promotie), en
20 x 32 vlakken (2x8 pionnen + 2x2 lopers (hier wordt dus met de pionnen wat valsgespeeld om het makkelijk te houden))

Dan moet je er ook nog op letten dat koningen altijd op het bord staan, terwijl alle andere stukken er wel of niet kunnen zijn...

Je moet dan dus eigenlijk de som gaan uitrekenen van alle mogelijke standen van alle mogelijke aantallen stukken van 2 x 64 vlakken (twee koningen) t/m het hierbovenbeschrevene.

Mijn calculus is helaas volledig weggezakt. Kan iemand ff uitrekenen?

[jvdmeer]

Verwijderd schreef op 08 november 2002 @ 12:30:
Even een opmerking:

Bedoel je met : "4 lopers kunnen op 64 vakjes staan" dat elke loper op 64 vakjes kan staan.

Zo ja: heb je er wel aan gedacht dat een loper op maar enkel op zijn 'eigen kleur kan lopen' en aangezien er 32 witte en 32 zwarte vlakken zijn betekend dit dus dat elke loper maar op 32 vakjes kan staan en niet op 64!!!

Nee, daar had ik aan gedacht, maar dat feit wordt bij de volgende van husselen pas duidelijk:
op de 32 witte vlakjes kan een witte of zwarte loper staan en op de 32 zwarte vlakjes kan een witte of zwarte loper staan. Dat samen geeft dat op elk van de 64 vakjes een witte of zwarte loper kan staan.
Dus vandaar tel ik voor alle 64 de vakjes 2 stukken (loper wit of zwart)
Het einddoel voor mij was het aantal mogelijke stellingen berekenen, en daarvoor is het genoeg om op elk vakje vaststellen welke stukken er kunnen staan, dat heb ik dus proberen te beredeneren en uit te rekenen.

[Verwijderd]

offtopic: d2-d4 is absoluut niet de beste openingszet

misschien ben ik gek, maar kun je wel zeggen dat bijvoorbeeld 4 lopers op 64 velden kunnen staan, aangezien er natuurlijk al velden bezet zijn door andere stukken. Moet je hier geen rekening mee houden in je berekening?

[Verwijderd]

Wordt er ook rekening mee gehouden dat bepaalde stellingen, hoewel ze qua positie van de stukken volstrekt reglementair zijn, niet voor kunnen komen, omdat ze door geen enkel partijverloop kunnen worden bereikt (retrograad bekeken dus)? Ik bedoel bijvoorbeeld de stelling
Wit: Kc4
Zwart: Ka8, Dh5, Th4, Th3.

[jvdmeer]

Mx. Alba schreef op 08 november 2002 @ 13:02:
Denk wel dat een pion niet op 64 vakjes kan staan - zelfs niet op 6x8=48 vakjes... Ze moeten immers altijd naar voren lopen! De 2 middelste pionnen kunnen op 32 vakjes staan, alle andere pionnen op minder! Totaal voor de pionnen kom je dus op:

4 pionnen die op 32 plaatsen kunnen staan,
4 pionnen die op 30 plaatsen kunnen staan,
4 pionnen die op 26 plaatsen kunnen staan, en
4 pionnen die op 21 plaatsen kunnen staan.

Dit klopt, maar het uiteindelijke doel was voor mij vast stellen hoeveel verschillende stukken op een bepaald vlakje konden staan. Met mijn redenering kunnen de pionnen op die bewuste 48 vlakjes staan.

Mx. Alba schreef op 08 november 2002 @ 13:02:De 4 lopers kunnen ieder slechts op 32 vakjes staan.

In principe maakt voor het aantal mogelijke schaakstanden de vraag of de koning wel of niet een roccade heeft aangegaan niet uit. (Wel voor het spel dat daarna zou kunnen volgen, maar daar gaat het niet om!)

De lopers heb ik in een posting ietsje hoger al toegelicht. En volgens de FIDE is een stuk wat een roccade nog mag doen, een ander stuk dan een stuk dat geen roccade meer mag doen. Die uitspraak is ooit geweest na een remise n.a.v. de 3-zetten-regel. De bewuste speler claimde toen dat de koning die in drie zetten had bewogen door die stap heen en terug zijn uitgangspositie (mogelijke roccade) niet gelijk was de huidige situatie (roccade niet meer mogelijk). De FIDE gaf hem in een later stadium daarop gelijk. Ik behandel daarom de onbewogen koning en torens als andere stukken als de bewogen versie.

Mx. Alba schreef op 08 november 2002 @ 13:02:Verder moet je rekening houden met promoverende pionnen. Door promoverende pionnen kunnen maximaal 12 willekeurige stukken in het spel komen (door pionslagen kunnen per 2 rijen maximaal 3 pionnen promoveren), die elk de volledige beweginsvrijheid van 64 vlakken hebben, tenzij het natuurlijk lopers worden...

Volgens mij moeten alle 16 de pionnen in een spel kunnen promoveren door andere stukken op te offeren. (Bijvoorbeeld wit offert de twee lopers en de twee paarden en zorgt dat de zwarte pionnen op [A,C,E,G][7,6] terecht komen en zwart offert stukken op zodat de pionnen op [B,D,F,H][1,2] terechtkomen. Hierna kunnen ze probleemloos passeren/promoveren.

Mx. Alba schreef op 08 november 2002 @ 13:02:Maarja, het ligt eraan wat je wilt berekenen. Als je echt precies wilt berekenen hoeveel mogelijke standen er zijn, ben je tot Sint Juttemis bezig met alle mogelijke uitzonderingen.

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.

[jvdmeer]

Verwijderd schreef op 08 November 2002 @ 13:29:
Wordt er ook rekening mee gehouden dat bepaalde stellingen, hoewel ze qua positie van de stukken volstrekt reglementair zijn, niet voor kunnen komen, omdat ze door geen enkel partijverloop kunnen worden bereikt (retrograad bekeken dus)? Ik bedoel bijvoorbeeld de stelling
Wit: Kc4
Zwart: Ka8, Dh5, Th4, Th3.

Dat was dus mijn ultieme doel, terwijl dat in praktijk onmogelijk is . Door vanaf de beginstelling (stelling 1) te begin met rekenen, volgde daaruit 20 nieuwe stellingen (2 t/m 21). Hierna zou ik die 20 nieuwe stellingen gaan evalueren met elk mogelijk zwart antwoord. En dan kwam ik op 400 nieuwe stellingen.
Deze 400 moesten dan weer bekeken worden met de 2e witte zet. Aangezien elke stelling een uniek nummer heeft dat afhankelijk is van de stelling, zouden dubbele zetten hier al uit gefilterd worden. Bijv. d4,d5,Ta3 geeft het zelfde uniek stelling als Ta3,d5,d4.
Zo leek het mij mooi om het hele spel door te rekenen, en dan vanaf alle winststellingen terug te rekenen om een ratio per zet toe te kennen.
Hierna hou je dus een db over met een stelling en de beste witte en de beste zwarte zet.

[Verwijderd]

jvdmeer schreef op 08 november 2002 @ 13:32:
[...]
En volgens de FIDE is een stuk wat een roccade nog mag doen, een ander stuk dan een stuk dat geen roccade meer mag doen. Die uitspraak is ooit geweest na een remise n.a.v. de 3-zetten-regel. De bewuste speler claimde toen dat de koning die in drie zetten had bewogen door die stap heen en terug zijn uitgangspositie (mogelijke roccade) niet gelijk was de huidige situatie (roccade niet meer mogelijk). De FIDE gaf hem in een later stadium daarop gelijk. Ik behandel daarom de onbewogen koning en torens als andere stukken als de bewogen versie.

Hetzelfde probleem doet zich voor in verband met de en passant regel. Als in de volgende stelling
Wit: Ka1, d4
Zwart: Ka8, e4 (zwart aan zet)
wits laatste zet d2-d4 was, heeft zwart de mogelijkheid e4xd3; als wits laatste zet bijvoorbeeld Ka2-a1 was, heeft zwart die mogelijkheid niet. Hoewel de positie van de stukken hetzelfde is, zijn het dus eigenlijk twee verschillende stellingen.

[Mx. Alba]

jvdmeer schreef op 08 november 2002 @ 13:32:
Dit klopt, maar het uiteindelijke doel was voor mij vast stellen hoeveel verschillende stukken op een bepaald vlakje konden staan. Met mijn redenering kunnen de pionnen op die bewuste 48 vlakjes staan.

Oké, dat is duidelijker.

De lopers heb ik in een posting ietsje hoger al toegelicht. En volgens de FIDE is een stuk wat een roccade nog mag doen, een ander stuk dan een stuk dat geen roccade meer mag doen. Die uitspraak is ooit geweest na een remise n.a.v. de 3-zetten-regel. De bewuste speler claimde toen dat de koning die in drie zetten had bewogen door die stap heen en terug zijn uitgangspositie (mogelijke roccade) niet gelijk was de huidige situatie (roccade niet meer mogelijk). De FIDE gaf hem in een later stadium daarop gelijk. Ik behandel daarom de onbewogen koning en torens als andere stukken als de bewogen versie.

Dat is ook duidelijk nu.

Volgens mij moeten alle 16 de pionnen in een spel kunnen promoveren door andere stukken op te offeren. (Bijvoorbeeld wit offert de twee lopers en de twee paarden en zorgt dat de zwarte pionnen op [A,C,E,G][7,6] terecht komen en zwart offert stukken op zodat de pionnen op [B,D,F,H][1,2] terechtkomen. Hierna kunnen ze probleemloos passeren/promoveren.

Daar had ik inderdaad overheengekeken...

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.

Hmmm...

Oké.

Maar je moet dan wel wit en zwart scheiden.

En wat dan ook moeilijk wordt: die 16 mogelijke promotiestukken! Dat kan namelijk in principe alles zijn...

[Mx. Alba]

Verwijderd schreef op 08 November 2002 @ 13:57:
Hetzelfde probleem doet zich voor in verband met de en passant regel. Als in de volgende stelling
Wit: Ka1, d4
Zwart: Ka8, e4 (zwart aan zet)
wits laatste zet d2-d4 was, heeft zwart de mogelijkheid e4xd3; als wits laatste zet bijvoorbeeld Ka2-a1 was, heeft zwart die mogelijkheid niet. Hoewel de positie van de stukken hetzelfde is, zijn het dus eigenlijk twee verschillende stellingen.

Als dat kon, denk je dan niet dat dat al gedaan was voor of door superschaakcomputers?

[jvdmeer]

Verwijderd schreef op 08 november 2002 @ 13:57:Hoewel de positie van de stukken hetzelfde is, zijn het dus eigenlijk twee verschillende stellingen.

Klopt, nooit aangedacht weer alles opnieuw uitrekenen. De en-passant situatie was ik vergeten, omdat dat nooit ter discussie is geweest met de 3-zetten-regel. dat betekent dus dat pionnen op rij 4 en 5 daar in twee situatie kunnen staan.

[Verwijderd]

Mx. Alba schreef op 08 November 2002 @ 14:20:
[...]


Als dat kon, denk je dan niet dat dat al gedaan was voor of door superschaakcomputers?

Sorry, als wat kon?
En schaakprogramma's/computers zijn gericht op het vinden van de sterkste zetten, niet op het tellen van het aantal mogelijke stellingen.

[Dido]

Verwijderd schreef op 08 november 2002 @ 15:23:Sorry, als wat kon?
En schaakprogramma's/computers zijn gericht op het vinden van de sterkste zetten, niet op het tellen van het aantal mogelijke stellingen.

De brute-force manier om een spel op te lossen is precies wat jij omschrijft...
En als je daar een oplossing voor vindt, dan veeg je Deep Blue en Fritz van tafel.
Aangezien er (hoeveel dan ook) een beperkt aantal zetten is, is er een oplossing (de perfecte schaakpartij met altijd dezelfde uitkomst).
Als die gevonden wordt is het wel over met schaken. Kunnen we aan go beginnen.

[Verwijderd]

Dido schreef op 08 November 2002 @ 15:58:
[...]

De brute-force manier om een spel op te lossen is precies wat jij omschrijft...
En als je daar een oplossing voor vindt, dan veeg je Deep Blue en Fritz van tafel.
Aangezien er (hoeveel dan ook) een beperkt aantal zetten is, is er een oplossing (de perfecte schaakpartij met altijd dezelfde uitkomst).
Als die gevonden wordt is het wel over met schaken. Kunnen we aan go beginnen.

Sorry maar dan vergeet je de faktor tijd. Via Brute Force is het al heel lang mogelijk ALLE zetten door te rekenen die mogelijk zijn en deze ook nog eens korrekt te waarderen. Maar de tegenstander moet niet van ouderdom zijn overleden voordat er een antwoord komt op zijn e2-e4 Op dit moment stopt men bij zet 8 en dat is zeer zeker voldoende om 99,99% van de wereldbevolking te verslaan.

Personen als Kasparov, Karpov enzo denken een 6 tot 8 zetten vooruit. Maar een groot gedeelte van de tijd schaakt men op gevoel (als een zet niet lekker aanvoelt is die ook niet goed) en kapt men zo volledige takken af (wat een computer dus vaak niet doet).

[Verwijderd]

Dido schreef op 08 november 2002 @ 15:58:
[...]

De brute-force manier om een spel op te lossen is precies wat jij omschrijft...
En als je daar een oplossing voor vindt, dan veeg je Deep Blue en Fritz van tafel.
Aangezien er (hoeveel dan ook) een beperkt aantal zetten is, is er een oplossing (de perfecte schaakpartij met altijd dezelfde uitkomst).
Als die gevonden wordt is het wel over met schaken. Kunnen we aan go beginnen.

Ik dacht niet dat ik dat omschreef.

Er worden in de betere schaakprogramma's allerlei "intelligente" methoden toegepast om tot de beste zetten te komen zonder dat daarvoor een veelheid aan zinloze varianten wordt doorgerekend. Moet ook wel want voor een pure brute force methode ontbreekt (voorlopig) gewoon de rekenkracht.

[Verwijderd]

asjmenouw respect voor de mensen die hier rekenen
na 2 reply gelezen te hebben moest ik huilen en nu pak ik een biertje voor ik depri wordt

[Dido]

Verwijderd schreef op 08 november 2002 @ 16:59:Ik dacht niet dat ik dat omschreef.

Dan begreep ik dit:

Mijn doel was dus uiteindelijk een database te maken met daarin de volgende data (huidige stelling, beste volgende stelling als wit heeft gezet en beste volgende stelling als zwart heeft gezet). Elk record bevatte dus 3 velden maal 32 bytes=96 bytes.

kennelijk verkeerd.
Een database met 'beste' stellingen (dus resultaat van beste zetten) lijkt me precies watr je nodig hebt om tot de oplossing van het schaakspel te komen.
uiteindelijk hoort namelijk bij ieder stelling 1 beste zet, inclusief bij de openingsstelling. En van daaruit kun je dus de perfecte partij spelen.
Dat dat je doel was begreep ik ook uit je opmerking dat je aan wou tonen of een bepaalde zet de beste openingszet was.

Ik heb trouwens zo'n vermoeden dat als schaak wordt opgelost, de oplossing altijd tot remise leidt...

[Diadem]

Het exacte aantal legale schaakstellingen is eigenlijk onmogelijk te geven. Er zijn teveel dingen die meespelen. Wat we dus willen bereiken is het geven van een zo laag mogelijke bovengrens.

Om te beginnen bekijken we een aanverwant probleem: Het aantal mogelijke verschillende stellingen, waarbij de stukken in exact dezelfde stand staan.

Je hebt rochade recht voor wit, zowel kort als lang. Alsmede voor zwart. Dit geeft dus al 16 verschillende mogelijkheden. Dan heb je nog het aan zet zijn van wit of zwart, wat een 5e bit geeft. Tot slot nog hebben we de en passant regel. Hiervoor is het relevant of een pion eventueel als laatste 2 vooruit gezet kan zijn geweest. Als wit pionnen heeft op b5, e5 en g5, en zwart op a5, c5, d5, f5, h5, dan kan in theorie elk van de zwarte pionnen als laatste gezet zijn. Dit is het maximale aantal. Dit geeft 6 mogelijkheden voor de laatste zet van zwart, of een van de pionnen, of geen van de pionnen. Zetten we de andere pionnen op de 4e rij, dan zijn er als zwart aan zet is maar 4 mogelijkheden.

Het totaal aantal mogelijkheden is dus 2⁴ * (4+6) = 160.

Er zijn natuurlijk slechts enkele stellingen met inderdaad 160 mogelijke verschillen terwijl de stukken hetzelfde staan. Laten we voor het gemak doen alsof alle stellingen zo zijn. Dan hoeven we alleen nog maar het aantal verschillende manieren waarop de stukken legaal kunnen staan te berekenen en we hebben een bovengrens.

En dat getal ga ik na het eten berekenen

[edit]
In die andere thread gaf ik nog 2¹² voor bovenstaande waarde. Ik heb daar dus inmiddels wat beter over nagedacht

[edit2]
De 5e bit voor de zetkleur valt weg, doordat ik die in het en-passant kunnen slaan heb gestopt. Je zou ook kunnen opmerken dat met alle pionnen gelijk om en om verdeeld over de 4e en 5e rij beide partijen 5 mogelijheden hebben voor en passant (niet, of elk vande 4 pionnen). Dan wordt het dus 2⁴ * 2 * 5 wat natuurlijk precies hetzelfde is. (idd, 5+3 is gelijk aan 4+4 )

[Zoefff]

Mx. Alba schreef op 08 November 2002 @ 13:02:
Denk wel dat een pion niet op 64 vakjes kan staan - zelfs niet op 6x8=48 vakjes... Ze moeten immers altijd naar voren lopen! De 2 middelste pionnen kunnen op 32 vakjes staan, alle andere pionnen op minder!

Is het niet zo dat er ook een zet is, waarbij je met je pion schuin achteruit een stuk kan slaan?

D8 ik nl ooit ergens gelezen te hebben? Ken niet alle regels van schaak hoor..

code:

x = pion
o = ander stuk

 x          
 o     ==>   xo    ==>      x

Zo dus... of isset niet duidelijk

Dan betekent het dat de pionnen nl wél op 8*8=64 plekken kunnen staan..

[Verwijderd]

zoeff: neen. achteruit met een pion is niet toegestaan
Wat jij bedoelt is de en passant regel. en dat is schuin naar voren.

indien op d4 een zwarte pion staat en wit speelt e2-e4 dan komt deze pion over e3 heen welke de plek zou zijn waar zwart zou mogen slaan.

[Zoefff]

Verwijderd schreef op 09 november 2002 @ 18:57:
zoeff: neen. achteruit met een pion is niet toegestaan
Wat jij bedoelt is de en passant regel. en dat is schuin naar voren.

indien op d4 een zwarte pion staat en wit speelt e2-e4 dan komt deze pion over e3 heen welke de plek zou zijn waar zwart zou mogen slaan.

Ah... ok...klikt ook wel logischer eigenlijk

[Diadem]

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]

Even terzijde: De meeste experts zijn het er wel over eens dat het schaakspel mits goed gespeeld remise is.

En je hebt vrij veel speelruimte voordat je je remise verspeelt. Je kunt je het dus ook permiteren om met a3 te beginnen, waarschijnlijk. Helemaal zeker weet je het natuurlijk nooit, maar zeer waarschijnlijk is het wel.

Aan Bobby Fischer werd eens gevraagd of hij van God zou kunnen winnen. Toen antwoorde hij: "Met zwart zou het heel moeilijk worden, maar als ik wit zou zijn, dan speelde ik gewoon spaans, en moest ik zeker remise kunnen houden".

Kijk, dat bedoel ik nu

[Verwijderd]

Diadem schreef op 09 November 2002 @ 19:02:
[...]
Aan Bobby Fischer werd eens gevraagd of hij van God zou kunnen winnen. Toen antwoorde hij: "Met zwart zou het heel moeilijk worden, maar als ik wit zou zijn, dan speelde ik gewoon spaans, en moest ik zeker remise kunnen houden".

Hieruit kun je dus afleiden dat Fischer 1. ... e7-e5 voor God het beste antwoord op 1. e2-e4 vond. Fischers favoriete verdediging tegen 1. e2-e4 was 1. ... c7-c5. Zou God een brakke Siciliaan hebben? Ik kan het me nauwelijks voorstellen.

[Diadem]

Verwijderd schreef op 09 november 2002 @ 19:56:
[...]

Hieruit kun je dus afleiden dat Fischer 1. ... e7-e5 voor God het beste antwoord op 1. e2-e4 vond. Fischers favoriete verdediging tegen 1. e2-e4 was 1. ... c7-c5. Zou God een brakke Siciliaan hebben? Ik kan het me nauwelijks voorstellen.

Hmm, je hebt gelijk. Ik denk dat ik ergens een stukje van de quote mis dan. Want ik kan me niet voorstellen dat God's siciliaan slecht is

eens zoeken

[Dido]

In hoeverre je Fischer al te serieus moet nemen in wat ie zegt weet ik niet...

Was er laatst niet een grootmeester die er van overtuigd was dat ie op het internet tegen Fischer gespeeld had? (Nigel Short dacht ik, maar ik kan me vergissen).
Hij vertelde in ieder geval over 1 partij waarbij (supposedly) Fischer begon met de zetten a2-a3 tot h2-h3 om vervolgens rustig te winnen.
Dat soort gekken zijn natuurlijk hartstikke leuk, maar of je wat aan hun genialiteit hebt bij dit soort vraagstukken is dubieus

[Diadem]

Dido schreef op 10 november 2002 @ 15:26:
In hoeverre je Fischer al te serieus moet nemen in wat ie zegt weet ik niet...

Was er laatst niet een grootmeester die er van overtuigd was dat ie op het internet tegen Fischer gespeeld had? (Nigel Short dacht ik, maar ik kan me vergissen).
Hij vertelde in ieder geval over 1 partij waarbij (supposedly) Fischer begon met de zetten a2-a3 tot h2-h3 om vervolgens rustig te winnen.
Dat soort gekken zijn natuurlijk hartstikke leuk, maar of je wat aan hun genialiteit hebt bij dit soort vraagstukken is dubieus

Dat was inderdaad Short ja. En als Short van het bord wordt gehakt door iemand die begint met a2-a3 t/m h2-h3 (of zoiets) om vervolgens alsnog te winnen, dan kun je er vanuit gaan dat hij tegen Fischer hebt gespeeld, of tegen Kasparov in een gekke bui. Want Short is namelijk geen prutser.

Fischer is waarschijnlijk de minst begrepen sporter ooit. Of hij ze allemaal op een rijtje heeft is nog de vraag, maar hij is minder gek dan sommige mensen soms denken. Hij is alleen erg gedesillusioneerd in de schaakwereld, en dan voornamelijk in de bobo's van de Fide. Dat is een reden dat hij gestopt is, de tweede is dat er voor hem niets meer te winnen viel. Hij zal nu altijd een legende blijven, als hij was blijven spelen en oud was geworden, tsja, dan weet je het niet. Ook wel waarschijnlijk, maar minder.

En als je Fischer, of Kasparov, wit geeft tegen God, dan ben ik er van overtuigd dat ze remise moeten kunnen houden.

[Verwijderd]

Diadem schreef op 10 november 2002 @ 21:51:
[...]

En als je Fischer, of Kasparov, wit geeft tegen God, dan ben ik er van overtuigd dat ze remise moeten kunnen houden.

Alleen als ze in absolute topvorm zijn en geen moment van twijfel kennen. Wedstrijdschaken is mentaal een zeer zware bezigheid, en wat dat betreft is god onverslaanbaar, denk ik. Die twijfelt namelijk nooit, en zeker niet aan zichzelf.

[Verwijderd]

/me heeft deze draad stilletjes gevolgd, nu het wat offtopic gaat mijn bijdrage:

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.

_{De formule die Shannon gebruikte staat in "Philosophical Magazine 41:256-275" uit 1950 maar ik kan hem nergens online vinden.}

[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.