---

hej alle

Alle der læser mit indlæg her, skal forstå mit ønske som sådan:

jeg søger et program til min windows vista computer, som kan udregne
sandsynligheder i forskellige spil.

noget lig som simulere af frits blaabjerg som nu er udgået i kan læse
om programmet her :


Værktøj hvor man ved eksperimenter kan finde sandsynligheden for en
lang række hændelser.

Mange af eksperimenterne findes også som spil, så man kan afprøve sine
resultater i praksis. Idéen med programmet er at nærme sig beregning
af sandsynlighed ad eksperimentel vej.

Specielt kan nævnes:

- Statistiske beregninger, regneark, grafik, strategi, ludomani,
kombinatorik.

- Eksperimenter med terninger, kort, lotto, klasselotteri (dansk og
tysk), lodsedler, tyveknægt, roulette, krukker, halveringstid, yatzy,
fødselsdag m.m.

- Nogle af spiltyperne: 3D-ludo, yatzy, begærlig, roulette, tyveknægt,
behændighed, legehus.

- Forskellige terningtyper (2 - 20 - sidet), farvede sider.

- Resultater kan overføres til regneark med mulighed for fremstilling
af grafer.

- Forskellige faktorer kan reguleres, så man selv kan bestemme, hvad
der skal optælles.

- Gevinsterne kan gemmes på diskette så arbejdet kan fortsættes
senere.

- Maskinerne holder øje med kassebeholdningen samt de forskellige
hitlister.

- Indeholder en lang række opgaver, der enkeltvis kan udskrives af
eleven efter behov.

- Opgavesættet findes i følgende formater:
Word6, Works 3 og WP6.1.

- Indlagt facitliste, hvoraf det fremgår, hvordan man kan udregne
sansynligheden teoretisk.

- Lærerdel til justering af forskellige faktorer. Bl.a. kan
facitlisten slås fra og holdninger og hitlister nulstilles.

på forhånd tak

MHV. pbc

---

On Wed, 30 Jul 2008 10:46:49 -0700 (PDT), pbc wrote:

> hej alle

Aha, så kan jeg osse være med

> Alle der læser mit indlæg her, skal forstå mit ønske som sådan:
>
> jeg søger et program til min windows vista computer, som kan udregne
> sandsynligheder i forskellige spil.

Min første indskydelse er anvendelse af fuzzy logic. Det var vældig moderne
for 10-20 år siden, men jeg synes ikke man hører så meget om det mere.
Hvorfor?
--
/ Mikkel

---

"Mikkel Mikkelsen" <mikkel@mikkelserver.invalid> wrote in message
news:1iwmiu350o2y3$.256z7c22fws3.dlg@40tude.net...
> On Wed, 30 Jul 2008 10:46:49 -0700 (PDT), pbc wrote:
>
>> hej alle
>
> Aha, så kan jeg osse være med
>
>> Alle der læser mit indlæg her, skal forstå mit ønske som sådan:
>>
>> jeg søger et program til min windows vista computer, som kan udregne
>> sandsynligheder i forskellige spil.
>
> Min første indskydelse er anvendelse af fuzzy logic. Det var vældig
> moderne
> for 10-20 år siden, men jeg synes ikke man hører så meget om det mere.
> Hvorfor?

Det har da ikke noget med det her at gøre.

---

On Thu, 31 Jul 2008 20:06:46 +0200, Edward Jensen wrote:

> "Mikkel Mikkelsen" <mikkel@mikkelserver.invalid> wrote in message
> news:1iwmiu350o2y3$.256z7c22fws3.dlg@40tude.net...
>> On Wed, 30 Jul 2008 10:46:49 -0700 (PDT), pbc wrote:
>>
>>> hej alle
>>
>> Aha, så kan jeg osse være med
>>
>>> Alle der læser mit indlæg her, skal forstå mit ønske som sådan:
>>>
>>> jeg søger et program til min windows vista computer, som kan udregne
>>> sandsynligheder i forskellige spil.
>>
>> Min første indskydelse er anvendelse af fuzzy logic. Det var vældig
>> moderne for 10-20 år siden, men jeg synes ikke man hører så meget
>> om det mere. Hvorfor?
>
> Det har da ikke noget med det her at gøre.

Okay, jeg trækker mig straks. Jeg kom bare til at tænke på den praktiske
anvendelse af fuzzy logic, brugt f.eks. i en elevator til at
sandsynlighedsberegne hvor der næste gang ville blive brug for den. Ud fra
en dataopsamling og statistisk beregning, kunne elevatoren "trænes" til at
være på pletten en ganske høj procentdel af tilfældene.

Jeg er dog ganske "uvidenskabelig" og skal/vil således ikke fremture
yderlige.
--
/ Mikkel

---

"Mikkel Mikkelsen" <mikkel@mikkelserver.invalid> wrote in message
news:aa23l9i9wfo7.1dpvuys2kjib7$.dlg@40tude.'net...
> On Thu, 31 Jul 2008 20:06:46 +0200, Edward Jensen wrote:
>
>> "Mikkel Mikkelsen" <mikkel@mikkelserver.invalid> wrote in message
>> news:1iwmiu350o2y3$.256z7c22fws3.dlg@40tude.net...
>>> On Wed, 30 Jul 2008 10:46:49 -0700 (PDT), pbc wrote:
>>>
>>>> hej alle
>>>
>>> Aha, så kan jeg osse være med
>>>
>>>> Alle der læser mit indlæg her, skal forstå mit ønske som sådan:
>>>>
>>>> jeg søger et program til min windows vista computer, som kan udregne
>>>> sandsynligheder i forskellige spil.
>>>
>>> Min første indskydelse er anvendelse af fuzzy logic. Det var vældig
>>> moderne for 10-20 år siden, men jeg synes ikke man hører så meget
>>> om det mere. Hvorfor?
>>
>> Det har da ikke noget med det her at gøre.
>
> Okay, jeg trækker mig straks. Jeg kom bare til at tænke på den praktiske
> anvendelse af fuzzy logic, brugt f.eks. i en elevator til at
> sandsynlighedsberegne hvor der næste gang ville blive brug for den. Ud fra
> en dataopsamling og statistisk beregning, kunne elevatoren "trænes" til at
> være på pletten en ganske høj procentdel af tilfældene.

Hvordan er fuzzy logic anvendelig her? Skal den ikke blot befinde sig dér,
hvor der er størst bayesiank sandsynlighed for, at den skal være?
Tænker du ikke på, hvordan fuzzy logic kan bruges i reguleringsteori f.eks.
til at styre elevatorens hastighed?

---

pbc wrote:
> hej alle
>
> Alle der læser mit indlæg her, skal forstå mit ønske som sådan:
>
> jeg søger et program til min windows vista computer, som kan udregne
> sandsynligheder i forskellige spil.
[...]

Torben Mogensen har lavet et programmeringssprog, som kan noget af det du har
brug for (muligvis det hele). Desværre har jeg aldrig selv brugt det, da mine
behov kan dækkes af den smule programmering jeg selv behersker (især nu hvor jeg
har fået styr på FreeBASIC), så jeg kan ikke hjælpe med det, men det vil Torben
sikkert meget gerne.

< http://www.diku.dk/~torbenm/Troll/ >

--
Peter Knutsen
sagatafl.org

---

Peter Knutsen <peter@sagatafl.invalid> writes:

> pbc wrote:
>> hej alle
>> Alle der læser mit indlæg her, skal forstå mit ønske som sådan:
>> jeg søger et program til min windows vista computer, som kan udregne
>> sandsynligheder i forskellige spil.
> [...]
>
> Torben Mogensen har lavet et programmeringssprog, som kan noget af det
> du har brug for (muligvis det hele). Desværre har jeg aldrig selv
> brugt det, da mine behov kan dækkes af den smule programmering jeg
> selv behersker (især nu hvor jeg har fået styr på FreeBASIC), så jeg
> kan ikke hjælpe med det, men det vil Torben sikkert meget gerne.
>
> < http://www.diku.dk/~torbenm/Troll/ >

Troll kan ganske rigtigt udregne sandsynligheder for forskellige
terningeslag -- både simple og komplicerede. Et mellemkompliceret
eksempel er at slå fire terninger og tage summen af de tre største:

sum largest 3 4d6

hvilket giver

Value % = % >=
3 : 0.0771604938272 100.0
4 : 0.308641975309 99.9228395062
5 : 0.771604938272 99.6141975309
6 : 1.62037037037 98.8425925926
7 : 2.93209876543 97.2222222222
8 : 4.78395061728 94.2901234568
9 : 7.02160493827 89.5061728395
10 : 9.41358024691 82.4845679012
11 : 11.4197530864 73.0709876543
12 : 12.8858024691 61.6512345679
13 : 13.2716049383 48.7654320988
14 : 12.3456790123 35.4938271605
15 : 10.1080246914 23.1481481481
16 : 7.25308641975 13.0401234568
17 : 3.99353626682 5.78703703704
18 : 1.79350077022 1.79350077022

Average = 12.2463300694 Spread = 2.85003819145 Mean deviation = 2.32031352794

Så sandsynligheden for at slå 16 eller mere er for eksempel lige over 13%.

Troll kan sagtens køre under Windows -- du skal blot først installere
programmerinsgsproget Moscow ML fra
http://www.itu.dk/people/sestoft/mosml.html, og du skal køre
programmet fra kommanodlinjen (der er ikke nogen grafisk grænseflade
til Troll). Jeg kører selv Troll fra et kommandolinjevindue i XEmacs,
når jeg bruger Windows.

Troll kan godt bruges til at beregne sandsynligheder for andet end
terninger, men den er ikke egnet til kortspil, da sandsynlighederne
afhænger af tidligere trukne kort. Det kan lade sig gøre, men det er
ikke så nemt, og det tager tid for Troll at beregne, fordi den skal
holde styr på mere.

Hvis du f.eks. vil kende sandsynligheden for N esser i fem kort, så
kan du skrive det som


function pick(cards,n) =
if n=0 then {}
else (
card := choose cards;
card @ call pick(cards drop card,n-1)
)

hand := call pick(1..52,5);
count 5 < hand


Funktionen tager n tilfældige kort fra en samling kort. hand er fem
tilfældigt trukne af 52. Hvis vi siger, at esserne er nummereret
1..4, så er antallet af esser lig med antallet af kort under 5.

Det vil dog tage en evighed at køre Troll på denne definition, da den
skal opremse alle muligheder for at trække fem kort, hvilket er ret
stort (2598960).

Jeg vil overveje at lave pick til en standardfunktion for at gøre den
slags beregninger hurtigere.

   Torben

---

torbenm@pc-003.diku.dk (Torben Ægidius Mogensen) writes:


> Hvis du f.eks. vil kende sandsynligheden for N esser i fem kort, så
> kan du skrive det som
>
>
> function pick(cards,n) =
> if n=0 then {}
> else (
> card := choose cards;
> card @ call pick(cards drop card,n-1)
> )
>
> hand := call pick(1..52,5);
> count 5 < hand

Rettelse: Der skulle stå "5 > hand".

> Det vil dog tage en evighed at køre Troll på denne definition, da den
> skal opremse alle muligheder for at trække fem kort, hvilket er ret
> stort (2598960).
>
> Jeg vil overveje at lave pick til en standardfunktion for at gøre den
> slags beregninger hurtigere.

Det har jeg så gjort, omend pick er blevet en infix operator.
Ovenstående definition kan nu skrives som

count 5 > ((1..52) pick 5)

og giver resultatet


Value % = % >=
0 : 65.8841998338 100.0
1 : 29.9473635608 34.1158001662
2 : 3.99298180811 4.16843660541
3 : 0.1736079047 0.175454797304
4 : 0.0018468926032 0.0018468926032

Average = 0.384615384615 Spread = 0.572000111966 Mean deviation = 0.506801537183


Der er altså lidt over 65% chance for, at du slet ikke får nogen esser,
og under 0.002% chance for, at du får fire esser.

   Torben

---

"Torben "Ægidius" Mogensen" <torbenm@pc-003.diku.dk> skrev i meddelelsen
news:7zabfyuvod.fsf@pc-003.diku.dk...
> torbenm@pc-003.diku.dk (Torben Ægidius Mogensen) writes:
>
>
>> Hvis du f.eks. vil kende sandsynligheden for N esser i fem kort, så
>> kan du skrive det som
>>
>>
>> function pick(cards,n) =
>> if n=0 then {}
>> else (
>> card := choose cards;
>> card @ call pick(cards drop card,n-1)
>> )
>>
>> hand := call pick(1..52,5);
>> count 5 < hand
>
> Rettelse: Der skulle stå "5 > hand".
>
>> Det vil dog tage en evighed at køre Troll på denne definition, da den
>> skal opremse alle muligheder for at trække fem kort, hvilket er ret
>> stort (2598960).
>>
>> Jeg vil overveje at lave pick til en standardfunktion for at gøre den
>> slags beregninger hurtigere.
>
> Det har jeg så gjort, omend pick er blevet en infix operator.
> Ovenstående definition kan nu skrives som
>
> count 5 > ((1..52) pick 5)
>
> og giver resultatet
>
>
> Value % = % >=
> 0 : 65.8841998338 100.0
> 1 : 29.9473635608 34.1158001662
> 2 : 3.99298180811 4.16843660541
> 3 : 0.1736079047 0.175454797304
> 4 : 0.0018468926032 0.0018468926032
>
> Average = 0.384615384615 Spread = 0.572000111966 Mean deviation =
> 0.506801537183
>
>
> Der er altså lidt over 65% chance for, at du slet ikke får nogen esser,
> og under 0.002% chance for, at du får fire esser.
>


Hvor lang tid tog den beregning af mere end 2598960 hands?

Mvh
Martin

---

Martin Larsen wrote:
> Hvor lang tid tog den beregning af mere end 2598960 hands?

Ja, det kunne være interessant at vide. Mit gæt er dog at det gik kodylt
hurtigt. Jeg lavede for noget tid siden et meget beregningstungt (kompileret)
program i FreeBASIC, og jeg blev meget imponeret over hvor hurtigt det gik. Et
programmeringssprog dedikeret til opgaven er fantastisk hurtigt, forestiller jeg
mig.

--
Peter Knutsen
sagatafl.org

---

---

"Martin Larsen" <mlarsen@post7.tele.dk> writes:

> "Torben "Ægidius" Mogensen" <torbenm@pc-003.diku.dk> skrev i

>> Ovenstående definition kan nu skrives som
>>
>> count 5 > ((1..52) pick 5)
>>
>> og giver resultatet
>>
>>
>> Value % = % >=
>> 0 : 65.8841998338 100.0
>> 1 : 29.9473635608 34.1158001662
>> 2 : 3.99298180811 4.16843660541
>> 3 : 0.1736079047 0.175454797304
>> 4 : 0.0018468926032 0.0018468926032
>>
>> Average = 0.384615384615 Spread = 0.572000111966 Mean deviation
>> = 0.506801537183
>>
>>
>> Der er altså lidt over 65% chance for, at du slet ikke får nogen esser,
>> og under 0.002% chance for, at du får fire esser.
>>
>
>
> Hvor lang tid tog den beregning af mere end 2598960 hands?

7 sekunder. Hertil skal siges, at Moscow ML bruger
bytekodefortolkning, så det er ikke den hurtigste implementering af
Standard ML.

   Torben

---

"Torben "Ægidius" Mogensen" <torbenm@pc-003.diku.dk> skrev i meddelelsen
news:7zwsj140gu.fsf@pc-003.diku.dk...
> "Martin Larsen" <mlarsen@post7.tele.dk> writes:
>
>> "Torben "Ægidius" Mogensen" <torbenm@pc-003.diku.dk> skrev i
>
>>> Ovenstående definition kan nu skrives som
>>>
>>> count 5 > ((1..52) pick 5)
>>>
>>> og giver resultatet
>>>
>>>
>>> Value % = % >=
>>> 0 : 65.8841998338 100.0
>>> 1 : 29.9473635608 34.1158001662
>>> 2 : 3.99298180811 4.16843660541
>>> 3 : 0.1736079047 0.175454797304
>>> 4 : 0.0018468926032 0.0018468926032
>>>
>>> Average = 0.384615384615 Spread = 0.572000111966 Mean deviation
>>> = 0.506801537183
>>>
>>>
>>> Der er altså lidt over 65% chance for, at du slet ikke får nogen esser,
>>> og under 0.002% chance for, at du får fire esser.
>>>
>>
>>
>> Hvor lang tid tog den beregning af mere end 2598960 hands?
>
> 7 sekunder. Hertil skal siges, at Moscow ML bruger
> bytekodefortolkning, så det er ikke den hurtigste implementering af
> Standard ML.

Ja, det er tæt på smerte- og livstidsgrænsen. Du skal nok ikke begynde at
undersøge en bridgehånd for meget, ((1..52) pick 13) er 635013559600 hænder


Mvh
Martin

---

---

Hej alle

Tak til alle for jeres indpot omkring mit spørgmål.

Jeg har kigget på troll og det ser interessant og godt ud.

Jeg håber selvfølgelig at der vil komme mange indlæg inu
da det er meget interessant at læse jeres forslag,

Jeg hvender tilbage når der kommer flere indlæg.

Tak for nu det var interessant

M.V.H.

pbc

---

pbc wrote:
> Hej alle
>
> Tak til alle for jeres indpot omkring mit spørgmål.
>
> Jeg har kigget på troll og det ser interessant og godt ud.
>
> Jeg håber selvfølgelig at der vil komme mange indlæg inu
> da det er meget interessant at læse jeres forslag,
>
> Jeg hvender tilbage når der kommer flere indlæg.
>
> Tak for nu det var interessant
>
> M.V.H.
>
> pbc

Er jeg den eneste der synes det indlæg ser ud som om det er blevet
google translated 3-4 gange før det landede på dansk, eller at man er en
forsøgsperson i en dobbeltblind turing test?

---

Martin Andersen wrote:
> Er jeg den eneste der synes det indlæg ser ud som om det er blevet
> google translated 3-4 gange før det landede på dansk, eller at man er
> en forsøgsperson i en dobbeltblind turing test?

Passer da også fint med sourcen:

9 19 ms 18 ms 21 ms ge1-3.cr1.taa.cph.ngdc.net [217.116.255.74]
10 19 ms 19 ms 20 ms vl924.ar0.taa.cph.ngdc.net [217.116.255.78]
11 21 ms 18 ms 18 ms fascom.cust.ngdc.net [217.116.238.137]
12 25 ms 19 ms 20 ms 83.221.154.134

I hvert fald ikke en fra denne side af jorden..

/Hauge

---

---

On 31 Jul., 22:07, "Hauge" <ha...@CUTsmart-tech.dk> wrote:
> Martin Andersen wrote:
> > Er jeg den eneste der synes det indlæg ser ud som om det er blevet
> > google translated 3-4 gange før det landede på dansk, eller at man er
> > en forsøgsperson i en dobbeltblind turing test?
>
> Passer da også fint med sourcen:
>
>   9    19 ms    18 ms    21 ms  ge1-3.cr1.taa.cph.ngdc.net [217.116.255.74]
>  10    19 ms    19 ms    20 ms  vl924.ar0.taa.cph.ngdc.net [217.116.255.78]
>  11    21 ms    18 ms    18 ms  fascom.cust.ngdc.net [217..116.238.137]
>  12    25 ms    19 ms    20 ms  83.221.154.134
>
> I hvert fald ikke en fra denne side af jorden..
>
> /Hauge

Hej

Hvad er det i skriver, jeg kan ikke forstå hvad det er, selv om jeg er
dansker.
Er det noget, som i mener jeg kan bruge, hvis i har forstået mit
spørgsmål, så
må i uddybe det i skriver.

MVH
PBC

---

On Thu, 31 Jul 2008 13:34:11 -0700 (PDT), pbc wrote:

> On 31 Jul., 22:07, "Hauge" <ha...@CUTsmart-tech.dk> wrote:
>> Martin Andersen wrote:
>>> Er jeg den eneste der synes det indlæg ser ud som om det er blevet
>>> google translated 3-4 gange før det landede på dansk, eller at man er
>>> en forsøgsperson i en dobbeltblind turing test?
>>
>> Passer da også fint med sourcen:
>>
>>   9    19 ms    18 ms    21 ms  ge1-3.cr1.taa.cph.ngdc.net [217.116.255.74]
>>  10    19 ms    19 ms    20 ms  vl924.ar0.taa.cph.ngdc.net [217.116.255.78]
>>  11    21 ms    18 ms    18 ms  fascom.cust.ngdc.net [217.116.238.137]
>>  12    25 ms    19 ms    20 ms  83.221.154.134
>>
>> I hvert fald ikke en fra denne side af jorden..
>>
>> /Hauge
>
> Hej
>
> Hvad er det i skriver, jeg kan ikke forstå hvad det er, selv om jeg er
> dansker.
> Er det noget, som i mener jeg kan bruge, hvis i har forstået mit
> spørgsmål, så
> må i uddybe det i skriver.

De gør sig desværre bare lystige over, at du ikke staver og formulerer dig
på perfekt akedemikersprog. Ignorér det!
--
/ Mikkel

---

On Fri, 1 Aug 2008 06:39:56 +0200, Mikkel Mikkelsen wrote:

> akedemikersprog.

Ach, det kan jo smutte - selv for den bedste
--
/ Mikkel

---

pbc wrote:
> Mange af eksperimenterne findes også som spil, så man kan afprøve sine
> resultater i praksis. Idéen med programmet er at nærme sig beregning
> af sandsynlighed ad eksperimentel vej.

Den helt generelle approach er at udføre en Monte Carlo simulation.

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

Ideen er rundt regnet at genererer et stort antal tilfældige tilstande
for spillet og så tælle alle dem der opfylder bestemte kriterier og derved
estimerer sandsyneligheden for det udfald. I en mere suffistikeret version
bruger man f.eks. Metropolis algoritmen til at sample "interessante"
tilstande mere hyppigt (Importance Sampling).

Det kunne man skrive langt om da det er et fascinerende emne, men det er
for sent...
--
Mvh. Carsten Svaneborg
http://gauss.ffii.org softwarepatent database

---

Carsten Svaneborg <sslug@zqex.dk> writes:

> pbc wrote:
>> Mange af eksperimenterne findes også som spil, så man kan afprøve sine
>> resultater i praksis. Idéen med programmet er at nærme sig beregning
>> af sandsynlighed ad eksperimentel vej.
>
> Den helt generelle approach er at udføre en Monte Carlo simulation.
>
> http://en.wikipedia.org/wiki/Monte_Carlo_method
>
> Ideen er rundt regnet at genererer et stort antal tilfældige tilstande
> for spillet og så tælle alle dem der opfylder bestemte kriterier og derved
> estimerer sandsyneligheden for det udfald. I en mere suffistikeret version
> bruger man f.eks. Metropolis algoritmen til at sample "interessante"
> tilstande mere hyppigt (Importance Sampling).

Monte Carlo metoder er ikke specielt præcise, men de er gode, hvis man
ikke kan finde nogen genveje til eksakt beregning, sådan at man bliver
nødt til at opremse hele udfaldsrummet for at finde eksakte resultater
(hvilket kan være alt for tidskrævende). Monte Carlo metoder går
groft sagt ud på at opremse en tilfældig delmængde af udfaldsrummet og
håbe på, at det giver et repræsentativt udsnit. Men eksakte bliver de
aldrig.

Troll beregner (med nogle få undtagelser) eksakt indenfor de
begrænsninger, som floating point aritmetik giver, så resultaterne er
bedre end Monte Carlo metoder. Jeg bruger dog selv Monte Carlo, når
den eksakte beregning i Troll bliver for tidskrævende. Da Troll også
kan lave (pseudo)tilfældige samples, kan Troll også bruges til dette.

Bemærk, at Troll ikke altid behøver at opremse hele udfaldssrummet.
Troll kan i mange tilfælde finde regulariteter i
terningebeskrivelserne og udnytte dem til at finde genveje. For
eksempel ser "max 10d10" ud til at kræve opremsning af 10^10 udfald,
men da max-operatoren er en homomorfi, tager det mindre end en
hundrededel af et sekund at beregne fordelingen:

Value % = % >=
1 : 1E~8 100.0
2 : 1.023E~5 99.99999999
3 : 0.00058025 99.99998976
4 : 0.00989527 99.99940951
5 : 0.08717049 99.98951424
6 : 0.50700551 99.90234375
7 : 2.22009073 99.39533824
8 : 7.91266575 97.17524751
9 : 24.13042577 89.26258176
10 : 65.13215599 65.13215599

Average = 9.5085658075 Spread = 0.789226309079 Mean deviation = 0.640163369695

Og så lige en advarsel: Jeg fandt en bug i Troll i dag, så hvis nogen
har downloaded Troll, så download den rettede version fra
www.diku.dk/~torbenm/Troll .

   Torben

---

"Torben "Ægidius" Mogensen" <torbenm@pc-003.diku.dk> skrev i meddelelsen
news:7zzlnrznjo.fsf@pc-003.diku.dk...

> Troll kan i mange tilfælde finde regulariteter i
> terningebeskrivelserne og udnytte dem til at finde genveje. For
> eksempel ser "max 10d10" ud til at kræve opremsning af 10^10 udfald,
> men da max-operatoren er en homomorfi, tager det mindre end en
> hundrededel af et sekund at beregne fordelingen:

Er det muligt kort at forklare det lidt nærmere?

Mvh
Martin

---

"Martin Larsen" <mlarsen@post7.tele.dk> writes:

> "Torben "Ægidius" Mogensen" <torbenm@pc-003.diku.dk> skrev i
> meddelelsen news:7zzlnrznjo.fsf@pc-003.diku.dk...
>
>> Troll kan i mange tilfælde finde regulariteter i
>> terningebeskrivelserne og udnytte dem til at finde genveje. For
>> eksempel ser "max 10d10" ud til at kræve opremsning af 10^10 udfald,
>> men da max-operatoren er en homomorfi, tager det mindre end en
>> hundrededel af et sekund at beregne fordelingen:
>
> Er det muligt kort at forklare det lidt nærmere?

Troll arbejder med multimængder, som er en mellemting mellem lister og
mængder, idet rækkefølgen ikke betyder noget (ligesom i mængder), men
antallet af ens elementer betyder noget (ligesom i lister).
Multimængder har en foreningsmængdeoperator U, som virker på den
oplagte måde (hvert element forekommer som summen af de gange, det
forekommer i de to mængder).

En homomorfi for multimængder er en funktion f, sådan at der findes en
operator o, så f(A U B) = F(A) o F(B), dvs. at man kan beregne f på
delmængderne og kombinere resultatet med o. Et eksempel er "sum", som
tager summen af af elementerne i en multimængde, idet sum(A U B) =
sum(A)+sum(B). Et andet er max, idet max(A U B) = max({max(A),max(B)}).

Hvis man kun har en enkelt multimængde, giver disse regler ikke nogen
tidsbesparelse, men i sandsynlighedsberegningerne arbejder vi med en
sandsynlighedsfordeling af multimængder. Groft sagt, kan man definere
sandsynlighedsfordelingen som en mængde af par (p,M), hvor p er en
sandsynlighed og M er en multimængde, og hvor summen af p'erne er 1.
Vi bruger herunder d1, d2 osv. for fordelinger.

Man kan udvide foreningsmængde til fordelinger:

d1 U d2 = {(p1*p2, M1 U M2) | (p1,M1) tilhører d1 og (p2,M2) tilhører M2}

Det er forholdsvist nemt at se, at størrelsen af d1 U d2 er produktet
af størrelserne af d1 og d2, selvom man kan kombinere par (p,M) og
(q,M) til (p+q,M). For eksempel er der "kun" 21 par af to terninger,
selv om hver terning har 6 muligheder. Men det bliver alligevel ret
stort, hvis man har mange terninger.

Man kan tage en funktion på en fordeling ved at tage den på alle
multimængderne:

f(d) = {(p, f(M)) | (p,M) tilhører d}

Der er aldrig flere elementer i resultatfordelingen end i
argumentfordelingen, men der kan værre færre, idet man kan kombinere
parrene (p,f(M1)) og (q,f(M2)) til (p+q,f(M1)), hvis f(M1) = f(M2).

Derfor kan en beregning af f.eks. sum(d1 U d2) gøres hurtigere ved at
sige sum(d1) ++ sum(d2), hvor ++ er + "løftet" til fordelinger.

Eksempel: Som nævnt har fordelingen af to terninger 21 elementer, og
fordelingen af fire terninger har 231 elementer. Beregning af summen
af hver af de 231 elementer kræver 231*3 = 693 plusoperationer. I
stedet kan man beregne summen af hver af de 21 par, hvilket kræver
21*2 = 42 plusoperationer og giver 11 mulige summer. Summerne af de
to delmænger (hver med 11 mulige summer) kan gøres med 121
plusoperationer, så vi har reduceret de 693 plusoperationer til
121*2+66 = 308 plusoperationer. Hvis vi kun beregner summen af
parrene en gang (fordi de to delmængder af par er ens), kan vi
reducere det til 121+66 = 187 plusoperationer.

Generelt er der en besparelse, hvis antallet af mellemresultater er
mindre end antallet af multimængder, som mellemresultaterne bliver
beregnet fra. Det gælder f.eks. sum, max og count.

Troll gør det ved at bruge en ikke-normaliseret repræsentation af
fordelinger. I stedet for at repræsentere en fordeling som en mængde
af par af formen (p,M), repræsenterer Troll den som en træstruktur,
hvor indre knuder enten er probabilistiske valg eller
foreningsoperatorer og bladene er multimængder. En operation som
f.eks. sum beregnes på bladene og resultaterne kombineres op gennem
træet.

   Torben

---

"Torben "Ægidius" Mogensen" <torbenm@pc-003.diku.dk> skrev i meddelelsen
news:7zsktijxgr.fsf@pc-003.diku.dk...
> "Martin Larsen" <mlarsen@post7.tele.dk> writes:
>
>> "Torben "Ægidius" Mogensen" <torbenm@pc-003.diku.dk> skrev i
>> meddelelsen news:7zzlnrznjo.fsf@pc-003.diku.dk...
>>
>>> Troll kan i mange tilfælde finde regulariteter i
>>> terningebeskrivelserne og udnytte dem til at finde genveje. For
>>> eksempel ser "max 10d10" ud til at kræve opremsning af 10^10 udfald,
>>> men da max-operatoren er en homomorfi, tager det mindre end en
>>> hundrededel af et sekund at beregne fordelingen:
>>
>> Er det muligt kort at forklare det lidt nærmere?
>
> Troll arbejder med multimængder, som er en mellemting mellem lister og
> mængder, idet rækkefølgen ikke betyder noget (ligesom i mængder), men
> antallet af ens elementer betyder noget (ligesom i lister).
> Multimængder har en foreningsmængdeoperator U, som virker på den
> oplagte måde (hvert element forekommer som summen af de gange, det
> forekommer i de to mængder).
>
> En homomorfi for multimængder er en funktion f, sådan at der findes en
> operator o, så f(A U B) = F(A) o F(B), dvs. at man kan beregne f på
> delmængderne og kombinere resultatet med o. Et eksempel er "sum", som
> tager summen af af elementerne i en multimængde, idet sum(A U B) =
> sum(A)+sum(B). Et andet er max, idet max(A U B) = max({max(A),max(B)}).
>
> Hvis man kun har en enkelt multimængde, giver disse regler ikke nogen
> tidsbesparelse, men i sandsynlighedsberegningerne arbejder vi med en
> sandsynlighedsfordeling af multimængder. Groft sagt, kan man definere
> sandsynlighedsfordelingen som en mængde af par (p,M), hvor p er en
> sandsynlighed og M er en multimængde, og hvor summen af p'erne er 1.
> Vi bruger herunder d1, d2 osv. for fordelinger.
>
> Man kan udvide foreningsmængde til fordelinger:
>
> d1 U d2 = {(p1*p2, M1 U M2) | (p1,M1) tilhører d1 og (p2,M2) tilhører M2}
>
> Det er forholdsvist nemt at se, at størrelsen af d1 U d2 er produktet
> af størrelserne af d1 og d2, selvom man kan kombinere par (p,M) og
> (q,M) til (p+q,M). For eksempel er der "kun" 21 par af to terninger,
> selv om hver terning har 6 muligheder. Men det bliver alligevel ret
> stort, hvis man har mange terninger.
>
> Man kan tage en funktion på en fordeling ved at tage den på alle
> multimængderne:
>
> f(d) = {(p, f(M)) | (p,M) tilhører d}
>
> Der er aldrig flere elementer i resultatfordelingen end i
> argumentfordelingen, men der kan værre færre, idet man kan kombinere
> parrene (p,f(M1)) og (q,f(M2)) til (p+q,f(M1)), hvis f(M1) = f(M2).
>
> Derfor kan en beregning af f.eks. sum(d1 U d2) gøres hurtigere ved at
> sige sum(d1) ++ sum(d2), hvor ++ er + "løftet" til fordelinger.
>
> Eksempel: Som nævnt har fordelingen af to terninger 21 elementer, og
> fordelingen af fire terninger har 231 elementer.

Mener du ikke c(9,4)=126

Jeg forstod ikke helt opbygningen af dit træ, men kunne måske studere din
kode.

Mvh
Martin

---

"Martin Larsen" <mlarsen@post7.tele.dk> writes:

> "Torben "Ægidius" Mogensen" <torbenm@pc-003.diku.dk> skrev i
> meddelelsen news:7zsktijxgr.fsf@pc-003.diku.dk...

>> Eksempel: Som nævnt har fordelingen af to terninger 21 elementer, og
>> fordelingen af fire terninger har 231 elementer.
>
> Mener du ikke c(9,4)=126

Jo. For at finde antallet af par sagde jeg 6*7/2 = 21 og for at finde
antallet af fire-sæt fandet jeg antallet af par af par som 21*22/1 =
231, hvorved jeg glemte at tage højde for, at to forskellige par af
par kan give samme fire-sæt. Beklager.

> Jeg forstod ikke helt opbygningen af dit træ, men kunne måske
> studere din kode.

Jeg må advare dig om, at jeg ikke har været voldsomt god til at
kommentere koden. Men heldigvis er SML nemmere at læse end
f.eks. Java, så du klarer det nok. Den centrale datastruktur er:

type value = int list

datatype dist = VAL of value
| CHOICE of real * dist * dist
| UNION of dist * dist
| TWICE of dist

Så en værdi (en multimængde) er repræsenteret som en liste af heltal.
En invariant er, at denne liste altid er sorteret.

En fordeling (distribution) er enten:

VAL v: En multimængde v, som er det enenste mulige udfald, eller

CHOICE (p,d1,d2), som siger at med sandsynlighed p finder du en værdi
fra fordelingen d1 og med sandsynlighed 1-p en værdi fra
fordelingen d2, eller

UNION (d1,d2), som siger, at du far en værdi ved at vælge en værdi fra
d1 og kombinere den med en verdi fra d2, eller

TWICE d, som er ækvivalent med UNION(d,d).

En almindelig sekssidet terning vil f.eks. have fordelingen

CHOICE (1/2, CHOICE (1/3, VAL [1], CHOICE (1/2, VAL [2], VAL [3])),
CHOICE (1/3, VAL [4], CHOICE (1/2, VAL [5], VAL [6])))

Man kunne også bruge fordelingen

CHOICE (1/6, VAL [1], CHOICE (1/5, VAL [2], CHOICE (1/4, VAL [3],
CHOICE (1/3, VAL [4], CHOICE (1/2, VAL[5], VAL[6])))))

men i visse situationer er der fordele ved balancerede træer.

Fordelingen af par af to terninger (2d6) vil være

TWICE
(CHOICE (1/2, CHOICE (1/3, VAL [1], CHOICE (1/2, VAL [2], VAL [3])),
CHOICE (1/3, VAL [4], CHOICE (1/2, VAL [5], VAL [6]))))

Hvis du beregner Troll-udtrykket

sum (3 < 2d6)

vil deludtrykket 2d6 beregne den herover viste distribution, 3 < vil
filtrere tal under 4 fra, hvilket distribuerer over træet og kun gøres
i bladknuderne, så man får:

TWICE
(CHOICE (1/2, CHOICE (1/3, VAL [], CHOICE (1/2, VAL [], VAL [])),
CHOICE (1/3, VAL [4], CHOICE (1/2, VAL [5], VAL [6]))))

som reduceres til

TWICE
(CHOICE (1/2, VAL [],
CHOICE (1/3, VAL [4], CHOICE (1/2, VAL [5], VAL [6]))))

Sum på dette reducerer i første omgang til

twiceWith (+)
(CHOICE (1/2, VAL [0],
CHOICE (1/3, VAL [4], CHOICE (1/2, VAL [5], VAL [6]))))

Bemærk, at summen af den tomme mængde er 0 og i alle andre tilfælde er
det tallet selv.

Næste skridt er at fordele twiceWith over CHOICE:

CHOICE (1/4,
twiceWith (+) (VAL [0]),
CHOICE (1/3,
twiceWith (+) (CHOICE (1/3, VAL [4], CHOICE (1/2, VAL [5], VAL [6]))),
unionWith (+) (VAL [0])
(CHOICE (1/3, VAL [4], CHOICE (1/2, VAL [5], VAL [6])))))

Det fremkommer ved, at der er en fjerdedel chance for at vælge 0 to
gange, en fjerdedel chance (dvs. 1/3 af resten) for at vælge et par
fra den anden del (4-6) og ellers et par af 0 og et andet tal.

Næste reduktion giver:

CHOICE (1/4,
VAL [0+0],
CHOICE (1/3,
CHOICE (1/9,
twiceWith (+) (VAL [4]),
CHOICE (1/2,
twiceWith (+) (CHOICE (1/2, VAL [5], VAL [6])),
unionWih (+) (VAL [4])
(CHOICE (1/2, VAL [5], VAL [6]))),
CHOICE (1/3, VAL [0+4], CHOICE (1/2, VAL [0+5], VAL [0+6]))))

og dernæst

CHOICE (1/4,
VAL [0],
CHOICE (1/3,
CHOICE (1/9,
VAL [4+4],
CHOICE (1/2,
CHOICE (1/4,
twiceWith (+) (VAL [5]),
CHOICE (1/3,
twiceWith (+) (VAL [6]),
unionWith (+) (VAL [5]) (VAL [6])),
CHOICE (1/2, VAL [4+5], VAL [4+6])),
CHOICE (1/3, VAL [4], CHOICE (1/2, VAL [5], VAL [6]))))

og

CHOICE (1/4,
VAL [0],
CHOICE (1/3,
CHOICE (1/9,
VAL [8],
CHOICE (1/2,
CHOICE (1/4,
VAL [5+5],
CHOICE (1/3,
VAL [6+6],
VAL [5+6]),
CHOICE (1/2, VAL [9], VAL [10])),
CHOICE (1/3, VAL [4], CHOICE (1/2, VAL [5], VAL [6]))))

=

CHOICE (1/4,
VAL [0],
CHOICE (1/3,
CHOICE (1/9,
VAL [8],
CHOICE (1/2,
CHOICE (1/4,
VAL [10],
CHOICE (1/3,
VAL [12],
VAL [11]),
CHOICE (1/2, VAL [9], VAL [10])),
CHOICE (1/3, VAL [4], CHOICE (1/2, VAL [5], VAL [6]))))

Det virker måske ikke som nogen genvej, men ved større træer er der en
stor gevinst. Bemærk, at VAL [10] forekommer to gange i træet, så det
er ikke optimalt, men det kan ikke betale sig at optimere alt for
meget på træerne under beregningerne. Der sker nogle lokale
reduktioner i træet undervejs, men de to forekomster er for langt fra
hinanden til, at det bliver opdaget. Men inden udskrift normaliseres
træet, så tallene kommer i sorteret orden:

CHOICE (1/4, VAL [0],
CHOICE (2/9, VAL [4],
CHOICE (2/7, VAL [5],
CHOICE (2/5, VAL [6],
CHOICE (1/9, VAL [8],
CHOICE (1/4, VAL [9],
CHOICE (1/2, VAL [10],
CHOICE (2/3, VAL [11],
VAL [12]))))))))

hvilket udskrives som

Value % = % >=
0 : 25.0 100.0
4 : 16.6666666667 75.0
5 : 16.6666666667 58.3333333333
6 : 16.6666666667 41.6666666667
8 : 2.77777777778 25.0
9 : 5.55555555556 22.2222222222
10 : 8.33333333333 16.6666666667
11 : 5.55555555556 8.33333333333
12 : 2.77777777778 2.77777777778

Average = 5.0 Spread = 3.62859017618 Mean deviation = 2.83333333333

   Torben

---

"Torben "Ægidius" Mogensen" <torbenm@pc-003.diku.dk> skrev i meddelelsen
news:7zmyjp42dn.fsf@pc-003.diku.dk...
>
> Average = 5.0 Spread = 3.62859017618 Mean deviation = 2.83333333333
>

Jeg fandt iøvrigt noget sjovt i forbindelse med "max 10d10"

n^10:
[1, 1024, 59049, 1048576, 9765625, 60466176, 282475249,
1073741824, 3486784401, 10000000000]

-

[0, 1, 1024, 59049, 1048576, 9765625, 60466176, 282475249,
1073741824, 3486784401]

=

[1, 1023, 58025, 989527, 8717049, 50700551, 222009073,
791266575, 2413042577, 6513215599]

Mvh
Martin

---

"Martin Larsen" <mlarsen@post7.tele.dk> writes:

> "Torben "Ægidius" Mogensen" <torbenm@pc-003.diku.dk> skrev i
> meddelelsen news:7zmyjp42dn.fsf@pc-003.diku.dk...
>>
>> Average = 5.0 Spread = 3.62859017618 Mean deviation = 2.83333333333
>>
>
> Jeg fandt iøvrigt noget sjovt i forbindelse med "max 10d10"
>
> n^10:
> [1, 1024, 59049, 1048576, 9765625, 60466176, 282475249,
> 1073741824, 3486784401, 10000000000]
>
> -
>
> [0, 1, 1024, 59049, 1048576, 9765625, 60466176, 282475249,
> 1073741824, 3486784401]
>
> =
>
> [1, 1023, 58025, 989527, 8717049, 50700551, 222009073,
> 791266575, 2413042577, 6513215599]

Ja, det er der vel ikke noget overraskende i. Hvis max 10d10 skal
være 1, skal alle 10 terninger være 1, hvilket har chance (1/10)^10.

Hvis max 10d10 er 2, skal alle ti terninger være 1 eller 2, men de må
ikke alle være 1, så det er altså (2/10)^2-(1/10)^10 = (2^10-1)/10^10.

osv.

Netop max af m terninger er ret nemt at beregne i hånden, men Troll
kan også klare mere komplicerede ting. Generelt er Troll hurtig i de
tilfælde, hvor der findes simple formler -- ikke fordi Troll bruger
dem, men fordi formlerne i reglen udnytter samme slags regulariteter,
som Troll gør med sin træstruktur.

Lad os tage et andet eksempel: Hvor mange forskellige værdier får man,
når man ruller 10d10? I Troll skriver man:

count different 10d10

og får efter ca. 9 sekunder resultatet:

Value % = % >=
1 : 1E~7 100.0
2 : 0.000459899999998 99.9999999
3 : 0.067176 99.99954
4 : 1.718892 99.932364
5 : 12.85956 98.213472
6 : 34.514424 85.353912
7 : 35.56224 50.839488
8 : 13.608 15.277248
9 : 1.63296 1.669248
10 : 0.036288 0.036288

Average = 6.513215599 Spread = 0.996391167134 Mean deviation = 0.834613074265

Det er ikke svært at finde ud af, hvor sandsynligt det er at få alle
ens: 1/10^9 (= 10^-7 procent), eller alle forskellige:
9/10*8/10*...*1/10 = 9!/10^10. Men det er ikke så nemt at udregne,
hvad chancen er for at få f.eks. seks forskellige. Man kan godt
opstille en formel, men den er kompliceret, og der er høj chance for,
at man laver fejl undervejs.

Eller noget mere kompliceret: Rul 7 d10 indtil der er mindst seks
forskellige, og tag derefter summen af sidste kast:

sum repeat x:=7d10 until 5 < count different x

som på under et sekund giver:
% >=
22 : 0.0666666666667 100.0
23 : 0.133333333333 99.9333333333
24 : 0.266666666667 99.8
25 : 0.466666666667 99.5333333333
26 : 0.8 99.0666666667
27 : 1.2 98.2666666667
28 : 1.46666666667 97.0666666667
29 : 2.13333333333 95.6
30 : 2.66666666667 93.4666666667
31 : 3.26666666667 90.8
32 : 3.93333333333 87.5333333333
33 : 4.6 83.6
34 : 5.0 79.0
35 : 5.53333333333 74.0
36 : 5.93333333333 68.4666666667
37 : 6.13333333333 62.5333333333
38 : 6.4 56.4
39 : 6.4 50.0
40 : 6.13333333333 43.6
41 : 5.93333333333 37.4666666667
42 : 5.53333333333 31.5333333333
43 : 5.0 26.0
44 : 4.6 21.0
45 : 3.93333333333 16.4
46 : 3.26666666667 12.4666666667
47 : 2.66666666667 9.2
48 : 2.13333333333 6.53333333333
49 : 1.46666666667 4.4
50 : 1.2 2.93333333333
51 : 0.8 1.73333333333
52 : 0.466666666667 0.933333333333
53 : 0.266666666667 0.466666666667
54 : 0.133333333333 0.2
55 : 0.0666666666667 0.0666666666667

Average = 38.5 Spread = 5.8864250611 Mean deviation = 4.79866666667

Er der en, der vil være så venlig at finde en formel herfor?

   Torben

---

Torben Ægidius Mogensen wrote:
> Monte Carlo metoder går groft sagt ud på at opremse en tilfældig
> delmængde af udfaldsrummet og håbe på, at det giver et
> repræsentativt udsnit. Men eksakte bliver de aldrig.

Nej, i de fleste praktiske problemer er det godt nok med en
værdi og et estimat af fejlen, og når det gælder høj-dimensionale
problemer vinder MC typisk over naivere metoder.

P.t. kører jeg en MC simulation af et polymer molekyle, der er
10000 bonds lang, dens konfigurationsrum er 3^10000 dimensionalt,
men det er kun et ~10000 dimensionalt underrum, der indeholder
relevante konfigurationer og det er dem jeg generer med importance
sampling.

Der findes ikke en eksakt løsning af det problem.

--
Mvh. Carsten Svaneborg
http://gauss.ffii.org softwarepatent database