matematikk.net

Mulig dette er noe offtopic, men jeg kjører på:

Jeg har spilt en del sjakk, og i den forbindelse har jeg ofte fundert over hvorvidt det hele tiden finnes et beste-trekk eller ikke. Rent matematisk vil jeg jo anta at det til en hver tid finnes et slikt trekk. Men med tanke på at sjakk har blitt spilt i flere tusen år, er det jo i såfall merkelig at toppspillere likevel velger svært ulike trekk i åpningen!

Gitt at det alltid finnes et trekk som er bedre enn alle andre lovlige trekk, og disse trekkene spilles fra start, har vi følgende tre mulige utfall:

• 1: Uansett motspill vil hvit vinne.
  2: Med perfekt motspill vil sort uansett vinne.
  3: Med perfekt motspill vil det uansett bli remis.

Dersom vi i framtiden har kraftige nok datamaskiner til å analysere alle mulige trekk, fra åpningen til sluttspillet, vil jo sjakk bli "løst". Da kan sjakspillere bare memorere alle beste-trekkene. Problemet ligger vel i at dersom motspilleren ikke spiller det beste svartrekket, må en selv begynne å kalkulere selv. Å huske alle mulige varianter vil jo være umulig. For et menneske. For datamaskiner derimot, er saken annerledes. Ved å lage en enorm tabell kan enkelt lage en sjakkcomputer som blir uslåelig.

Alternativt er det ikke mulig å peke ut et beste-trekk.

Ser dere på dette som et matematisk eller filosofisk et spørsmål? Tror dere det alltid finnes et bestre-trekk? Vil det (eventuelle) perfekte partiet noen gang bli spilt?

Tror problemet her er at det er UMULIG å memorisere de perfekte trekkene.

De perfekte trekkene som gjelder for et spill, kan umiddelbart gjøres udugelige dersom motspilleren gjør ET trekk som ikke faller innenfor det perfekte spillet. Altså man kan ikke stole på at motspilleren lar deg spille de trekkene du har memorisert.

Dette gjør (i min mening) at det ikke finnes noe beste-trekk, fordi det krever at motspilleren til enhver tid gjør SITT beste-trekk. Hvis han ser at du vinner den, så kan han gjøre et ikke-beste-trekk, så er man tilbake på å spille fra evner, og ikke minne fordi det er helt uaktuelt at en person memoriserer to eller flere perfekte partier med alle beste-trekk for begge spillere.

Enig det, men for datamaskiner er det vel mulig? Et beste-trekk tar jo høyde for alle mulige motspill - også de som ikke er best. Spørsmålet blir jo så om det er mulig å regne fram alle disse trekkene. Det finnes sikkert flere mulige sjakkposisjoner enn atomer i universet, så det er en enorm regnejobb som skal til!

Hva som er det beste trekket avhenger av hvor mange trekk man ser fram i tid. En datamaskin som tar et trekk basert på alle mulige trekkombinasjoner for, la oss si en million trekk, kan man kanskje si er tilnærmet det perfekte trekk. Men en så kraftig maskin finnes vel ikke.

“The possible number of chess games is so huge that no one will invest the effort to calculate the exact number.”

Og ja, antall atomer i universet kan knapt sies å være en brøkdel engang. Det er estimert at antall sjakkpartier er over [tex]10^{100,000}[/tex] men det blir jo et slags minimum, siden ingen gidder å undersøke det. Vi må nok vente noen år slik at prosesseringskrafta til maskinene økes mer.

Lag en Java-tutororial for det da, Aleks ^^

Forøvrig liker jeg Javavideoene dine godt, må øve litt mer på java i sommer, så mulig de blir brukt noe mer!

fuglagutt skrev:Lag en Java-tutororial for det da, Aleks ^^

Forøvrig liker jeg Javavideoene dine godt, må øve litt mer på java i sommer, så mulig de blir brukt noe mer!

Apropos udl, har du vurdert å utvide udl med en Python tutorial også, alex ? Python er jo mye brukt til å gjøre matematikk også, så tipper det kunne blitt populært med videoer om vitenskapelig bruk av python. (f.eks. bruk av scipy, numpy,pyplot etc. )

Skal nevnes at det ikke er jeg som lager Java-videoene. Det er en kompis av meg. Jeg lager bare matten.

En annen kompis ytra at han ville lage Python-videoer, men det ble ikke noe av.

Aleks855 skrev:Dette gjør (i min mening) at det ikke finnes noe beste-trekk, fordi det krever at motspilleren til enhver tid gjør SITT beste-trekk. Hvis han ser at du vinner den, så kan han gjøre et ikke-beste-trekk, så er man tilbake på å spille fra evner, og ikke minne fordi det er helt uaktuelt at en person memoriserer to eller flere perfekte partier med alle beste-trekk for begge spillere.

Der er jeg uenig. Ihvertfall om vi har samme definisjon på "beste trekk".

"Beste trekk" kan vel ses på som et lokalt eller globalt problem.

I det lokale problemet har du en eller annen evalueringsfunksjon $f$ som tar en sjakkposisjon som input og gir tilbake et reellt tall, som et mål på "hvor god er denne posisjonen for meg?". Det beste trekket er det som maksimerer denne funksjonen. Dette er i prinsippet lett å utføre hvis man har en grei måte å evaluere $f$ på.

Vi kan se på "tilstandsrommet" til sjakk som et tre som begynner i startposisjonen, og hvert mulige trekk fra en gitt posisjon starter en ny gren. La oss si at treet "over" en posisjon $p$ består av alle posisjoner som kan nås fra $p$ (Dette kalles filteret utspent av $p$ i ordenteori).

Det lokale problemet kan gjøret til et globalt problem ved å la $f(p)$ være en funksjon av hele treet over $p$. Dvs. du må ta hensyn til alle mulige mottrekk fra motspilleren, samt alle dine mulige resulterende trekk, etc., i motsetning til det lokale problemet, der vi kun der på treet ett nivå over $p$.

Vi kan selvfølgelig lage "semi-lokale" evalueringsfunksjoner $f_n(p)$ som tar hensyn til treet $n$ nivåer over $p$. Hvis vi har en lokal evalueringsfunksjon $f$, kan vi iterere denne for å lage en semilokal funksjon, eller en global funksjon hvis du ikke bryr deg om regnetiden. Det vanskelige er å lage en god evalueringsfunksjon. Det er tross alt ikke lett å beskrive noe så komplekst og nyansert som en sjakkposisjon med ett enkelt tall. Man må ta hensyn til både taktiske bidrag og strategiske bidrag. Begge implementasjonene er høyst ikketrivielle.

Moderne sjakkmaskiner maksimerer semilokale evalueringsfunksjoner når de utfører trekk. Krav til regnetid osv. setter selvfølgelig grenser for hvor nøye datamaskinen kan lete gjennom tilstandsrommet, og mye forsking går ut på nettopp å optimalesere søketiden ved hjelp av ulike heuristikker.

Jeg skjønner noe av det du sier, men mye av det er teori jeg ikke har forkunnskapene for å diskutere.

Men det ser ut som problematikken bunner ut i at vi prøver å kvantisere noe som virker som en veldig filosofisk problemstilling.

I tilleg er det viktig å skille mellom "alle" sjakkposisjoner, teoretiske sjakkposisjoner og reelle sjakkposisjoner.
Eksempelvis så settes det begrensinger etter 50 trekk på spilleren, i tillegg til at om en ender i en loop ender spillet i remis.
På bakgrunn av de faktiske begrensingene finnes det bare et endelig antall sjakkspill som er mulig å utføre.

Merk dette tallet
er fortsatt latterlig høyt, langt høyere enn noen datamaskiner i dag, eller overskuelig fremtid kan klare å beregne (i farten var
det snakk om rundt $10^{70}$ mulige parti, som fortsatt er flere parti enn atomer i universet..), men det er langt i fra "uendelig" eller noen
filosofisk diskusjon. Det er enkelt og greit et spørsmål om tid før alle mulige sjakkparti er annalysert, langt tid ja, men endelig.

Shougen eller Go!, derimot vil ta mye mye lengre tid :p

Hvor lenge siden er det en profesjonell sjakkspiller klarte å slå en superdatamaskin ?

EDIT: Ser jeg bommet grovt på antall ulige parti, men det er fortsatt endelig og igjen bare spørsmål om tid

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

Når alle mulige sjapparti er analysert vil det alltid finnes et eller flere trekk som er best mulig. Spørsmålet vil da heller være om hvit alltid vinner, eller om alle sjakkparti vil ende i remis.

Oppgave:

Spillet Skajakk er som sjakk, men hver spiller gjør to trekk om gangen, i stedet for bare ett. Vis at hvit uansett kan hindre at svart vinner.

Anta at svart har en vinnende strategi. Da kan hvit flytte hesten sin ut og tilbake i samme trekk og dermed reversere situasjonen og bruke svart
sin vinnende strategi. Hvis svart skulle gjøre nøyaktig det samme ville situasjonen stått stille, og det er en regel som sier at hvis samme stilling oppstår
for tredje gang så blir det remis.

Følger opp med en ny sjakkgåte jeg fikk av min lærer (for en tid tilbake) i forbindelse med temaet kombinatorikk:

Anta at en springer står på a1. Finnes det en lovlig trekkrekkefølge slik at springeren ender på h8 og på veien er innom hvert felt én gang?

Når en springer beveger seg vil feltet den går til alltid ha motsatt farge av det den stod på. Altså vil en springer som starter på et sort felt og beveger seg
n trekk være på et svart felt dersom n er et partall og på et hvitt felt om n er et oddetall. For å bevege seg fra a1 til h8 og i tillegg være innom alle feltene på
brettet krever 63 trekk. Siden a1 er et svart felt vil det si at springeren ender på et hvitt felt, som motsier at den kan ende på h8, siden dette feltet også er svart.