Kirjautuminen

Haku

Tehtävät

Keskustelu: Ohjelmointikysymykset: Pascal: Mikähän on pasianssin läpimenotodennäköisyys?

PetriKeckman [08.07.2022 19:37:02]

#

Ohjelmoin yhdeksän vuotta sitten javascriptillä, silloin kun vielä jaksoin nähdä vaivaa ja jotain osasinkin, joulupasianssin:

https://petke.info/joulukalenteri/p19.html

Jouluista siinä on itse piirtämäni kortit (kortin takapuolta lukuunottamatta) - sopiva pasianssin aihe näin lähes keskikesälle! Eihän jouluun juuri tällä hetkellä 8/7/2022 klo 19:35 ole kuin 4039 tuntia 24 minuuttia ja 30 sekuntia :)

Ei se nyt niin taidokasta koodia ole, että haluaisin sen tähän laittaa esille, mutta näettehän sen sivulta.

Totesin pelaamalla monta peliä, että ehkä noin joka kymmenes kerta pääsen läpi. Tarkemman läpimenotodennäköisyyden saisi, kun pistäisi ohjelman simuloimaan peliä miljoonia kertoja...Matemaattisesti en osaa laskea todennäköisyyttä.

Pasianssin säännöt ovat siis: nostetaan pakasta neljä korttia pöydälle. Poistetaan samaa maata olevat kortit ja laitetaan pakasta tilalle uudet kortit. Tarkoitus on saada pakka tyhjäksi, eli pasianssi tyssää, jos kaikki kortit ovat eri maata pöydällä. On huomioitava, että pelipöydälle ei nosteta uusia kortteja kesken kaiken, vaan vasta kun edelliset samaa maata olevat on poistettu. Tämähän käsittääkseni vaikuttaa peliin? Pelamalla pasianssia pääsette nopeasti juonesta kiinni.

Olen nyt kokonaisen vuorokauden yrittänyt ohjelmoida pasianssia simuloivaa ohjelmaa. Vaikeaa on :( Palaan tähän projektiin, kun olen saanut ohjelman aikaiseksi. Vai saako joku muu ennen minua? Pascalilla yritän ja haluan käyttää siinä osoitinmuuttujia, mikä juuri tekee hommasta minulle vaikeaa.

Metabolix [09.07.2022 02:12:55]

#

PetriKeckman kirjoitti:

Pascalilla yritän ja haluan käyttää siinä osoitinmuuttujia, mikä juuri tekee hommasta minulle vaikeaa.

Minustakin tämä olisi sikäli vaikea ohjelmoida osoitinmuuttujia käyttämällä, että en näe osoittimille mitään hyvää käyttökohdetta. Yleensä kannattaa välttää tarpeetonta osoitinten käyttöä, koska niihin liittyy erityisen suuri ohjelmointivirheen vaara.

PetriKeckman kirjoitti:

Totesin pelaamalla monta peliä, että ehkä noin joka kymmenes kerta pääsen läpi. Tarkemman läpimenotodennäköisyyden saisi, kun pistäisi ohjelman simuloimaan peliä miljoonia kertoja.

Oheinen Pascal-ohjelma näyttää, että peleistä noin 8,56 prosenttia menee läpi.

program PetriAnssi;

uses SysUtils;

function KortinNimi(Kortti: Integer): String;
var
  Maa, Arvo: Integer;
  MaaS, ArvoS: String;
begin
  Maa := Kortti mod 4;
  Arvo := Kortti div 4;
  case Maa of
    0: MaaS := 'risti';
    1: MaaS := 'ruutu';
    2: MaaS := 'hertta';
    3: MaaS := 'pata';
  end;
  case Arvo of
    0: ArvoS := 'K';
    11: ArvoS := 'J';
    12: ArvoS := 'D';
    1..10: ArvoS := IntToStr(Arvo);
  end;
  KortinNimi := MaaS + '-' + ArvoS;
end;

function AjaPeli(Tulosta: Boolean): Boolean;
var
  Kortit: Array [0..51] of Integer;
  Nostettu, NostettuAlussa: 4..52;
  Maa: 0..3;
  I, J: Integer;
  MaaLkm: Array[0..3] of Integer;
begin
  AjaPeli := True;
  for I := 0 To 51 do begin
    J := Random(I + 1);
    Kortit[I] := Kortit[J];
    Kortit[J] := I;
  end;
  Nostettu := 4;
  repeat begin
    if Tulosta then WriteLn(KortinNimi(Kortit[0]):10, KortinNimi(Kortit[1]):10, KortinNimi(Kortit[2]):10, KortinNimi(Kortit[3]):10);
    NostettuAlussa := Nostettu;
    for Maa := 0 to 3 do MaaLkm[Maa] := 0;
    for I := 0 to 3 do Inc(MaaLkm[Kortit[I] mod 4]);
    for I := 0 to 3 do if MaaLkm[Kortit[I] mod 4] > 1 then begin
      Kortit[I] := Kortit[Nostettu];
      Inc(Nostettu);
      if Nostettu = 52 then Exit;
    end;
  end until Nostettu = NostettuAlussa;
  AjaPeli := False;
end;

var
  Tulokset: Array [Boolean] of LongInt;
  I, N: LongInt;
begin
  Randomize;
  if AjaPeli(True) then WriteLn('Pakka tyhjenee.') else WriteLn('Tappio.');
  WriteLn('Montako ajetaan?');
  ReadLn(N);
  Tulokset[True] := 0;
  Tulokset[False] := 0;
  for I := 1 to N do begin
    Inc(Tulokset[AjaPeli(False)]);
    if (I = N) or (I mod 100000 = 0) then
      WriteLn('Voittoja ', Tulokset[True], ', tappioita ', Tulokset[False], ', voittoja ', (100 * Tulokset[True] / I):4:2, ' %');
  end;
end.

PetriKeckman kirjoitti:

Matemaattisesti en osaa laskea todennäköisyyttä.

Se onkin tällaisessa pelissä aika rankkaa käsin, mutta koska kortin numerolla ei ole merkitystä, ongelma on aika helppo ratkaista rekursiolla, kunhan nopeutuksena välitulokset laittaa muistiin.

JavaScript-versio; paina F12 ja kopioi selaimen konsoliin. Tästä vahvistuu voiton todennäköisyydeksi 8,57 prosenttia.

(() => {
let kertoma = Array(53).fill().map((x, i, t) => t[i] = i ? t[i-1] * BigInt(i) : 1n);

let muisti = {};
function tulos(tila) {
	// Pakka tyhjä?
	if (tila[0] + tila[1] + tila[2] + tila[3] == 0) {
		return {voitot: 1n, tappiot: 0n};
	}
	// Pöytä täysi?
	if (tila[4] + tila[5] + tila[6] + tila[7] == 4) {
		// Pöydällä pelkkiä ykkösiä? => Tappioiden määrä on pakan mahdollisten järjestysten määrä.
		if ((tila[4] | tila[5] | tila[6] | tila[7]) == 1) {
			return {voitot: 0n, tappiot: kertoma[tila[0] + tila[1] + tila[2] + tila[3]]};
		}
		// Muuten poistetaan samat maat.
		if (tila[4] > 1) tila[4] = 0;
		if (tila[5] > 1) tila[5] = 0;
		if (tila[6] > 1) tila[6] = 0;
		if (tila[7] > 1) tila[7] = 0;
	}

	// Dynaaminen ohjelmointi, alkeisversio:
	// Jos tämä tila on jo laskettu, palautetaan tulos muistista.
	let avain = tila.join(",");
	if (muisti[avain]) return muisti[avain];

	// Käydään kaikki vaihtoehdot, mitä maata pakasta voi tulla.
	let summa = {voitot: 0n, tappiot: 0n};
	for (let maa of [0, 1, 2, 3]) if (tila[maa]) {
		// Koska seuraava kortti voi olla mikä tahansa, seuraava välitulos pitää kertoa vaihtoehdoilla.
		let vaihtoehtoja = BigInt(tila[maa]);
		// Siirretään tätä maata yksi pakasta pöydälle.
		let uusi = tila.concat();
		uusi[maa] -= 1;
		uusi[maa + 4] += 1;
		// Rekursiolla jatketaan.
		let t = tulos(uusi);
		summa.voitot += t.voitot * vaihtoehtoja;
		summa.tappiot += t.tappiot * vaihtoehtoja;
	}
	muisti[avain] = summa;
	return summa;
}

// Ratkaisun alussa pakassa on 13 jokaista maata ja esillä 0 jokaista maata.
let t = tulos([13, 13, 13, 13, 0, 0, 0, 0]);
return 100 * Number(t.voitot) / Number(t.voitot + t.tappiot);
})();

PetriKeckman [09.07.2022 03:12:44]

#

Ai Metabolix ehtikin ennen :) Olin juuri kirjoittamassa viestiä:
Himskattiin vaikeat osoitinmuuttujat! Simulointi hoituu taulukoilla, paitsi että ohjelmani täytyy olla virheellinen, sillä sain miljoonasta simuloinnista maksimissaan kuusi läpi.

program pasianssi;
TYPE kortit = 	1..52;
	maat  	=	1..4;
	poytaind	=	1..4;
VAR	lapimenot, peli	:	LongInt;
	poytakortit	:	ARRAY[1..4] OF kortit;
	pakka	:	ARRAY [1..52] OF kortit;
	ind		:	kortit;
	lapimeni	:	BOOLEAN;
	maxpeli	:	Longint;
function kortinmaa(kortti:kortit):maat; {palauttaa kortin 1..52 maan 1..4}
BEGIN
	kortinmaa:=(kortti-1) div 13+1;
END;
PROCEDURE alusta; {laitetaan taulukkoon 52 korttia, jotta taulukko voidaan sekoittaa}
VAR i	:	kortit;
BEGIN
	FOR i:=1 TO 52 DO
		pakka[i]:=i;
	lapimenot:=0;
	maxpeli:=1000000;
END;
PROCEDURE sekoitapakka;
VAR i,j, apu	: 	kortit;
BEGIN
	Randomize;
	FOR i:=1 TO 52 DO {vaihdetaan 52 kertaa korttipareja}
		BEGIN
			apu:= pakka[i];
			j:=Random(52)+1;
			pakka[i]:=pakka[j];
			pakka[j]:=apu;
		END;
END;
FUNCTION kaikkierimaata:BOOLEAN; {Onko taulukossa poytakortit kaikki erimaata?}
BEGIN
	IF ind<=49 THEN
	BEGIN
		IF ((kortinmaa(poytakortit[1])<>kortinmaa(poytakortit[2]))
			AND (kortinmaa(poytakortit[1])<>kortinmaa(poytakortit[3]))
			AND (kortinmaa(poytakortit[1])<>kortinmaa(poytakortit[4]))
			AND (kortinmaa(poytakortit[2])<>kortinmaa(poytakortit[3]))
			AND (kortinmaa(poytakortit[2])<>kortinmaa(poytakortit[4]))
			AND (kortinmaa(poytakortit[3])<>kortinmaa(poytakortit[4])))
			THEN
				BEGIN
					kaikkierimaata:=TRUE;
				END
			ELSE kaikkierimaata:=FALSE;
	END;
	IF ind=50 THEN
	BEGIN
		IF (kortinmaa(poytakortit[1])<>kortinmaa(poytakortit[2]))
			AND (kortinmaa(poytakortit[1])<>kortinmaa(poytakortit[3]))
			AND (kortinmaa(poytakortit[2])<>kortinmaa(poytakortit[3]))
			THEN
				BEGIN
					kaikkierimaata:=TRUE;
				END
			ELSE kaikkierimaata:=FALSE;
	END;
	IF ind=51 THEN
	BEGIN
		IF kortinmaa(poytakortit[1])<>kortinmaa(poytakortit[2])
			THEN
				BEGIN
					kaikkierimaata:=TRUE;
				END
			ELSE kaikkierimaata:=FALSE;
	END;
END;
PROCEDURE poistakortit(iind,jind:maat);
BEGIN
	poytakortit[iind]:=pakka[ind];
	ind:=ind+1;
	poytakortit[jind]:=pakka[ind];
	IF (ind>=51) THEN
	BEGIN
		lapimeni:=TRUE; {läpimeni}
		lapimenot:=lapimenot+1;
		WRITELN('Läpimeni');
	END;
END;
PROCEDURE poistasamatmaat;
VAR i,j,vika	:	poytaind;
BEGIN
	IF ind<=49 THEN vika:=4;
	IF ind=50 THEN vika:=3;
	IF ind=51 THEN vika:=2;

	FOR i:=1 TO vika DO {poistetaan kortit, mitkä ovat ekan kanssa samaa maata.}
		FOR j:=i+1 TO vika DO
			IF kortinmaa(poytakortit[i])=kortinmaa(poytakortit[j]) THEN
				poistakortit(i,j);
	FOR i:=2 TO vika DO {poistetaan kortit, mitkä ovat tokan kanssa samaa maata. "Tokan oikealla puolella"}
		FOR j:=i+1 TO 4 DO
			IF kortinmaa(poytakortit[i])=kortinmaa(poytakortit[j]) THEN
				poistakortit(i,j);
	IF kortinmaa(poytakortit[vika-1])=kortinmaa(poytakortit[vika]) THEN
				poistakortit(vika,vika+1);

END;
PROCEDURE pelaapasianssi;
VAR i	:	poytaind;
BEGIN
	{laitetaan neljä ensimmäistä korttia pöydälle}
	ind:=5; {osoittaa pakan päälimmäiseen korttiin}
	FOR i:=1 TO 4 DO poytakortit[i]:=pakka[i];
	REPEAT
		poistasamatmaat;
	UNTIL kaikkierimaata OR lapimeni;
END;
begin
	alusta;
	sekoitapakka;
	FOR peli:=1 TO maxpeli DO
		BEGIN
			pelaapasianssi;
			sekoitapakka;
		END;
	WRITELN('Lapimenoprosentti=', (100 * lapimenot / maxpeli):5);
end.

PetriKeckman [09.07.2022 04:44:10]

#

Tässä toinen

https://petke.info/pasianssi/

sen verta tylsä pasianssi, että sitä ei ehkä jaksa pelata läpi, mutta simulointiohjelman osasin jopa minä ehkä ohjelmoida. Sain läpimenoprosentiksi 1.756% Tälle voisi olla ehkä melkko helppa laskea tarkkakin arvo?

program pikkupasianssi;
CONST	peleja	=	100000000; {10 miljoonaa simulointia}
TYPE kortit = 	1..52;
VAR	pakka	:	ARRAY [1..52] OF kortit;
	eimennytlapi	:	BOOLEAN;
	tappioita, peli	:	LongInt;
	indeksi	:	kortit;
function arvo(kortti:kortit):kortit; {palauttaa kortin arvon}
BEGIN
	arvo:=((kortti-1) mod 13)+1;
END;
PROCEDURE alusta; {Laitetaan kortit pakkaan sekoitusta varten}
BEGIN
	Randomize;
	FOR indeksi:=1 TO 52 DO
		pakka[indeksi]:=indeksi;
	tappioita:=0;

END;
PROCEDURE sekoitapakka; {Vaihdetaan 52 korttia}
VAR i,j, apu	: 	kortit;
BEGIN
	FOR i:=1 TO 52 DO
		BEGIN
			apu:= pakka[i];
			j:=Random(52)+1;
			pakka[i]:=pakka[j];
			pakka[j]:=apu;
		END;
END;
PROCEDURE pelaa;
VAR pelaajanlaskuri: kortit;
BEGIN
	indeksi:=1;
	pelaajanlaskuri:=1;
	eimennytlapi:=FALSE;
	REPEAT
		IF arvo(pakka[indeksi])=pelaajanlaskuri THEN eimennytlapi:=TRUE;
		pelaajanlaskuri:=pelaajanlaskuri+1;
		IF pelaajanlaskuri=14 THEN pelaajanlaskuri:=1;
		indeksi:=indeksi+1;
	UNTIL (indeksi=52) OR eimennytlapi;
END;
begin
	alusta;
	FOR peli:=1 TO peleja DO
	BEGIN
		sekoitapakka;
		pelaa;
		IF eimennytlapi THEN tappioita:=tappioita+1;
	END;
	WRITELN('Läpimenoja=', peleja-tappioita,' kpl eli läpimenoprosentti=', 100*(peleja-tappioita)/peleja);
end.

Metabolix [09.07.2022 09:45:49]

#

PetriKeckman kirjoitti:

Simulointi hoituu taulukoilla, paitsi että ohjelmani täytyy olla virheellinen, sillä sain miljoonasta simuloinnista maksimissaan kuusi läpi.

En jaksanut ihan kaikkea lukea, mutta ainakin poistasamatmaat toimii luultavasti väärin: kommentit eivät vastaa toimintaa ja sekä toiminta että kommentit ovat virheelliset, yhdestä silmukasta puuttuu vika-muuttujan käyttö, ja kun ensimmäisen kortin kanssa samaa olevat on poistettu, seuraavissa silmukoissa on jo indeksit pielessä. Myös poistakortit on epäilyttävä ja parametrien tyyppi iind,jind:maat on selvästi väärä.

Harmi, että vaikka koodaat logiikan periaatteessa selkeillä nimillä, kriittisimmät asiat on nimetty epämääräisesti kuten ind (mikä ind?) ja pakka (joka kuitenkin sisältää ilmeisesti myös pöytäkortit).

Selkein tapa korttien poistoon on se, että ensin lasketaan jokaisen maan kortit ja sitten poistetaan ne maat, joita on enemmän kuin yksi. Koska maat on jo laskettu, uuden kortin voi nostaa heti eikä tarvitse ohjelmoida vielä yhtä välivaihetta poistamiseen. Kannattaa laittaa esillä olevat kortit ihan omaan taulukkoonsa, jolloin niitä on helpompi käsitellä pakasta erillään.

Käytännössä peli näyttää siis tältä (täydennä Maa, KortinMaa, Kortit, Pakka, PakkaTyhja, Nosta):

function PoistaKortit: Boolean;
var MaanMaara: Array [Maa] of Integer;
begin
  for i := 1 to 4 do MaanMaara[KortinMaa(Kortit[i])] := 0;
  for i := 1 to 4 do Inc(MaanMaara[KortinMaa(Kortit[i])]);
  for i := 1 to 4 do if (MaanMaara[KortinMaa(Kortit[i])] > 1 then begin
    PoistaKortit := True;
    if not PakkaTyhja then Kortit[i] := Nosta;
  end;
end;

function PelinTulos: Boolean;
begin
  while not PakkaTyhja do if not PoistaKortit then Break;
  PelinTulos := PakkaTyhja;
end;

Grez [09.07.2022 10:31:38]

#

Jäin miettimään, että jos pöydässä on kahta eri maata, kaksi kumpaakin, niin kumpikohan on parempi strategisesti valita, se jota on jäljellä enemmän vai se jota on jäljellä vähemmän. Tämähän on pelissä ainoa tilanne, jossa pelaajalla on päätäntävaltaa.

(Jos vastaava valintatilanne tulee niin, että toista maata on jäljellä vain yksi, niin silloin on ilman muuta selvää että sitä maata ei kannata valita, koska silloin peli ei voi mennä läpi.

Edit: Tai se taisikin olla niin, että riittää että pakka tyhjenee, vaikka pöytään jäisikin yksi kortti kutakin maata.)

Metabolix [09.07.2022 12:15:44]

#

Grez kirjoitti:

Jäin miettimään, että jos pöydässä on kahta eri maata, kaksi kumpaakin, niin kumpikohan on parempi strategisesti valita, se jota on jäljellä enemmän vai se jota on jäljellä vähemmän.

Totta, itse en edes huomioinut tätä vaihtoehtoa, koska Petrin kirjallisten sääntöjen mukaan ”poistetaan samaa maata olevat kortit” ja näin ollen poistin ne kaikki, mikä ei ollut ilmeisesti todellisten sääntöjen mukaista.

Edellisiin koodeihin tämä tarkoittaa siis, että korttien laskemisen jälkeen pitää ensin valita poistettava maa ja poistaa sitten vain kyseisen maan kortit.

Kun tämän korjaa, niin kulloinkin parhaalla valinnalla voi voittaa 10,00 %, enemmän jäljellä olevilla 9,94 %, satunnaisella noin 9,57 %, vähemmän jäljellä olevilla 9,23 % ja huonoimmalla valinnalla 9,08 %.

Tässä on vielä korjattu JS-koodi, josta voi valita laskettavan strategian. Tämän satunnaisuudessa on tietysti se puute, että välitulokset tallennetaan ja näin samoja satunnaisvalintoja saatetaan käyttää useaan kertaan.

(() => {
'use strict';
let kertoma = Array(53).fill().map((x, i, t) => t[i] = i ? t[i-1] * BigInt(i) : 1n);

let muisti = {};
function tulos(tila) {
	// Pakka tyhjä?
	if (tila[0] + tila[1] + tila[2] + tila[3] == 0) {
		return {voitot: 1n, tappiot: 0n};
	}

	// Dynaaminen ohjelmointi, alkeisversio: jos tämä tila on laskettu, palautetaan tulos muistista.
	let avain = tila.join(",");
	if (muisti[avain]) return muisti[avain];

	// Käsi täysi?
	if (tila[4] + tila[5] + tila[6] + tila[7] == 4) {
		// Enintään yksi joka maata? => Tappioiden määrä on pakan mahdollisten järjestysten määrä.
		if ((tila[4] | tila[5] | tila[6] | tila[7]) == 1) {
			return muisti[avain] = {voitot: 0n, tappiot: kertoma[tila[0] + tila[1] + tila[2] + tila[3]]};
		}
		// Muu määrä kuin 0 tai 2 jotain maata? => Vain yksi on poistettavissa.
		if ((tila[4] | tila[5] | tila[6] | tila[7]) != 2) for (let maa of [4, 5, 6, 7]) if (tila[maa] > 1) {
			tila[maa] = 0;
			return muisti[avain] = tulos(tila);
		}
		// Kahta maata, etsitään ne ja valitaan a = enempi.
		let a = 0, b = 3;
		while (tila[a + 4] <= 1) ++a;
		while (tila[b + 4] <= 1) --b;
		if (tila[a] < tila[b]) [a, b] = [b, a];

		// Strategiat:
		const strategia = ["huonoin", "vähempi", "random", "enempi", "paras"][4];
		switch (strategia) {
			case "random":
				tila[(Math.random() < 0.5 ? a : b) + 4] = 0;
				return muisti[avain] = tulos(tila);
			case "enempi":
				tila[a + 4] = 0;
				return muisti[avain] = tulos(tila);
			case "vähempi":
				tila[b + 4] = 0;
				return muisti[avain] = tulos(tila);
			default:
				let uusi = tila.concat();
				tila[a + 4] = 0;
				uusi[b + 4] = 0;
				let t = [tulos(tila), tulos(uusi)];
				let paras = t[0].voitot * t[1].tappiot < t[1].voitot * t[0].tappiot ? 1 : 0;
				return muisti[avain] = (strategia == "paras") ? t[paras] : t[paras ^ 1];
		}
	}

	// Käydään kaikki vaihtoehdot, mitä maata pakasta voi tulla.
	let summa = {voitot: 0n, tappiot: 0n};
	for (let maa of [0, 1, 2, 3]) if (tila[maa]) {
		// Koska seuraava kortti voi olla mikä tahansa, seuraava välitulos pitää kertoa vaihtoehdoilla.
		let vaihtoehtoja = BigInt(tila[maa]);
		// Siirretään tätä maata yksi pakasta käteen.
		let uusi = tila.concat();
		uusi[maa] -= 1;
		uusi[maa + 4] += 1;
		// Rekursiolla jatketaan.
		let t = tulos(uusi);
		summa.voitot += t.voitot * vaihtoehtoja;
		summa.tappiot += t.tappiot * vaihtoehtoja;
	}
	return muisti[avain] = summa;
}

let t = tulos([13, 13, 13, 13, 0, 0, 0, 0]);
print(100 * Number(t.voitot) / Number(t.voitot + t.tappiot));
})();

Vastaus

Muista lukea kirjoitusohjeet.
Tietoa sivustosta