|
|
 | Travelling saleman problem
Fra : Jakob |
Dato : 17-03-04 13:51 |
|
Hej NG
Læser her i Aktuel Videnskab, som er fra september-oktober 2003, at
problemmet med sælgeren, der skal finde den korteste rute mellem 49
byer blev beregnet i 1954. Den korteste rute mellem alle verdens byer,
1.904.711 byer, blev fundet her for nylig.
Når man finder sådan en rute må man da approksimere en del, fordi man
kan da ikke sammenligne alle ruter på, som der findes.
Når man laver sådan en approksimation, kan der så muligvis ikke gå
bedre løsninger tabt?
/Jakob
PS. Samtlige ruter ved 49 byer er 49! og ved verdens samtlige byer er
det 1.904.711!, så mange muligheder vil da tage evigheder at regne ud
på en normal binær computer.
| |
 Ukendt (17-03-2004)
| Kommentar
Fra : Ukendt |
Dato : 17-03-04 14:04 |
|
"Jakob" <s031822@student.dtu.dk> wrote in message
news:svhg50ht1j9etldffttk7tihctq06hdo3c@4ax.com...
>
> Når man finder sådan en rute må man da approksimere en del, fordi man
> kan da ikke sammenligne alle ruter på, som der findes.
Har man fundet en korteste rute, så er der ingen, der er kortere. Der
anvendes typisk en metode som "branch & bound", som gør at man ikke
nødvendigvis skal beregne alle muligheder for at garantere, at det er
den korteste man har fundet. Men det er imponerende at have foretaget
beregningen med så mange punkter !
hilsen
Uffe
| |
Kristian Damm Jensen (17-03-2004)
| Kommentar
Fra : Kristian Damm Jensen |
Dato : 17-03-04 14:11 |
|
Jakob wrote:
> Hej NG
>
> Læser her i Aktuel Videnskab, som er fra september-oktober 2003, at
> problemmet med sælgeren, der skal finde den korteste rute mellem 49
> byer blev beregnet i 1954. Den korteste rute mellem alle verdens byer,
> 1.904.711 byer, blev fundet her for nylig.
>
> Når man finder sådan en rute må man da approksimere en del, fordi man
> kan da ikke sammenligne alle ruter på, som der findes.
Nej, man kan ikke beregne og sammenligne samtlige rute, men det behøver man
heller ikke. Hvis man tilrettelægger sin søgning "passende" kan man beskære
søgetræet kraftigt og komme langt under worst-case ... i praktiske
tilfælde. Man vil altid kunne opbygge et scenarie hvor det ikke er muligt
at finde den optimale løsning uden at beregne samtlige løsninger.
--
Kristian Damm Jensen damm (at) ofir (dot) dk
"I conclude that there are two ways of constructing a software design:
One way is to make it so simple that there are obviously no
deficiencies and the other way is to make it so complicated that there
are no obvious deficiencies." -- C.A.R. Hoare
| |
Thomas Krog (17-03-2004)
| Kommentar
Fra : Thomas Krog |
Dato : 17-03-04 16:10 |
|
> Man vil altid kunne opbygge et scenarie hvor det ikke er muligt
> at finde den optimale løsning uden at beregne samtlige løsninger.
Så vidt jeg ved er det endnu ikke bevist at der altid vil findes et scenarie
hvor samtlige muligheder skal afprøves. Det er vist blot den gængse
opfattelse at der altid vil findes et sådan scenarie.
/Thomas Krog
| |
Torben Ægidius Mogen~ (17-03-2004)
| Kommentar
Fra : Torben Ægidius Mogen~ |
Dato : 17-03-04 14:33 |
|
Jakob <s031822@student.dtu.dk> writes:
> Læser her i Aktuel Videnskab, som er fra september-oktober 2003, at
> problemmet med sælgeren, der skal finde den korteste rute mellem 49
> byer blev beregnet i 1954. Den korteste rute mellem alle verdens byer,
> 1.904.711 byer, blev fundet her for nylig.
>
> Når man finder sådan en rute må man da approksimere en del, fordi man
> kan da ikke sammenligne alle ruter på, som der findes.
>
> Når man laver sådan en approksimation, kan der så muligvis ikke gå
> bedre løsninger tabt?
>
> PS. Samtlige ruter ved 49 byer er 49! og ved verdens samtlige byer er
> det 1.904.711!, så mange muligheder vil da tage evigheder at regne ud
> på en normal binær computer.
Man behøver ikke at beregne alle kombinationer individuielt. Lad os
sige at du allerede har fundet en løsning på 1.3 Mkm. Hvis du
derefter er ved at afprøve en anden løsning og du allerede efter
halvdelen af byerne er nået over 1.3 Mkm, så der det ligegyldigt
hvilken rækkefølge de resterende byer kommer i, så du kan afskære
(N/2)! kombinationer på en gang.
De bedste TSP (travelling salesman problem) programmer bruger metoder,
der kan skære mange kombinationer væk meget tidligt i søgningen, så
den faktiske søgning er for et langt mindre antal ruter. Dermed kan
man finde en eksakt minimal løsning for selv et stort antal byer.
En af de ting man udnytter er geometrisk information: Man ved
f.eks. at den direkte vej mellem to byer er kortere end en omvej via
en tredie by (trekantsuligheden).
Hvis man har lov at approximere, så er problemet meget lettere
(afhængigt af hvor meget slæk du har lov til). F.eks. vil en grådig
algoritme (som stort set går ud på altid at vælge den nærmeste
ubesøgte by) i lineær tid give en løsning, der er maksimalt dobbelt så
lang som den optimale.
Torben
| |
Pongo (17-03-2004)
| Kommentar
Fra : Pongo |
Dato : 17-03-04 20:31 |
|
Torben Ægidius Mogensen wrote:
> Jakob <s031822@student.dtu.dk> writes:
>
>> Læser her i Aktuel Videnskab, som er fra september-oktober 2003, at
>> problemmet med sælgeren, der skal finde den korteste rute mellem 49
>> byer blev beregnet i 1954. Den korteste rute mellem alle verdens
>> byer, 1.904.711 byer, blev fundet her for nylig.
> De bedste TSP (travelling salesman problem) programmer bruger metoder,
> der kan skære mange kombinationer væk meget tidligt i søgningen, så
> den faktiske søgning er for et langt mindre antal ruter. Dermed kan
> man finde en eksakt minimal løsning for selv et stort antal byer.
Bare lige et lille afledt spørgsmål:
Benytter man også TSP-algoritmer i skak-programmer ?
Det forekommer mig, at der må være en del ligheder.
/Klaus
| |
 Henning Makholm (17-03-2004)
| Kommentar
Fra : Henning Makholm |
Dato : 17-03-04 20:45 |
|
Scripsit "Pongo" <Pongos.email@ddress>
> Benytter man også TSP-algoritmer i skak-programmer ?
> Det forekommer mig, at der må være en del ligheder.
Øhm, kan du ikke lige forklare dig lidt nøjere. Jeg kan ikke se anden
lighed end at begge problemer er "svære" (for en passende diffus værdi
af "svær").
[Branch-and-bound kan formentlig udnyttes med fordel i begge tilfælde,
men det gør den altså ikke til en "TSP-algoritme"]
--
Henning Makholm "Ligger Öresund stadig i Middelfart?"
| |
Pongo (17-03-2004)
| Kommentar
Fra : Pongo |
Dato : 17-03-04 21:03 |
|
Henning Makholm wrote:
>> Benytter man også TSP-algoritmer i skak-programmer ?
>> Det forekommer mig, at der må være en del ligheder.
>
> Øhm, kan du ikke lige forklare dig lidt nøjere. Jeg kan ikke se anden
> lighed end at begge problemer er "svære" (for en passende diffus værdi
> af "svær").
>
> [Branch-and-bound kan formentlig udnyttes med fordel i begge tilfælde,
> men det gør den altså ikke til en "TSP-algoritme"]
Jeg tænkte mest på, at man vel også er nødt til at gennemregne alle
mulige træk-kombinationer i et skakprogram, hvis man vil sikre at man
laver det bedst mulige træk. Jeg forstillede mig, at man kunne benytte
nogle af de samme trick, selvom det ikke var afstande man ønskede at
beregne.
Hvis man kunne beregne alle mulighederne til ende, burde man vel kunne
lave et program der aldrig ville tabe. Jeg kan godt se der kommer nogle
andre problematikker ind over. Vejen til målet er jo underordnet, bare
man når frem før modstanderen. Desuden har man jo en modstander som ikke
nødvendigvis bruger samme pointsystem til at beregne det bedste træk.
Jeg læste engang at der findes et endeligt antal mulige skakpartier.
Antallet stod faktisk også opgivet, men jeg har vanskeligt ved at se
hvordan man har fundet frem til tallet.
/Klaus
| |
Bertel Lund Hansen (17-03-2004)
| Kommentar
Fra : Bertel Lund Hansen |
Dato : 17-03-04 21:52 |
|
Pongo skrev:
>Jeg tænkte mest på, at man vel også er nødt til at gennemregne alle
>mulige træk-kombinationer i et skakprogram, hvis man vil sikre at man
>laver det bedst mulige træk.
I princippet, ja. Men et træks strategiske værdi ændrer sig under
spillet. Det sker ikke med transportveje.
>Hvis man kunne beregne alle mulighederne til ende, burde man vel kunne
>lave et program der aldrig ville tabe.
Nej. Der findes spil hvor det er givet hvem der vinder hvis begge
spiller optimalt. Måske er skak et sådant spil, men det vides
vist ikke.
>Jeg kan godt se der kommer nogle andre problematikker ind over.
>Vejen til målet er jo underordnet, bare man når frem før modstanderen.
Når frem før modstanderen? I skak?
--
Bertel
http://bertel.lundhansen.dk/ FIDUSO: http://fiduso.dk/
| |
Pongo (18-03-2004)
| Kommentar
Fra : Pongo |
Dato : 18-03-04 00:26 |
|
Bertel Lund Hansen wrote:
>> Jeg kan godt se der kommer nogle andre problematikker ind over.
>> Vejen til målet er jo underordnet, bare man når frem før
>> modstanderen.
>
> Når frem før modstanderen? I skak?
Det skulle forstås i lidt overført betydning. Målet er at sætte mat. Det
er ligegyldigt om man gør det hurtigst muligt, når blot man gør det før
sin modstander. På den måde er vejen til målet mere underordnet end i
TSP.
/Klaus
| |
Peter Græbe (18-03-2004)
| Kommentar
Fra : Peter Græbe |
Dato : 18-03-04 10:15 |
|
Bertel Lund Hansen skrev:
> Nej. Der findes spil hvor det er givet hvem der vinder hvis begge
> spiller optimalt. Måske er skak et sådant spil, men det vides
> vist ikke.
Optimalt spil fra begge parter burde vel resultere i remis?
--
Med venlig hilsen
Peter Græbe
| |
Peter Makholm (18-03-2004)
| Kommentar
Fra : Peter Makholm |
Dato : 18-03-04 10:20 |
|
Peter Græbe <graebe_fjern@webspeed.dk> writes:
> Optimalt spil fra begge parter burde vel resultere i remis?
Nej, der findes spil hvor den ene spiller har en fordel. Nim er et
sådan spil hvor den første spiller har en garanteret vinder-strategi.
--
Peter Makholm | First you fall in love with Antarctica, and then it
peter@makholm.net | breaks your heart
http://hacking.dk | -- Antarctica
| |
Peter Græbe (18-03-2004)
| Kommentar
Fra : Peter Græbe |
Dato : 18-03-04 16:48 |
|
Peter Makholm skrev:
> Nej, der findes spil hvor den ene spiller har en fordel. Nim er et
> sådan spil hvor den første spiller har en garanteret vinder-strategi.
Jeg burde have præciseret. Jeg havde kun skak i tankerne. Hvid har i
skak en fordel, fordi han trækker først - men denne fordel er ikke
afgørende.
--
Med venlig hilsen
Peter Græbe
| |
Torben Ægidius Mogen~ (18-03-2004)
| Kommentar
Fra : Torben Ægidius Mogen~ |
Dato : 18-03-04 17:39 |
|
Peter Græbe <graebe_fjern@webspeed.dk> writes:
> Peter Makholm skrev:
>
> > Nej, der findes spil hvor den ene spiller har en fordel. Nim er et
> > sådan spil hvor den første spiller har en garanteret vinder-strategi.
>
> Jeg burde have præciseret. Jeg havde kun skak i tankerne. Hvid har i
> skak en fordel, fordi han trækker først - men denne fordel er ikke
> afgørende.
I et spil uden tilfældigheder er en hver fordel afgørende. Hvis begge
sider spiller perfekt, vil udfaldet blive det samme hver gang. Hvis
dette er remis, har hverken sort eller hvid fordel. Hvis udfaldet er
sejr til sort eller hvid, så er sejren sikker og fordelen dermed
afgørende.
Det er kun hvis der er tilfældigheder i spillet (terninger eller
kort), hvor man kan tale om små fordele når begge spillere spiller
optimalt, f.eks. vil første spiller i Backgammon nok have en
statistisk fordel, men den er ikke ret stor. Hvis spillerne ikke er
perfekte, kan man også snakke om små fordele, men det er sværere at
ræsonere om.
Torben
| |
Peter Græbe (18-03-2004)
| Kommentar
Fra : Peter Græbe |
Dato : 18-03-04 18:57 |
|
Torben Ægidius Mogensen skrev:
> I et spil uden tilfældigheder er en hver fordel afgørende.
Hvis vi ser bort fra udefrakommende fænomener, er skak uden
tilfældigheder. Jeg kan sagtens forestille mig en stilling i skak, hvor
enten hvid eller sort har en fordel, den være sig positionel eller
materialemæssig, som ikke tilstrækkelig stor til at gennemtvinge
gevinst.
Fx visse slutspil med uligefarvede løbere.
> Hvis udfaldet er
> sejr til sort eller hvid, så er sejren sikker og fordelen dermed
> afgørende.
Det åbner vel også mulighed for, at en fordel _ikke_ nødvendigvis er
afgørende?
--
Med venlig hilsen
Peter Græbe
| |
Peter Weis (18-03-2004)
| Kommentar
Fra : Peter Weis |
Dato : 18-03-04 22:46 |
|
"Peter Græbe" <graebe_fjern@webspeed.dk> wrote:
> Det åbner vel også mulighed for, at en fordel _ikke_ nødvendigvis er
> afgørende?
Hvis der er tilfældighed involveret, ja.
mvh
Peter
| |
Peter Græbe (18-03-2004)
| Kommentar
Fra : Peter Græbe |
Dato : 18-03-04 23:46 |
|
Peter Weis skrev:
> Hvis der er tilfældighed involveret, ja.
Er det skak eller noget andet, du tænker på?
--
Med venlig hilsen
Peter Græbe
| |
Peter Weis (19-03-2004)
| Kommentar
Fra : Peter Weis |
Dato : 19-03-04 13:02 |
|
"Peter Græbe" wrote:
> Peter Weis skrev:
>
> > Hvis der er tilfældighed involveret, ja.
>
> Er det skak eller noget andet, du tænker på?
Næh, egentlig ikke.
Skak er i princippet fuldt gennemskueligt og helt uden tilfældighed.
Kompleksiteten er bare så overvældende, at en fuld analyse af spillet endnu
ikke har fundet sted. Det betyder at visse valg i spillet kan have karakter
af tilfældighed, da de ikke er fuldt gennemskuelige i praksis.
Tilfældighed er fx terningkast.
mvh
Peter
| |
Torben Ægidius Mogen~ (19-03-2004)
| Kommentar
Fra : Torben Ægidius Mogen~ |
Dato : 19-03-04 09:29 |
|
Peter Græbe <graebe_fjern@webspeed.dk> writes:
> Torben Ægidius Mogensen skrev:
>
> > I et spil uden tilfældigheder er en hver fordel afgørende.
>
> Hvis vi ser bort fra udefrakommende fænomener, er skak uden
> tilfældigheder. Jeg kan sagtens forestille mig en stilling i skak, hvor
> enten hvid eller sort har en fordel, den være sig positionel eller
> materialemæssig, som ikke tilstrækkelig stor til at gennemtvinge
> gevinst.
> Fx visse slutspil med uligefarvede løbere.
>
> > Hvis udfaldet er
> > sejr til sort eller hvid, så er sejren sikker og fordelen dermed
> > afgørende.
>
> Det åbner vel også mulighed for, at en fordel _ikke_ nødvendigvis er
> afgørende?
Hvis spillet med garanti ender i remis, så har ingen af spillerne vel
en fordel?
Torben
| |
Kristian Damm Jensen (19-03-2004)
| Kommentar
Fra : Kristian Damm Jensen |
Dato : 19-03-04 10:44 |
|
Torben Ægidius Mogensen wrote:
> Peter Græbe <graebe_fjern@webspeed.dk> writes:
>
<snip>
>> Det åbner vel også mulighed for, at en fordel _ikke_ nødvendigvis er
>> afgørende?
>
> Hvis spillet med garanti ender i remis, så har ingen af spillerne vel
> en fordel?
Det er en strid om ord.
Hvis man i en given stilling i skak har en springer mere end modstanderen
vil man tale om at man har en materiel fordel. Den vil i mange tilfælde
være så stor, at man på baggrund af denne fordel bør vinde partiet, den er
altså afgørende.
Men hvis de eneste brikker på brætter er K+S og K, så kan man ikke vinde,
og så er der ikke afgørende fordel.
--
Kristian Damm Jensen damm (at) ofir (dot) dk
There's a difference between a philosophy and a bumper sticker --
Charles M. Schulz
| |
Henning Makholm (19-03-2004)
| Kommentar
Fra : Henning Makholm |
Dato : 19-03-04 16:43 |
|
Scripsit "Kristian Damm Jensen" <REdammMOVE@ofir.dk>
> Hvis man i en given stilling i skak har en springer mere end modstanderen
> vil man tale om at man har en materiel fordel. Den vil i mange tilfælde
> være så stor, at man på baggrund af denne fordel bør vinde partiet, den er
> altså afgørende.
Jo, men det forudsætter jo at spillerne er fejlbarlige. Deltråden her
handler så vidt jeg kan se om matematisk optimale strategier - og der
er der ikke nogen mellemvej mellem "ingen fordel" (ændringen har ingen
indflydelse på hvilket resultat to optimale spillere opnår) og
"afgørende fordel" (ændringen giver den ene spiller mulighed for at nå
remis i stedet for at tabe, eller for at vinde i stedet for ikke at
gøre det).
--
Henning Makholm "Logic is a system for talking about
propositions that can be true or false, or at least enjoy
properties that are generalized versions of truth and falsehood."
| |
Kristian Damm Jensen (20-03-2004)
| Kommentar
Fra : Kristian Damm Jensen |
Dato : 20-03-04 23:05 |
|
Henning Makholm wrote:
> Scripsit "Kristian Damm Jensen" <REdammMOVE@ofir.dk>
>
>> Hvis man i en given stilling i skak har en springer mere end
>> modstanderen vil man tale om at man har en materiel fordel. Den vil
>> i mange tilfælde være så stor, at man på baggrund af denne fordel
>> bør vinde partiet, den er altså afgørende.
>
> Jo, men det forudsætter jo at spillerne er fejlbarlige.
Nej. I et parti mellem to spillere på stormesterniveua vil den spiller der
er bagud med en springer (og hvor der stadig er et rimeligt antal brikker
på brættet og en nogenlunde afklaret stilling) give op. Det skyldes ikke,
at han forventer at begå yderligere fejl, men at han forvneter at hans
modstander *ikke* gør det.
> Deltråden her
> handler så vidt jeg kan se om matematisk optimale strategier
Den handler om spilteori, men spilteori anvendt på et specifikt domæne,
nemlig skak.
> - og der
> er der ikke nogen mellemvej mellem "ingen fordel" (ændringen har ingen
> indflydelse på hvilket resultat to optimale spillere opnår) og
> "afgørende fordel" (ændringen giver den ene spiller mulighed for at nå
> remis i stedet for at tabe, eller for at vinde i stedet for ikke at
> gøre det).
Du ignorerer let og elegant, at jeg netop gør rede for at der er tale om
forskellig sprogbrug. Ordet fordel betyder noget forskelligt for
skakspillere og matematiske spilteoretikere. Så længe man ikke er opmærksom
på den forskel, og klar over hvilket betydning modparten tillægger order,
sålænge kan man ikke forvente at få en meningsfuld diskussion. Peter Græbe
bruger så vidt jeg kan se ordet i dets skakteoretiske betydning. (Hvor
alene det at være hvid og dermed trække først opfattes som en fordel, men
ikke en afgørende fordel.)
--
Kristian Damm Jensen damm (at) ofir (dot) dk
Science is like sex: sometimes something useful comes out, but that is
not the reason we are doing it. -- Richard Feynman
| |
Peter Græbe (21-03-2004)
| Kommentar
Fra : Peter Græbe |
Dato : 21-03-04 03:12 |
|
Kristian Damm Jensen skrev:
> sålænge kan man ikke forvente at få en meningsfuld diskussion. Peter Græbe
> bruger så vidt jeg kan se ordet i dets skakteoretiske betydning. (Hvor
> alene det at være hvid og dermed trække først opfattes som en fordel, men
> ikke en afgørende fordel.)
Netop.
Det minder mig om:
Afdøde stormester Jefim Bogoljubow, der var i besiddelse af en
fantastisk selvtillid, sagde: "Når jeg har Hvid, vinder jeg, fordi jeg
har Hvid. Når jeg har Sort, vinder jeg, fordi jeg er Bogoljubow."
--
Med venlig hilsen
Peter Græbe
| |
Henning Makholm (21-03-2004)
| Kommentar
Fra : Henning Makholm |
Dato : 21-03-04 16:25 |
|
Scripsit "Kristian Damm Jensen" <REdammMOVE@ofir.dk>
> Henning Makholm wrote:
> > Scripsit "Kristian Damm Jensen" <REdammMOVE@ofir.dk>
> >> Hvis man i en given stilling i skak har en springer mere end
> >> modstanderen vil man tale om at man har en materiel fordel. Den vil
> >> i mange tilfælde være så stor, at man på baggrund af denne fordel
> >> bør vinde partiet, den er altså afgørende.
> > Jo, men det forudsætter jo at spillerne er fejlbarlige.
> Nej. I et parti mellem to spillere på stormesterniveua
Vi taler ikke om "stormesterniveau". Vi taler om _ufejlbarlige_
spillere. Det er noget ganske andet.
--
Henning Makholm "Han råber og skriger, vakler ud på kørebanen og
ind på fortorvet igen, hæver knytnæven mod en bil,
hilser overmådigt venligt på en mor med barn, bryder ud
i sang og stiller sig til sidst op og pisser i en port."
| |
Kristian Damm Jensen (21-03-2004)
| Kommentar
Fra : Kristian Damm Jensen |
Dato : 21-03-04 17:09 |
|
Henning Makholm wrote:
> Scripsit "Kristian Damm Jensen" <REdammMOVE@ofir.dk>
>> Henning Makholm wrote:
>>> Scripsit "Kristian Damm Jensen" <REdammMOVE@ofir.dk>
>
>>>> Hvis man i en given stilling i skak har en springer mere end
>>>> modstanderen vil man tale om at man har en materiel fordel. Den vil
>>>> i mange tilfælde være så stor, at man på baggrund af denne fordel
>>>> bør vinde partiet, den er altså afgørende.
>
>>> Jo, men det forudsætter jo at spillerne er fejlbarlige.
>
>> Nej. I et parti mellem to spillere på stormesterniveua
>
> Vi taler ikke om "stormesterniveau". Vi taler om _ufejlbarlige_
> spillere. Det er noget ganske andet.
Du tager ikke stilling til mit argument. Hvis vi virkelig taler om
ufejlbarlige spillere, bliver mit argument blot endnu stærkere.
--
Kristian Damm Jensen damm (at) ofir (dot) dk
I knew, logically, that everything that had happened since I read that
silly ad had been impossible. So I chucked logic. Logic is a feeble
reed, friend. "Logic" proved that airplanes can't fly and that H-bombs
won't work and that stones don't fall out of the sky. Logic is a way of
saying that anything which didn't happen yesterday won't happen
tomorrow. -- Robert A. Heinlein
| |
Bertel Lund Hansen (18-03-2004)
| Kommentar
Fra : Bertel Lund Hansen |
Dato : 18-03-04 17:41 |
|
Peter Græbe skrev:
>Jeg burde have præciseret. Jeg havde kun skak i tankerne. Hvid har i
>skak en fordel, fordi han trækker først - men denne fordel er ikke
>afgørende.
Det er jo det man ikke ved fordi spillet ikke (i praksis) kan
analyseres til bunds.
--
Bertel
http://bertel.lundhansen.dk/ FIDUSO: http://fiduso.dk/
| |
Peter Græbe (18-03-2004)
| Kommentar
Fra : Peter Græbe |
Dato : 18-03-04 19:06 |
|
Bertel Lund Hansen skrev:
> Peter Græbe skrev:
>>Jeg burde have præciseret. Jeg havde kun skak i tankerne. Hvid har i
>>skak en fordel, fordi han trækker først - men denne fordel er ikke
>>afgørende.
> Det er jo det man ikke ved fordi spillet ikke (i praksis) kan
> analyseres til bunds.
Man er ifølge Kasparov [1] efterhånden nået så langt, at stort set alle
(anvendelige) åbninger er analyseret næsten til bunds til 15. træk. Det
er dog et stykke. (For en sjælden gangs skyld ærgrer computerteknologien
mig.)
[1] Fra Garry Kasparaov: On my great predecessors, Part I.
--
Med venlig hilsen
Peter Græbe
| |
Peter Makholm (18-03-2004)
| Kommentar
Fra : Peter Makholm |
Dato : 18-03-04 17:42 |
|
Peter Græbe <graebe_fjern@webspeed.dk> writes:
> Peter Makholm skrev:
>
> > Nej, der findes spil hvor den ene spiller har en fordel. Nim er et
> > sådan spil hvor den første spiller har en garanteret vinder-strategi.
>
> Jeg burde have præciseret. Jeg havde kun skak i tankerne. Hvid har i
> skak en fordel, fordi han trækker først - men denne fordel er ikke
> afgørende.
Vides det?
Bertels påstand var netop at det ikke var kendt om den ene spille
havde en garanteret vinderstrategi. Jeg kan ikke se hvorfor to
optimalt spillende spillere burde ende i remis, og jeg kan heller ikke
se en grund til at det netop skulle være hvid der skulle have en
eventuel garanteret vinderstrategi.
Det kan meget vel være at hvid har en empirisk målt meget lille
fordel. Men jeg kan ikke forestille mig at denne fordel er andet end
empiri, baseret på at skak er for kompliceret til at vi kan udtale og
særlig meget om optimale strategier.
--
Peter Makholm | Emacs is the only modern general-purpose
peter@makholm.net | operating system that doesn't multitask
http://hacking.dk |
| |
Peter Græbe (18-03-2004)
| Kommentar
Fra : Peter Græbe |
Dato : 18-03-04 19:15 |
|
Peter Makholm skrev:
> Peter Græbe <graebe_fjern@webspeed.dk> writes:
>> Jeg burde have præciseret. Jeg havde kun skak i tankerne. Hvid har i
>> skak en fordel, fordi han trækker først - men denne fordel er ikke
>> afgørende.
> Vides det?
Ikke i en grad så det er matematisk tilfredsstillende, eller hvordan det
nu skal formuleres. Det er ikke bevist, det er empirisk vist.
> Bertels påstand var netop at det ikke var kendt om den ene spille
> havde en garanteret vinderstrategi. Jeg kan ikke se hvorfor to
> optimalt spillende spillere burde ende i remis, og jeg kan heller ikke
> se en grund til at det netop skulle være hvid der skulle have en
> eventuel garanteret vinderstrategi.
>
> Det kan meget vel være at hvid har en empirisk målt meget lille
> fordel. Men jeg kan ikke forestille mig at denne fordel er andet end
> empiri, baseret på at skak er for kompliceret til at vi kan udtale og
> særlig meget om optimale strategier.
Jeg har ikke postuleret, at hvid har en garanteret vinderstrategi. Jeg
har nævnt, at hvid ved at være den første til at trække har en fordel,
der ikke er afgørende. Så uvidenskabeligt det end måtte lyde, kan hvid
bl.a. have en psykologisk fordel.
--
Med venlig hilsen
Peter Græbe
| |
Bertel Lund Hansen (18-03-2004)
| Kommentar
Fra : Bertel Lund Hansen |
Dato : 18-03-04 19:36 |
|
Peter Græbe skrev:
>Jeg har nævnt, at hvid ved at være den første til at trække har en fordel,
>der ikke er afgørende.
Du har ikke nævnt det, du har hævdet det.
--
Bertel
http://bertel.lundhansen.dk/ FIDUSO: http://fiduso.dk/
| |
Peter Græbe (18-03-2004)
| Kommentar
Fra : Peter Græbe |
Dato : 18-03-04 19:48 |
|
Bertel Lund Hansen skrev:
> Du har ikke nævnt det, du har hævdet det.
Bevar mig vel. Så har jeg hævdet det. Påstået det. Postuleret det.
Men hvordan kan jeg hævde det uden at nævne det?
--
Med venlig hilsen
Peter Græbe
| |
Jeppe Stig Nielsen (20-03-2004)
| Kommentar
Fra : Jeppe Stig Nielsen |
Dato : 20-03-04 00:40 |
|
Peter Græbe wrote:
>
> Jeg burde have præciseret. Jeg havde kun skak i tankerne. Hvid har i
> skak en fordel, fordi han trækker først - men denne fordel er ikke
> afgørende.
Det synes intuitionen at sige, men et matematisk bevis for det ligger
uden for rækkevidde.
--
Jeppe Stig Nielsen <URL: http://jeppesn.dk/>. «
"Je n'ai pas eu besoin de cette hypothèse (I had no need of that
hypothesis)" --- Laplace (1749-1827)
| |
Henning Makholm (20-03-2004)
| Kommentar
Fra : Henning Makholm |
Dato : 20-03-04 01:00 |
|
Scripsit Jeppe Stig Nielsen <mail@jeppesn.dk>
> Peter Græbe wrote:
> > Jeg burde have præciseret. Jeg havde kun skak i tankerne. Hvid har i
> > skak en fordel, fordi han trækker først - men denne fordel er ikke
> > afgørende.
> Det synes intuitionen at sige, men et matematisk bevis for det ligger
> uden for rækkevidde.
Hvis vi ser formelt på det, er det svært at overhovedet at tildele
mening til den intuitive opfattelse. Enten *er* det en fordel at have
det første træk - og i så fald vil hvid altid vinde ved fejlfrit spil,
og så er forskellen afgørende, eller også er det *ikke* en fordel, og
så vil sort altid kunne undgå at tabe.
--
Henning Makholm "Vi skal nok ikke begynde at undervise hinanden i
den store regnekunst her, men jeg vil foreslå, at vi fra
Kulturministeriets side sørger for at fremsende tallene og også
give en beskrivelse af, hvordan man læser tallene. Tak for i dag!"
| |
Jeppe Stig Nielsen (20-03-2004)
| Kommentar
Fra : Jeppe Stig Nielsen |
Dato : 20-03-04 01:13 |
|
Henning Makholm wrote:
>
> > > Jeg burde have præciseret. Jeg havde kun skak i tankerne. Hvid har i
> > > skak en fordel, fordi han trækker først - men denne fordel er ikke
> > > afgørende.
>
> > Det synes intuitionen at sige, men et matematisk bevis for det ligger
> > uden for rækkevidde.
>
> Hvis vi ser formelt på det, er det svært at overhovedet at tildele
> mening til den intuitive opfattelse. Enten *er* det en fordel at have
> det første træk - og i så fald vil hvid altid vinde ved fejlfrit spil,
> og så er forskellen afgørende, eller også er det *ikke* en fordel, og
> så vil sort altid kunne undgå at tabe.
Ja, det er en mere rigtig forklaring.
»Små« fordele eksisterer ikke i denne sammenhæng.
--
Jeppe Stig Nielsen <URL: http://jeppesn.dk/>. «
"Je n'ai pas eu besoin de cette hypothèse (I had no need of that
hypothesis)" --- Laplace (1749-1827)
| |
Kristian Damm Jensen (21-03-2004)
| Kommentar
Fra : Kristian Damm Jensen |
Dato : 21-03-04 21:12 |
|
Henning Makholm wrote:
> Scripsit Jeppe Stig Nielsen <mail@jeppesn.dk>
>> Peter Græbe wrote:
>
>>> Jeg burde have præciseret. Jeg havde kun skak i tankerne. Hvid har i
>>> skak en fordel, fordi han trækker først - men denne fordel er ikke
>>> afgørende.
>
>> Det synes intuitionen at sige, men et matematisk bevis for det ligger
>> uden for rækkevidde.
>
> Hvis vi ser formelt på det, er det svært at overhovedet at tildele
> mening til den intuitive opfattelse. Enten *er* det en fordel at have
> det første træk - og i så fald vil hvid altid vinde ved fejlfrit spil,
> og så er forskellen afgørende, eller også er det *ikke* en fordel, og
> så vil sort altid kunne undgå at tabe.
Du forudsætter a priori at en fordel altid vil føre til gevinst, men det er
ikke givet i min ordbog. (Som ikke er belastet af et indgående kendskab til
spilteori.)
Lad os tage en analogi. Vi løber om kap. Den der kommer i mål med mere end
10 sekunders forspring har vundet. Lykkes det ikke for nogen af parterne er
der tale om uafgjort. Du får 5 sekunders forspring. Det er hvad jeg kalder
en fordel! Men hvis vi løber lige godt er det ikke en fordel, der giver
noget forskel på slutresultatet.
--
Kristian Damm Jensen damm (at) ofir (dot) dk
The only substitute for good manners is quick reflexes.
| |
Henning Makholm (21-03-2004)
| Kommentar
Fra : Henning Makholm |
Dato : 21-03-04 21:34 |
|
Scripsit "Kristian Damm Jensen" <REdammMOVE@ofir.dk>
> Henning Makholm wrote:
> > Hvis vi ser formelt på det, er det svært at overhovedet at tildele
> > mening til den intuitive opfattelse. Enten *er* det en fordel at have
> > det første træk - og i så fald vil hvid altid vinde ved fejlfrit spil,
> > og så er forskellen afgørende, eller også er det *ikke* en fordel, og
> > så vil sort altid kunne undgå at tabe.
> Du forudsætter a priori at en fordel altid vil føre til gevinst, men det er
> ikke givet i min ordbog. (Som ikke er belastet af et indgående kendskab til
> spilteori.)
Nej, jeg forudsætter blot at en fordel vil føre til et ændret resultat
(ved optimalt spil). Når vi betragter virkningen af at hvid trækker
først, er denne forskel den *eneste* forskel mellem spillerne, og hvis
vi derfor antager at den gør en fordel i sidste ende, må det være
fordi spillet ikke ender i remis. Så hvis forskellen er en *fordel*
for hvid, må det være fordi hvid vinder.
> Lad os tage en analogi. Vi løber om kap.
Et kapløb er en temmelig analog foreteelse, som ikke passer særligt
godt som analogi til en formel behandling af skak.
--
Henning Makholm "Nett hier.
Aber waren Sie schon mal in Baden-Württemberg?"
| |
Kristian Damm Jensen (22-03-2004)
| Kommentar
Fra : Kristian Damm Jensen |
Dato : 22-03-04 08:53 |
|
Henning Makholm wrote:
> Scripsit "Kristian Damm Jensen" <REdammMOVE@ofir.dk>
<snip>
>> Lad os tage en analogi. Vi løber om kap.
>
> Et kapløb er en temmelig analog foreteelse, som ikke passer særligt
> godt som analogi til en formel behandling af skak.
Som du kan regne ud er jeg uenig. Formålet med analogien er at få dig til
at forstå, hvorfor jeg mener at din definition af ordet "fordel" er for
snæver i en generel sammenhæng. At det giver god mening i en fagspecifik
sammenhæng, in casu spilteori, at benytte vil jeg ikke bestride. Men hvis
man ikke kan skelne mellem de to betydninger af ordet, så render man sig
staver i livet, når man forsøger at diskuttere med personer som ikke kender
(eller i ekstreme tilfælde anerkender) den fagspecifikke betydning af
ordet.
--
Kristian Damm Jensen damm (at) ofir (dot) dk
'When I use a word,' said Humpty Dumpty, 'it means what I choose it to
mean.'
| |
Henning Makholm (22-03-2004)
| Kommentar
Fra : Henning Makholm |
Dato : 22-03-04 13:46 |
|
Scripsit "Kristian Damm Jensen" <REdammMOVE@ofir.dk>
> Som du kan regne ud er jeg uenig. Formålet med analogien er at få dig til
> at forstå, hvorfor jeg mener at din definition af ordet "fordel" er for
> snæver i en generel sammenhæng.
Jeg anvender ordet "fordel" i den eneste betydning der er meningsfuld
sammen med en forudsætning om optimalt spil. Denne forudsætning har
været en del af tråden lige sinde Peter Græbes første indlæg.
Jeg kan kun beklage at du nægter at indse dette.
> Men hvis man ikke kan skelne mellem de to betydninger af ordet,
Jeg skelner fint - men den betydning du insisterer på at slæbe ind i
debatten hele tiden er irrelevant i konteksten.
--
Henning Makholm "Hele toget raslede imens Sjælland fór forbi."
| |
Jeppe Stig Nielsen (20-03-2004)
| Kommentar
Fra : Jeppe Stig Nielsen |
Dato : 20-03-04 00:38 |
|
Bertel Lund Hansen wrote:
>
> >Hvis man kunne beregne alle mulighederne til ende, burde man vel kunne
> >lave et program der aldrig ville tabe.
>
> Nej. Der findes spil hvor det er givet hvem der vinder hvis begge
> spiller optimalt. Måske er skak et sådant spil, men det vides
> vist ikke.
Jo, fordi skak er et endeligt spil uden tilfældigheder, er udfaldet
givet på forhånd *hvis* begge spillere spiller optimalt. Det er ikke så
svært at bevise.
Det eneste der er spørgsmålet, er om udfaldet er gevinst til hvid, remis
eller gevinst til sort når (og hver gang) de to perfekte spillere mødes.
Det får vi nok aldrig bevist.
Men jeg holder på remis ...
--
Jeppe Stig Nielsen <URL: http://jeppesn.dk/>. «
"Je n'ai pas eu besoin de cette hypothèse (I had no need of that
hypothesis)" --- Laplace (1749-1827)
| |
Ole Andersen (20-03-2004)
| Kommentar
Fra : Ole Andersen |
Dato : 20-03-04 08:19 |
|
Jeppe Stig Nielsen wrote:
> Det eneste der er spørgsmålet, er om udfaldet er gevinst til hvid, remis
> eller gevinst til sort når (og hver gang) de to perfekte spillere mødes.
> Det får vi nok aldrig bevist.
Er det ikke blot et spørgsmål om computerkraft?
--
Ole Andersen, Copenhagen, DK * http://palnatoke.org *
No man has a natural right to commit aggression on the natural rights
of another; and this is all from which the laws ought to restrain him.
- Thomas Jefferson
| |
Bertel Lund Hansen (20-03-2004)
| Kommentar
Fra : Bertel Lund Hansen |
Dato : 20-03-04 08:35 |
|
Ole Andersen skrev:
>Er det ikke blot et spørgsmål om computerkraft?
Det kan man jo sige om mange tunge beregninger, men hvis deres
hastighed skal forbedres med en astronomisk faktor, er det et
lidt tomt udsagn.
Henning Makholm angav en øvre grænse og skrev: det er et tal med
27002 cifre.
Du kan jo regne på hvor meget vi skal speede vores nuværende
somputere op før det kan gennemregnes på 100 år.
--
Bertel
http://bertel.lundhansen.dk/ FIDUSO: http://fiduso.dk/
| |
Ole Andersen (20-03-2004)
| Kommentar
Fra : Ole Andersen |
Dato : 20-03-04 09:22 |
|
Bertel Lund Hansen wrote:
> Du kan jo regne på hvor meget vi skal speede vores nuværende
> somputere op før det kan gennemregnes på 100 år.
Nej, det kan jeg desværre ikke med min nuværende computer. 
--
Ole Andersen, Copenhagen, DK * http://palnatoke.org *
Thesis #26: Public Relations does not relate to the public. Companies
are deeply afraid of their markets. - Cluetrain Manifesto
| |
Henning Makholm (21-03-2004)
| Kommentar
Fra : Henning Makholm |
Dato : 21-03-04 16:48 |
|
Scripsit Bertel Lund Hansen <nospamius@lundhansen.dk>
> Henning Makholm angav en øvre grænse og skrev: det er et tal med
> 27002 cifre.
> Du kan jo regne på hvor meget vi skal speede vores nuværende
> somputere op før det kan gennemregnes på 100 år.
Bemærk at min grænse var *øvre*. Det virkelige antal mulige partier er
selvfølgelig betydelig mindre.
Her er en lidt løs nedre grænse: Hvis de to spillere samarbejder om
at trække partiet så langt ud som overhovedet muligt, må det ikke
desto mindre være muligt i hvert dobbelttræk for *enten* sort eller
hvid at vælge mellem to mulige træk uden at miste muligheden for at
fortsætte spillet til den bitre ende. Det giver mindst 2^6300
forskellige partier, et tal med 1897 cifre.
Til sammenligning: Hvis vi tætpakker hele det synlige univers med
bittesmå supercomputere der måler en plancklængde på hver led og kan
afprøve et skakparti per plancktid, og lader dem regne lige fra big
bang til idag, vil antallet af partier de har prøvet endnu, være et
tal med kun knap 250 cifre ...
--
Henning Makholm "Den nyttige hjemmedatamat er og forbliver en myte.
Generelt kan der ikke peges på databehandlingsopgaver af
en sådan størrelsesorden og af en karaktér, som berettiger
forestillingerne om den nye hjemme- og husholdningsteknologi."
| |
armor (09-04-2004)
| Kommentar
Fra : armor |
Dato : 09-04-04 08:36 |
|
"Jeppe Stig Nielsen" <mail@jeppesn.dk> skrev i en meddelelse
news:405B8475.F2639412@jeppesn.dk...
> Bertel Lund Hansen wrote:
> >
> > >Hvis man kunne beregne alle mulighederne til ende, burde man vel kunne
> > >lave et program der aldrig ville tabe.
> >
> > Nej. Der findes spil hvor det er givet hvem der vinder hvis begge
> > spiller optimalt. Måske er skak et sådant spil, men det vides
> > vist ikke.
>
> Jo, fordi skak er et endeligt spil uden tilfældigheder, er udfaldet
> givet på forhånd *hvis* begge spillere spiller optimalt. Det er ikke så
> svært at bevise.
>
> Det eneste der er spørgsmålet, er om udfaldet er gevinst til hvid, remis
> eller gevinst til sort når (og hver gang) de to perfekte spillere mødes.
> Det får vi nok aldrig bevist.
>
Udfaldet af et spil med to perfekte spillere vil altid ende i remis da den
spiller der først opdager modspilleren har en fordel vil kæmpe for remis og
det tidligt i et spil altid vil være muligt at opnå dette. Vi taler her om
at ingen af spillerne kan fejle og det derfor er taktik/kombinationsteri det
handler om. Ingen af spillerne vil miste brikker da man ved modspilleren er
lige så stærk som en selv. Den eneste grund til at miste brikker er for at
opnå en bedre stilling en modstanderen men det er usandsynligt at dette vil
ske da de er lige stærke.
rAnders.
| |
Jeppe Stig Nielsen (09-04-2004)
| Kommentar
Fra : Jeppe Stig Nielsen |
Dato : 09-04-04 09:52 |
|
armor wrote:
>
> Udfaldet af et spil med to perfekte spillere vil altid ende i remis da den
> spiller der først opdager modspilleren har en fordel vil kæmpe for remis og
> det tidligt i et spil altid vil være muligt at opnå dette.
Jeg tror du har ret, men hverken du eller jeg kan vide det da vi ikke
har overskuet alle kombinationer af stillinger.
Perfekte spillere »opdager« ikke »modspilleren har en fordel«. Fordi
de er perfekte, har de hele tiden kunnet se at det ville ende i remis,
og at der derfor ikke var nogen der havde en »fordel«.
--
Jeppe Stig Nielsen <URL: http://jeppesn.dk/>. «
"Je n'ai pas eu besoin de cette hypothèse (I had no need of that
hypothesis)" --- Laplace (1749-1827)
| |
Henning Makholm (18-03-2004)
| Kommentar
Fra : Henning Makholm |
Dato : 18-03-04 22:06 |
|
Scripsit "Pongo" <Pongos.email@ddress>
> Henning Makholm wrote:
> >> Benytter man også TSP-algoritmer i skak-programmer ?
> >> Det forekommer mig, at der må være en del ligheder.
> > Øhm, kan du ikke lige forklare dig lidt nøjere.
> Jeg tænkte mest på, at man vel også er nødt til at gennemregne alle
> mulige træk-kombinationer i et skakprogram, hvis man vil sikre at man
> laver det bedst mulige træk.
Det er der ingen der har bevist (og antagelsen forekommer mig også ret
tvivlsomt).
> Jeg forstillede mig, at man kunne benytte nogle af de samme trick,
> selvom det ikke var afstande man ønskede at beregne.
Jeg tror ikke der er meget andet end den generelle ide (som kan
udtrykkes i ganske få ord) der kan genbruges.
> Hvis man kunne beregne alle mulighederne til ende, burde man vel kunne
> lave et program der aldrig ville tabe.
Måske, se den efterfølgende diskussion om hvordan optimale strategier
opfører sig.
> Jeg læste engang at der findes et endeligt antal mulige skakpartier.
Javist. Det kan man let udlede af reglen af at partiet automatisk er
remis hvis der går 50 træk uden at en brik bliver slået eller en bonde
flytter sig. Derfor kan et parti maksimalt være 50*(30+16*6)=6300
(dobbelt)træk langt, og ingen spiller kan nogensinde have mere end 139
forskellige træk at vælge imellem på en gang.
Derfor kan der ikke være mere end 139^(2*6300) forskellige
skakpartier; det er et tal med 27002 cifre. Det virkelige antal er en
hel del lavere end som så, fordi jeg har benyttet temmelig grove
tilnærmelser.
> Antallet stod faktisk også opgivet, men jeg har vanskeligt ved at se
> hvordan man har fundet frem til tallet.
Jeg finder det ikke troværdigt at nogen skulle have beregnet det
*eksakte* antal forskellige mulige skakpartier.
[*] Forklaring på mine tilnærmelser. I løbet af et parti kan
50-træks-tælleren nulstilles 30 gange ved at en brik bliver slået
(de to konger er immune), og 6 gange for hver af de 16 bønder.
139 er summen af:
8 bønder har højst 4 mulige træk ad gangen hver: 32
2 tårne har i bedste fald 14 mulige træk hver: 28
2 løbere har i bedste fald 13 mulige træk hver: 26
2 springere og kongen har i bedste fald 8 m.t.h: 24
Dronningen har i bedste fald 14+13 mulige træk: 27
Lang og kort rokade: 2
--
Henning Makholm "What a hideous colour khaki is."
| |
Martin Moller Peders~ (20-03-2004)
| Kommentar
Fra : Martin Moller Peders~ |
Dato : 20-03-04 09:37 |
|
In <87hdwlhnlg.fsf@kreon.lan.henning.makholm.net> Henning Makholm <henning@makholm.net> writes:
>ingen spiller kan nogensinde have mere end 139
>forskellige træk at vælge imellem på en gang.
> 139 er summen af:
> 8 bønder har højst 4 mulige træk ad gangen hver: 32
Forkert. En bonde kan forvandles til fire forskellige brikker.
/Martin
| |
Martin Moller Peders~ (20-03-2004)
| Kommentar
Fra : Martin Moller Peders~ |
Dato : 20-03-04 10:55 |
|
In <c3gvqt$cjd$1@news.net.uni-c.dk> Martin Moller Pedersen <tusk@daimi.au.dk> writes:
>In <87hdwlhnlg.fsf@kreon.lan.henning.makholm.net> Henning Makholm <henning@makholm.net> writes:
>>ingen spiller kan nogensinde have mere end 139
>>forskellige træk at vælge imellem på en gang.
>> 139 er summen af:
>> 8 bønder har højst 4 mulige træk ad gangen hver: 32
>Forkert. En bonde kan forvandles til fire forskellige brikker.
Plus at man kan have flere dronnninger af samme farve, saa de
139 er alt for lavt sat.
Mvh
Martin
| |
Henning Makholm (21-03-2004)
| Kommentar
Fra : Henning Makholm |
Dato : 21-03-04 16:32 |
|
Scripsit Martin Moller Pedersen <tusk@daimi.au.dk>
> Plus at man kan have flere dronnninger af samme farve, saa de
> 139 er alt for lavt sat.
OK. For at være sikker må vi så hellere sige: Ingen spiller har mere
end 16 brikker, og ingen brik kan trække på mere end 27 måder ad
gangen. Derfor har hver spiller højst 432 trækmuligheder.
Det giver en øvre grænse på 432^(6300*2), som har 33208 cifre.
Bedre?
--
Henning Makholm "*Se*!! Nu hælder den vand ud
af ørerne *igen*!! *Et mirakel*!!!"
| |
Jens Olsen (22-03-2004)
| Kommentar
Fra : Jens Olsen |
Dato : 22-03-04 12:16 |
|
"Pongo" <Pongos.email@ddress> wrote in message news:<4058a764$0$177$edfadb0f@dtext01.news.tele.dk>...
> Bare lige et lille afledt spørgsmål:
> Benytter man også TSP-algoritmer i skak-programmer ?
> Det forekommer mig, at der må være en del ligheder.
Engang for mange år siden, da jeg lærte om den slags ting, var den
traditionelle løsning ved et spil hvor modstanderne veksler til at
foretage et træk, at anvende en A* algoritme med alfa-beta afskæring.
En sådan løsning bygger jo naturligvis på den forudsætning at
modstanderen benytter samme evalueringsfunktion som programmet selv.
Iøvrigt kan man vel sige, at brugen af evalueringsfunktionen kun er
nødvendiggjort af umuligheden af at foretage et komplet gennemløb af
søgetræet. Eller omvendt måske, at med en tilstrækkeligt god
evalueringsfunktion er intet (eller kun et meget lille søgetræ)
nødvendigt.
Evalueringsfunktionen indkapsler altså det man kunne kalde forståelsen
for spillet eller erfaringen.
Mennesker spiller ved at have en god evalueringsfunktion og et lille
søgetræ, da mennesker er istand til at se ligheder mellem stillinger
på et mere abstrakt plan. Maskiner er (for tiden) nødt til at forlade
sig på at gå meget dybt i søgetræet.
Jens Olsen
| |
Henning Makholm (22-03-2004)
| Kommentar
Fra : Henning Makholm |
Dato : 22-03-04 13:50 |
|
Scripsit jenspolsen@hotmail.com (Jens Olsen)
> Engang for mange år siden, da jeg lærte om den slags ting, var den
> traditionelle løsning ved et spil hvor modstanderne veksler til at
> foretage et træk, at anvende en A* algoritme med alfa-beta afskæring.
> En sådan løsning bygger jo naturligvis på den forudsætning at
> modstanderen benytter samme evalueringsfunktion som programmet selv.
Nej - den er bare pessimistisk med hensyn til hvad modspilleren
foretager sig. (Og så antager den i øvrigt at evalueringsfunktionen
"virker", dvs at det ikke kan være en ulempe at havne i en stillig man
opfatter som bedre end det man forventede modstanderen ville gøre).
> Iøvrigt kan man vel sige, at brugen af evalueringsfunktionen kun er
> nødvendiggjort af umuligheden af at foretage et komplet gennemløb af
> søgetræet.
Ja. Eller sagt på en anden måde: Hvis man havde ressourcer til at
gennemløbe hele søgetræet kunne man nøjes med en meget simpel
evalueringsfunktion:
0: Jeg har tabt
½: Jeg har hverken tabt eller vundet endnu
1: Jeg har vundet
--
Henning Makholm "Man vælger jo selv sine forbilleder."
| |
Jeppe Stig Nielsen (22-03-2004)
| Kommentar
Fra : Jeppe Stig Nielsen |
Dato : 22-03-04 14:35 |
|
Henning Makholm wrote:
>
> 0: Jeg har tabt
> ½: Jeg har hverken tabt eller vundet endnu
> 1: Jeg har vundet
»Endnu«? Skulle det ikke nærmere være
0: Jeg taber (medmindre min modstander er »idiot«)
½: Jeg sikrer mig remis, men kan ikke vinde (medmindre ... »idiot«)
1: Jeg vinder (helt sikkert)
--
Jeppe Stig Nielsen <URL: http://jeppesn.dk/>. «
"Je n'ai pas eu besoin de cette hypothèse (I had no need of that
hypothesis)" --- Laplace (1749-1827)
| |
Henning Makholm (22-03-2004)
| Kommentar
Fra : Henning Makholm |
Dato : 22-03-04 16:52 |
|
Scripsit Jeppe Stig Nielsen <mail@jeppesn.dk>
> Henning Makholm wrote:
> > 0: Jeg har tabt
> > ½: Jeg har hverken tabt eller vundet endnu
> > 1: Jeg har vundet
> »Endnu«? Skulle det ikke nærmere være
Ja, vurderingsfunktionen giver en værdi for en *stilling*. Min pointe
er at hvis man har kræfter til at søge hele træet igennem, behøver
vurderingsfunktionen ikke sige nogetsomhelst om stillinger hvor
spillet ikke er slut.
--
Henning Makholm "We can hope that this serious deficiency will be
remedied in the final version of BibTeX, 1.0, which is
expected to appear when the LaTeX 3.0 development is completed."
| |
Torben Ægidius Mogen~ (23-03-2004)
| Kommentar
Fra : Torben Ægidius Mogen~ |
Dato : 23-03-04 10:04 |
|
Henning Makholm <henning@makholm.net> writes:
> Scripsit Jeppe Stig Nielsen <mail@jeppesn.dk>
> > Henning Makholm wrote:
>
> > > 0: Jeg har tabt
> > > ½: Jeg har hverken tabt eller vundet endnu
> > > 1: Jeg har vundet
>
> > »Endnu«? Skulle det ikke nærmere være
>
> Ja, vurderingsfunktionen giver en værdi for en *stilling*. Min pointe
> er at hvis man har kræfter til at søge hele træet igennem, behøver
> vurderingsfunktionen ikke sige nogetsomhelst om stillinger hvor
> spillet ikke er slut.
I givet fald mangler du en værdi, der siger at spillet er sluttet
uafgjort.
Torben
| |
Henning Makholm (23-03-2004)
| Kommentar
Fra : Henning Makholm |
Dato : 23-03-04 13:06 |
|
Scripsit torbenm@diku.dk (Torben Ægidius Mogensen)
> Henning Makholm <henning@makholm.net> writes:
> > Scripsit Jeppe Stig Nielsen <mail@jeppesn.dk>
> > > Henning Makholm wrote:
> > > > 0: Jeg har tabt
> > > > ½: Jeg har hverken tabt eller vundet endnu
> > > > 1: Jeg har vundet
> > Min pointe er at hvis man har kræfter til at søge hele træet
> > igennem, behøver vurderingsfunktionen ikke sige nogetsomhelst om
> > stillinger hvor spillet ikke er slut.
> I givet fald mangler du en værdi, der siger at spillet er sluttet
> uafgjort.
Nej. I så fald har jeg hverken tabt eller vundet => ½.
--
Henning Makholm "We will discuss your youth another time."
| |
Kristian Damm Jensen (24-03-2004)
| Kommentar
Fra : Kristian Damm Jensen |
Dato : 24-03-04 09:36 |
|
Henning Makholm wrote:
> Scripsit torbenm@diku.dk (Torben Ægidius Mogensen)
>> Henning Makholm <henning@makholm.net> writes:
>>> Scripsit Jeppe Stig Nielsen <mail@jeppesn.dk>
>>>> Henning Makholm wrote:
>
>>>>> 0: Jeg har tabt
>>>>> ½: Jeg har hverken tabt eller vundet endnu
>>>>> 1: Jeg har vundet
>
>>> Min pointe er at hvis man har kræfter til at søge hele træet
>>> igennem, behøver vurderingsfunktionen ikke sige nogetsomhelst om
>>> stillinger hvor spillet ikke er slut.
>
>> I givet fald mangler du en værdi, der siger at spillet er sluttet
>> uafgjort.
>
> Nej. I så fald har jeg hverken tabt eller vundet => ½.
Forskellen ligger i "endnu". Din evalueringsfunktion skelner ikke mellem et
afsluttet og et uafsluttet spil.
--
Kristian Damm Jensen damm (at) ofir (dot) dk
The truth may be out there, but lies are inside your head. -- Terry
Pratchett
| |
Henning Makholm (24-03-2004)
| Kommentar
Fra : Henning Makholm |
Dato : 24-03-04 12:49 |
|
Scripsit "Kristian Damm Jensen" <REdammMOVE@ofir.dk>
> Henning Makholm wrote:
> > Scripsit torbenm@diku.dk (Torben Ægidius Mogensen)
> > Nej. I så fald har jeg hverken tabt eller vundet => ½.
> Forskellen ligger i "endnu". Din evalueringsfunktion skelner ikke mellem et
> afsluttet og et uafsluttet spil.
Det behøver den heller ikke. Husk at forudsætningen er at man kan
gennemsøge hele træet. I så fald er evelueringsfunktionens vurdering
af uafsluttede spil ganske ligegyldig.
--
Henning Makholm "... not one has been remembered from the time
when the author studied freshman physics. Quite the
contrary: he merely remembers that such and such is true, and to
explain it he invents a demonstration at the moment it is needed."
| |
Kasper Kristensen (17-03-2004)
| Kommentar
Fra : Kasper Kristensen |
Dato : 17-03-04 23:29 |
|
"Jakob" <s031822@student.dtu.dk> wrote in message
news:svhg50ht1j9etldffttk7tihctq06hdo3c@4ax.com...
> Hej NG
>
> Når man finder sådan en rute må man da approksimere en del, fordi man
> kan da ikke sammenligne alle ruter på, som der findes.
Det er faktisk en dansker, som har fundet ruten.
Se (hvor du kan se ruten på et kort):
http://www.math.princeton.edu/tsp/world/
Så vidt jeg kan se, så er der tale om en (god) approksimation og ikke et
globalt minimum.
Kasper
| |
Jakob (18-03-2004)
| Kommentar
Fra : Jakob |
Dato : 18-03-04 13:14 |
|
>Det er faktisk en dansker, som har fundet ruten.
>
>Se (hvor du kan se ruten på et kort):
> http://www.math.princeton.edu/tsp/world/
>
>Så vidt jeg kan se, så er der tale om en (god) approksimation og ikke et
>globalt minimum.
Ja, en god approksimation og intet andet. Den korteste rute kan jo
ikke blive kortere hele tiden, hvis man da ikke tager
kontinentialdriften med i betragtning.
Hvad menes der med "the current lowest bound", som der står på den
hjemmeside du linker til?
/Jakob
| |
Kasper Kristensen (18-03-2004)
| Kommentar
Fra : Kasper Kristensen |
Dato : 18-03-04 14:55 |
|
"Jakob" <s031822@student.dtu.dk> wrote in message
news:bd4j5093r1i9u0cblude7b40vsth5dj8kb@4ax.com...
>
> Hvad menes der med "the current lowest bound", som der står på den
> hjemmeside du linker til?
>
Der menes at alle ruter _mindst_ er af den angivne længde. Den korteste rute
kan således godt være længere end dette tal, men ikke kortere.
Kasper
| |
Allan Rasmussen (18-03-2004)
| Kommentar
Fra : Allan Rasmussen |
Dato : 18-03-04 10:57 |
|
Jakob wrote:
> Hej NG
>
> Læser her i Aktuel Videnskab, som er fra september-oktober 2003, at
> problemmet med sælgeren, der skal finde den korteste rute mellem 49
> byer blev beregnet i 1954. Den korteste rute mellem alle verdens byer,
> 1.904.711 byer, blev fundet her for nylig.
>
> Når man finder sådan en rute må man da approksimere en del, fordi man
> kan da ikke sammenligne alle ruter på, som der findes.
>
> Når man laver sådan en approksimation, kan der så muligvis ikke gå
> bedre løsninger tabt?
>
Jeg er ikke sikker på om de har fundet en rute der følger vejnettet,
søruter osv. eller om det er i fugleflugt, men jeg ved at deres næste
projekt er at udregne en TSP tour for alle kendte stjerner. Ligesom
vejnettet og anden infrastruktur ændrer sig, så bevæger de fleste
stjerner sig også, så TSP touren er bare et udtryk for den øjeblikkelige
situation i udregningsøjeblikket.
Hvis man har lavet approksimation ligger det i ordet at det ikke er
eksakt, hvorfor bedre løsninger godt kan gå tabt.
MVH
Allan
| |
Ukendt (18-03-2004)
| Kommentar
Fra : Ukendt |
Dato : 18-03-04 16:11 |
|
"Allan Rasmussen" <gaetenmail@idanmark.dk> wrote in message
news:c3brhe$2rdf$1@gnd.k-net.dk...
>
> Jeg er ikke sikker på om de har fundet en rute der følger vejnettet,
> søruter osv. eller om det er i fugleflugt
Fugleflugt ifølge artiklen ("Great Circle distance").
| |
Jeppe Stig Nielsen (20-03-2004)
| Kommentar
Fra : Jeppe Stig Nielsen |
Dato : 20-03-04 00:44 |
|
Uffe Kousgaard wrote:
>
> > Jeg er ikke sikker på om de har fundet en rute der følger vejnettet,
> > søruter osv. eller om det er i fugleflugt
>
> Fugleflugt ifølge artiklen ("Great Circle distance").
Ja, og »fuglen« ser bort fra et Jorden ikke er en kugle (Jordens
fladtrykthed og orografi).
--
Jeppe Stig Nielsen <URL: http://jeppesn.dk/>. «
"Je n'ai pas eu besoin de cette hypothèse (I had no need of that
hypothesis)" --- Laplace (1749-1827)
| |
Carsten Svaneborg (18-03-2004)
| Kommentar
Fra : Carsten Svaneborg |
Dato : 18-03-04 15:30 |
|
Jakob wrote:
> Den korteste rute mellem alle verdens byer,
> 1.904.711 byer, blev fundet her for nylig.
En sjov sidebemærkning. TSP problemet kan implementeres
ved at bruge en myretue.
http://www.cogs.susx.ac.uk/lab/nlp/gazdar/teach/atc/1999/web/johannf
tsp.html
Myrer sætter et feromon spor hvor de går. Dette aftager
med en vis rate. Myrer fortrækker at følge sporet hvis det
findes, og "reinforcer" derfor signalet ved at lægge deres
egne feromoner.
Har man myrer, der går mellem tue og en madkilde, langs flere
forskellige spor, så den det spor der er kortest benyttest
hyppigst og vil derfor have det stærkeste feromon signal.
De længrer router vil derfor på sigt forsvinde, fordi myrene
vælger sporet med det stærkeste signal.
På den måde kan TSP problemet opfattes som en emergent
løsning af en myretue. Hvor en myre skal besøge N byer
mellem tue og fødekilde.
Det interessante er at man kun behøver feromon styrken f(x,y)
og så en masse simple agenter (myrene), der laver en guided
random walk langs feromon gradienter.
--
Mvh. Carsten Svaneborg
http://www.softwarepatenter.dk
| |
Jens Olsen (22-03-2004)
| Kommentar
Fra : Jens Olsen |
Dato : 22-03-04 12:24 |
|
Carsten Svaneborg <zqex@sted.i.tyskland.de> wrote in message news:<acooi1-q55.ln1@dhcp024.mpipks-dresden.mpg.de>...
> En sjov sidebemærkning. TSP problemet kan implementeres
> ved at bruge en myretue.
Sjov og ret simpel tanke, tak for den. Det er da parallel distribueret
computing af første karat.
Jens Olsen
| |
Michael Vittrup (22-03-2004)
| Kommentar
Fra : Michael Vittrup |
Dato : 22-03-04 12:26 |
|
| |
Carsten Svaneborg (22-03-2004)
| Kommentar
Fra : Carsten Svaneborg |
Dato : 22-03-04 14:03 |
| | |
Jens Olsen (22-03-2004)
| Kommentar
Fra : Jens Olsen |
Dato : 22-03-04 15:16 |
|
Michael Vittrup <vittrup@ima.auc.dk> wrote in message news:<Pine.GSO.4.21.0403221225110.11403-100000@dumbo.servers.ima.auc.dk>...
> On 22 Mar 2004, Jens Olsen wrote:
>
> >Carsten Svaneborg <zqex@sted.i.tyskland.de> wrote in message news:<acooi1-q55.ln1@dhcp024.mpipks-dresden.mpg.de>...
> >> En sjov sidebemærkning. TSP problemet kan implementeres
> >> ved at bruge en myretue.
> >
> >Sjov og ret simpel tanke, tak for den. Det er da parallel distribueret
> >computing af første karat.
>
>
> Ehm .. hvordan skal det forståes, i praksis? Sender man X antal myrer
> afsted i forskellige retninger, for så at måle den korteste rute, eller
> hva'?
>
Nej, som det fremgår af Carstens Svaneborgs indlæg er det sjove jo
netop, at løsningen på det globale problem fremkommer ved uafhængige
individuelle agenters
lokale handlinger, uden at disse har nogen som helst ide om systemets
globale tilstand.
Jens Olsen
| |
|
|