[Perl] Kaartspel schudden *

[Anoniem: 29724]

Ik ben bezig met een maken van een spelletje (voor mezelf) hartenjagen. Ik maak dit in Perl maar dat doet verder niet zo heel veel terzake. Er zijn 52 kaarten die over 4 spelers verdeelt moeten worden. Iedere kaart mag uiteraard maar 1 x uitgegeven worden.

Hier is dan meteen mijn vraag. Hoe zou je een functie kunnen maken die kaarten kan schudden?

Ik heb nu 1 = hartenaas, 2 = hartenheer etc.. Wat ik dus moet doen is 1-52 random doorelkaar gooien en dan iedere speler kaarten geven. Iemand enig idee hoe je dit zou kunnen doen? Ben benieuwd naar tips.p.s.

Ik had eerst bedacht om gewoon met een random functie kaarten weg te geven en dan bijhouden welke kaarten al uitgegeven zijn maar dit gaat enorm lang loopen.. Ik dacht dat het wel mee zou vallen maar niet dus.

[gorgi_19]

* gorgi_19 zou (in vb.net) alles in een hashtable gooien. Hierbij zijn de keys 1 t/m 52 en de values een random nummer. Vervolgens kan je sorteren op de values. Oftewel: Koppel iedere kaart aan een random nummer en sorteer op random nummer.

Geen idee of zo een methodiek ook zou werken in Perl.

Zo voorkom je in ieder geval eindeloze iteraties met het bijhouden of iets wel of niet is uitgegeven..

[ Voor 32% gewijzigd door gorgi_19 op 10-08-2003 14:52 ]

[hammerhead]

Je kunt gewoon even zoeken op een random permutatie algoritme.

Basis is iets van:
* Zet alles in een array.
* Ga alle indices een keer af en swap het element (=kaart) op deze plaats met een kaart op een willekeurige andere index.

Als je dit voor alle indices een keer hebt gedaan heb je de kaarten gewoon geschud.

[ACM]

Anoniem: 29724 schreef op 10 augustus 2003 @ 14:37:
Ik had eerst bedacht om gewoon met een random functie kaarten weg te geven en dan bijhouden welke kaarten al uitgegeven zijn maar dit gaat enorm lang loopen.. Ik dacht dat het wel mee zou vallen maar niet dus.

Je hoeft maximaal slechts 51x een random waarde te genereren, ik weet niet precies hoe jij dat hebt gemaakt en waarom het lang zou duren, maar in principe hoeft dat niet lang te duren.

Maak bijvoorbeeld een arraytje met de kaartnummers die nog "in de hand zijn" en elke keer dat je er daar een random uitgekozen hebt verwijder je die entry.
Dan krijg je dus in php (ik weet dat je perl doet, maar daar ken ik de syntax niet zo goed van):

PHP:

$kaartenhand = array(...);
while(nog_kaarten_uit_te_delen())
{
   $maxrandom = count($kaartenhand);
   $kies_een_kaart = random(0, $maxrandom);
   deel_kaart_uit_aan_whoever($kies_een_kaart);
   unset($kaartenhand[$kies_een_kaart]);  
}

Een andere manier is de array random sorteren en dan gewoon steeds de bovenste waarde pakken. Php kent zelfs een functie ervoor, maar die zal in perl ook wel eenvoudig te maken zijn.

[Anoniem: 29724]

Bedankt voor jullie tips. Er zaten meerdere bruikbare ideeen bij. Ik ga eerst even voor ACM zijn idee met een array en daar random uitpakken en dan array verkleinen zodat max kaarten verkleind wordt. Ik heb daar wel een goed gevoel over. Idee van Hammerhead lijkt me ook erg mooi trouwens maar dan moet ik een perl module includen en daar heb ik in eerste instantie geen trek in. Het is wel zo dat als dat 1 x werkt dan is het een makkie verder maar ik houd dat nog even achter de hand.

acm: Ik had eerst gewoon random nummer pakken tussen 1 en 52 die aan speler1 geven, uitgegeven kaart in array stoppen dan weer random nummer pakken en die kaart aan speler2 geven behalve als kaart al uitgeven was, dus array checken, etc.. etc.. Dikke ramp dus want hoe meer kaarten uitgeven zijn hoe langer de functie aan het zoeken is naar een niet gebruikt nummer. Naja dat was mn eerste stukje code gewoon uitgeschreven. Ik had er toen nog niet over nagedacht maar zat in de fase van 'eerst maar eens beginnen met een opzetje'.. nou ja dat werkte dus niet. Ik ga maandag weer verder! Iedereen bedankt!

[phreggle]

Ik zou zoiets doen:

code:

my @cards = (1..52);
my $c = scalar(@cards);

foreach(reverse 0..$c) {
  my $card = splice(@cards, rand $c, 1);
  push(@cards, $card);
}

Je pakt dus een random kaart eruit (splice met lengte 1) en stopt die achteraan. Dan heb je dus een 'shuffle array' functie en kan je gewoon de kaarten uitdelen.

[hammerhead]

Anoniem: 29724 schreef op 10 August 2003 @ 15:19:
Bedankt voor jullie tips. Er zaten meerdere bruikbare ideeen bij. Ik ga eerst even voor ACM zijn idee met een array en daar random uitpakken en dan array verkleinen zodat max kaarten verkleind wordt. Ik heb daar wel een goed gevoel over. Idee van Hammerhead lijkt me ook erg mooi trouwens maar dan moet ik een perl module includen en daar heb ik in eerste instantie geen trek in. Het is wel zo dat als dat 1 x werkt dan is het een makkie verder maar ik houd dat nog even achter de hand.

acm: Ik had eerst gewoon random nummer pakken tussen 1 en 52 die aan speler1 geven, uitgegeven kaart in array stoppen dan weer random nummer pakken en die kaart aan speler2 geven behalve als kaart al uitgeven was, dus array checken, etc.. etc.. Dikke ramp dus want hoe meer kaarten uitgeven zijn hoe langer de functie aan het zoeken is naar een niet gebruikt nummer. Naja dat was mn eerste stukje code gewoon uitgeschreven. Ik had er toen nog niet over nagedacht maar zat in de fase van 'eerst maar eens beginnen met een opzetje'.. nou ja dat werkte dus niet. Ik ga maandag weer verder! Iedereen bedankt!

Ik zie niet in waarom je een extra perl module moet includen. Het enige wat je nodig hebt zijn een random generator, een for lusje en wat array operaties. Weet niet welke extra perl module je daarvoor nodig denkt te hebben...

Verder is het probleem van de methode van ACM idd dat het erg lang kan gaan duren op het moment dat je dus nog maar 3 kaarten over hebt ofzo. Het voordeel van mijn methode is dat hij de kaarten in lineaire tijd door elkaar schudt. Het kost altijd even lang om de kaarten opnieuw te schudden.

[bigtree]

Hoewel het perl is, is dit probleem wel heel basic.

Even googlen, en je voor je het weet heb je wat je zoekt.

[ACM]

hammerhead schreef op 10 August 2003 @ 15:32:
Verder is het probleem van de methode van ACM idd dat het erg lang kan gaan duren op het moment dat je dus nog maar 3 kaarten over hebt ofzo. Het voordeel van mijn methode is dat hij de kaarten in lineaire tijd door elkaar schudt. Het kost altijd even lang om de kaarten opnieuw te schudden.

Dan moet je mijn methode beter bekijken, zijn eigen eerste methode had die beperking. De mijne is gewoon lineair met het aantal aanwezige en/of benodigde kaarten, afhankelijk van welke minder is.

Jouw methode schud alles in lineaire tijd, afhankelijk van het aantal kaarten, ook als er maar 4 nodig zijn. Anderzijds heeft mijn versie wellicht wat complexere array-bewerkingen nodig, magoed, dat maakt hem niet ineens non-lineair (hooguit een beetje superlineair op dat vlak, doordat de array kleiner wordt).

[Anoniem: 26306]

In dit topic heb ik uitgelegd dat de methode die hammerhead nu geeft niet optimaal is. De methode die ACM voorstelt is wel 100% random, en -zoals hij zelf aangeeft- lineair.

[ACM]

En dat zal dan in de richting gezocht moeten worden dat de zijne een soort mengelmoes is van een trekking zonder teruglegging en een trekking met teruglegging (oftewel, het is mogelijk dat je twee keer dezelfde positie swapt, terwijl je wel alle posities wilt laten swappen), terwijl mijn methode een pure trekking zonder teruglegging is (wat volgens mij ook min of meer verplicht is voor een random-trekking als deze). Of denk ik nou helemaal verkeerd?

[ Voor 10% gewijzigd door ACM op 10-08-2003 16:58 ]

[Anoniem: 26306]

hammerhead schreef op 10 August 2003 @ 14:58:
* Zet alles in een array.
* Ga alle indices een keer af en swap het element (=kaart) op deze plaats met een kaart op een willekeurige andere index.

Ik denk dat het daar gezocht moet worden.

[MSalters]

Ik denk dat hammerhead's algoritme fout is. Het rekent makkelijker met 3 kaarten {A,B,C}:

ABC -> BAC of CBA -> BCA(1/2) of ABC(1/4) of CAB(1/4) -> ACB(3/8) of BAC(3/8) of CBA(1/4)

Je ziet dat maar de helft van de 6 mogelijkheden voorkomt, en dat de kansen een eindige binaire representatie hebben. Dat geldt voor alle algoritmes die precies N keer swappen; de kansen zijn dan een veelvoud van 2^-N. Aangezien alle kansen 1/N! moet zijn is dit niet mogelijk; voor N>=3 zit er altijd een factor 1/3 in, en 1/3 heeft geen eindige binaire representatie.

[Soultaker]

Kunnen we geen FAQ-item over dit onderwerp maken? Het komt wel met enige regelmaat langs en eigenlijk valt er niet zoveel nieuws over te zeggen. (Dwz. er ontstaat geen interessante discussie, maar meer het oplepelen van geschikte algoritmen en het afwijzen van voor de hand liggende ongeschikte algoritmen).

[bigtree]

Soultaker schreef op 11 August 2003 @ 00:34:
Kunnen we geen FAQ-item over dit onderwerp maken? Het komt wel met enige regelmaat langs en eigenlijk valt er niet zoveel nieuws over te zeggen. (Dwz. er ontstaat geen interessante discussie, maar meer het oplepelen van geschikte algoritmen en het afwijzen van voor de hand liggende ongeschikte algoritmen).

Als het vaak langskomt is dat meer een teken dat mensen de search niet gebruiken. Ik betwijfel of diezelfde mensen wel de faq lezen. Maar het is altijd nuttig om in GoT ontgonnen kennis expliciet te maken en de FAQ is daar een uitstekend middel voor.

Wellicht handig om in het kader daarvan te vermelden dat er voor bijvoorbeeld php een standaard functie is voor het shufflen van arrays: shuffle.

Nog een nuttig linkje. Goed keyword voor google is in dit verband trouwens 'fisher yates shuffle', want zo heet de eerder in deze thread besproken methode.

[windancer]

Altijd interessant : kijk even in Knuth's "The Art of Computer Programming". Daarin staan een aantal shuffling algorithmes beschreven ook met een aanbeveling welke te gebruiken.

[curry684]

Hmm kaartspel shuffling staat me nu niet echt bij dat het zo vaak langskomt, maar het staat iedereen natuurlijk vrij om een interessant stuk te schrijven over dit soort onderwerpen en te mailen naar een P&W-mod, dan beland het vanzelf in de technische FAQ

[nhimf]

Kijk even in dit topic: [rml][ Borland C] Random getallen maken loopt vast*[/rml]
Ik zocht zelf naar een snelle randomizer waarin elk getal maar 1x mocht voorkomen. Deze methode die ik als tip kreeg werkt echt snel en perfect.


ps. Je kan natuurlijk ook kijken naar de methode die soultaker gaf in mijn topic.

[ Voor 15% gewijzigd door nhimf op 11-08-2003 09:51 ]

[Soultaker]

curry684 schreef op 11 August 2003 @ 09:38:
Hmm kaartspel shuffling staat me nu niet echt bij dat het zo vaak langskomt

Als ik zoek op "array" en "random" en alleen de eerste twee (van de negen) pagina's met resultaten bekijk, krijg ik al een hele stapel van exact dezelfde problemen:

Uniek random getal
[rml][ php] random kaarten delen[/rml]
[rml][ php] Random image, alleen jpg, zonder dubbele[/rml]
[rml][ DELPHI] Kaarten[/rml]
JAVA Random probleempje !!!
[rml][ PHP] Random image script zonder dubbele[/rml]
[rml][ php] random een getal maar niet dubbel[/rml]
random elementen uit array halen

En dat is nog maar een bescheiden greep uit de beschikbare resultaten...

[curry684]

Soultaker: ipv dat je nu de hint oppikt uit "maar het staat iedereen natuurlijk vrij om een interessant stuk te schrijven over dit soort onderwerpen"...

[Soultaker]

curry684 schreef op 11 August 2003 @ 15:12:
Soultaker: ipv dat je nu de hint oppikt uit "maar het staat iedereen natuurlijk vrij om een interessant stuk te schrijven over dit soort onderwerpen"...

Jaja, maar het is warm, en ik ben lui, en ik heb het druk, <insert lame reason here>. Ik zal binnenkort eens kijken of ik wat dingen uit die topics op een rijtje kan zetten (maar de echte interessante bijdragen komen toch van derden).

[curry684]

offtopic:
Netjes gehapt...

[Anoniem: 30225]

Anoniem: 26306 schreef op 10 August 2003 @ 17:25:
[...]
Ik denk dat het daar gezocht moet worden.

pseudo-code:

code:

  kaarten := array(1,2,3,4,5,6,...,51,52);

  // getallen random maken a.k.a. schudden
  for i:=1 to Length(kaarten) do
  begin
    rnd := random(52);
    temp := kaarten[i];
    kaarten[i] := kaarten[rnd];
    kaarten[rnd] := temp;
  end;
end;

[ Voor 7% gewijzigd door Anoniem: 30225 op 12-08-2003 00:30 . Reden: typo ]

[ACM]

En dat is nou net de code die niet perfect random is

[curry684]

Het beste algoritme voor realistisch een kaartspel schudden is botweg om een X aantal keer een willekeurige kaart naar achterin het dek te plaatsen. De reden hierachter is dat bij veel kaartspellen (denk aan hartenjagen, klaverjassen, poker) het ongewenst is om het dek 'kapot te schudden'. In dit geval dien je overigens ook gebruikte kaarten realistisch op het dek te plaatsen, en enkele keren 'couperen' kan ook effectief zijn. De waarde van X moet je even mee spelen.