Esitin täällä jo Numeropelini, missä oli tekoälyä eli pelipuun käsittelyä, mutta se oli apinoitu eli suurimmaksi osaksi copy/pastattu Amigan Pascalille tehdystä ohjelmasta, mikä taas oli copy/pastattu HY:ssa 1987 Tietorakenteet kurssille tehdystä harjoitustyöstä. Oli tarkoitus yrittää käyttää samaa ohjelmaa älykkään ristinolla pelin luomiseen, mutta totesin, että ei siitä mitään tule. On aloitettava uudestaan kokonaan tyhjältä pöydältä, missä pelipuuta käsitellään sitten rekursiivisesti.
Joskus 80-luvulla opiskellessani olisin voinut jotain osatakin, mutta olen nyt ihan alkeissa taas Pascalin käytössä. Jouduin aloittamaan ja omaksumaan osoitinmuuttujien käytön ihan alusta:
Program Ristinolla;
uses Crt;
CONST
maxind=20;
TYPE indtype = 1..maxind;
solmuos = ^solmu;
solmu = RECORD
arvo:Integer; {pelitilanteen arvo laiton x,y jälkeen}
{Yleensä siis nolla, koska olemme kiinnostuneita vain }
{voitosta tai tappiosta}
x :Indtype; {20x20 merkin laiton x ja y koordnaatat}
y :Indtype;
oikveli:solmuos; {saman tason muut mahdolliset siirrot}
END;
puu = ^puutaso;
puutaso = RECORD
ylataso:puu;
siirrot:solmuos;
parasarvo:INTEGER; {Ristinolla pelissä tutkitaan vain voittoja}
END;
VAR pelipuu : puu;
solmumuuttuja : solmuos;
PROCEDURE ALUSTA;
BEGIN
IF pelipuu = NIL THEN
BEGIN
writeln('pelipuu on NIL');
New(pelipuu);
New(solmumuuttuja);
pelipuu^.siirrot:=solmumuuttuja;
pelipuu^.siirrot^.x:=1; {yllä luotiin muuttujalle pelipuu osoitin puuhun, mikä on osoitin tietueeseen, }
{missä on siirrot sarake, mikä osoitta solmu tietueeseen, missä on}
{ x ja y sarake. SEKAVAA!!}
pelipuu^.siirrot^.y:=2;
Writeln(pelipuu^.siirrot^.x);
Writeln(pelipuu^.siirrot^.y);
END
END;
begin
ALUSTA;
end.Tässä projektissa olisi tarkoitus edetä pikku askel kerrallaan ja päätyä jonkinlaiseen ristinolla pelin tekoälyyn. Tällä hetkellä ajatuksenani on, että tekoäly ei millään tavalla analysoi pelipöytää muuta kuin mahdollisten voittojen osalta. Saa nähdä toimiiko idea...Kun siis pelipuun tyveen tulee alussa 20x20 - 1 pelaajan eri mahdollista ristin laittoa (ohjelma alkaa aina aloituksella, missä kone laittaa nollan kohtaan 10x10), sen jälkeen kolmos tasolla puussa onkin soluja jo 1 + (20x20-1) + (20x20-1)*(20x20-2)= 159 202 kpl Heh! Eipä taida tästä projektista tulla mitään, mutta testaan ennen kuin lyön kokonaan pyyhettä kehään. Siis tasolla neljä pitäisi käydä läpi sitten 159 202 * (20x20-3)=63 203 194 solua, jos nyt oikein järkeilin...
Varmaankin myös pelipöydän tilanne pitäisi toteuttaa dynaamisilla muuttujilla. Tällöinhän siinä ei alussa olisi kuin yksi alkio. Nyt pelipöytä on kylmästi 20x20 tauukko ja joka tasolla on siis (hieman) alle 400 mahdollista laittoa.
TYPE poyta = ^merkki;
merkki = RECORD
kumpi : SmalInt; {kumpi merkki?}
xkoord : SmalInt
ykoord : SmallInt;
END;TMS....
Mutta aloitan nyt toisella tapaa...
Ristinollapeli on nyt vasta siinä vaiheessa, että kone arpoo siirtonsa - tarkoitus oli luoda vasta käyttöliittymä, hiiren vasemman näppäimen lukua eli X:n laitto ja vähän koodia millä ohjelma huomaa, jos ruudukossa on jommalla kummalla viisi peräkkäin.
http://petke.info/kayttoliittyma.exe
uses graph, wincrt, winmouse;
const maxindex = 20; {Ruudukon koko on 20x20}
var gd,gm: integer; {Tarvitaan grafiikan alustukseen}
ch:char;
i,j:SmallInt;
mposx, mposy, state: longint;
x1,y1,x2,y2: SmallInt;
pelitilanne: ARRAY [1..maxindex,1..maxindex] OF SmallInt;
voittomerkki: SmallInt;
merkit : ARRAY [0..1] OF String;
PROCEDURE Nolla(x1,y1,x2,y2:SmallInt); {Piirtää nollan}
BEGIN
MoveTo(x1,y1);
Ellipse(x1+16,y1+12,0,360,15,11);
end;
PROCEDURE Risti(x1,y1,x2,y2:SmallInt); {Piirtää ristin}
BEGIN
MoveTo(x1,y1);
LineRel(32,24);
MoveTo(x2,y1);
LineRel(-32,24);
MoveTo(x1+1,y1+1);
LineRel(32,24);
MoveTo(x2+1,y1+1);
LineRel(-32,24);
end;
PROCEDURE piirra; {Tulostaa taulukon}
var ip,jp: SmallInt;
BEGIN
for ip:=1 to maxindex do
for jp:=1 to maxindex do
begin
x1:=(ip-1)*32;
y1:=(jp-1)*24;
x2:=ip*32;
y2:=jp*24;
IF (pelitilanne[ip,jp]=1) THEN Risti(x1,y1,x2,y2);
IF (pelitilanne[ip,jp]=0) THEN Nolla(x1,y1,x2,y2);
Rectangle(x1,y1,x2,y2);
end;
end;
FUNCTION viisiperakkain(i,j,merkki,xsuunta,ysuunta: SmallInt):BOOLEAN; {tutkii ]
{onko viisiperäkkäin}
{merkkiä 'merkki' ruudusta i,j suuntiin, missä koordinaatteja kasvatetaan xsuunnan ja ysuunnan verran}
VAR x,y,lkm:SmallInt;
BEGIN
x:=i;
y:=j;
lkm:=0;
REPEAT
IF pelitilanne[x,y]=merkki THEN
BEGIN
lkm:=lkm+1;
y:=y+ysuunta;
x:=x+xsuunta;
END;
UNTIL ((lkm=5) OR (x>maxindex) OR (y>maxindex) OR (x<1) OR (y<1) OR (pelitilanne[x,y]<>merkki));
IF lkm=5 THEN BEGIN
viisiperakkain:=TRUE;
voittomerkki:=merkki;
END
ELSE viisiperakkain:=FALSE;
END;
FUNCTION voitto: BOOLEAN; {tutkitaan onko pelipöydällä voittotilannetta}
var i,j,merkki: SmallInt;
voittoapu: BOOLEAN;
BEGIN
voittoapu:=FALSE; {Oletetaan, että pelilaudalla ei ole viittä peräkkäin}
for merkki:=0 TO 1 DO {Pelilaudalla 0 merkitsee nollaa ja 1 ristiä. Tutkitaan erikseen molemmat merkit}
BEGIN
FOR i:=1 TO Maxindex DO
FOR j:=1 TO Maxindex DO
BEGIN
IF ((viisiperakkain(i, j, merkki,-1,1)) OR (viisiperakkain(i, j, merkki,-1,0)) OR (viisiperakkain(i, j, merkki,-1,-1)) OR (viisiperakkain(i, j, merkki,0,-1)) OR (viisiperakkain(i, j, merkki,1,-1)) OR (viisiperakkain(i, j, merkki,-1,0)) OR (viisiperakkain(i,j, merkki,-1,-1)) OR (viisiperakkain(i, j, merkki,0,1))) THEN
BEGIN
voittoapu:=TRUE;
voittomerkki:=merkki
END;
END;
END;
voitto:=voittoapu;
END;
PROCEDURE alusta; {Alustetaan grafiikka, hiiri, satunnaislukugeneraattori ja laitetaan peli kentälle nolla}
BEGIN
gd := d4bit;
gm := m640x480;
initgraph(gd,gm,'');
initmouse;
for i:=1 TO maxindex do
for j:=1 TO maxindex do
pelitilanne[i,j]:=2;
pelitilanne[10,10]:=0; {kone laittaa 0:n about keskelle pelikenttää}
Randomize;
piirra;
merkit[0]:='O';
merkit[1]:='X'
end;
PROCEDURE laitaristi; {Missä kohti pelaaaja painoi? - siihen risti}
var Reali, Realj: Real;
sisalto: SmallInt;
begin
REPEAT
repeat until lpressed;
getmousestate(mposx,mposy,state);
Reali:=Int(mposx/32);
Realj:=Int(mposy/24);
sisalto:=pelitilanne[trunc(Reali)+1,trunc(Realj)+1];
if sisalto=2 THEN pelitilanne[trunc(Reali)+1,trunc(Realj)+1]:=1;
repeat until not lpressed;
UNTIL sisalto=2;
end;
PROCEDURE laitanolla; {Käyttöliittymän tekoa tutkivassa Demossa vain arotaan koneen merkin paikka}
BEGIN
pelitilanne[Random(Maxindex)+1,Random(Maxindex)+1]:=0;
END;
begin
alusta;
repeat
if Keypressed THEN ch:= Readkey;
repeat until lpressed;
if not voitto THEN BEGIN
laitaristi;
piirra;
END;
repeat until not lpressed;
if not voitto THEN
BEGIN
laitanolla;
piirra;
END;
until (ch = #27) OR voitto;
WRITELN(merkit[voittomerkki], ' VOITTI!');
ch:=Readkey;
end.Väliaikatiedote ristinollatekoälystä.
Yritän kuvallani selventää käyttämäni pelipuun rakennetta:
https://petke.info/osoittimet2.png
Kuten näette pelipuu osoittaa alimpaan tasoon (EDIT: Alussa ei, mutta rakentelun loppuvaiheessa käsittääkseni osoittaa) (EDIT2: Heh! Mietin uudestaan...Taitaa pelipuu osoittaa sittenkin pelipuun ylimpään tasoon. Tietueen kentän osoittimen nimi 'ylataso' on vain väärä ja nuolet kuvassa väärään suuntaan - sori, oon vähän sekaisin, mutta en viitti poistaa tätä viestiä.). Vähän epäortodoksinen tietorakenne, mutta tällä nyt mennään...Pelipuun rakenne on apinoitu numeropelistä. En tässä ohjelmassa edes käytä puutaso tietueen 'parasarvo' saraketta, vaan pelipuun rakentelu päättyy heti kun saavutetaan koneen voittotilanne. Tämä saattaa olla paha logiikkavirhe! Täytyy miettiä, huomenna...
Ohjelma ei vielä ole kovin hyvin kommentoitu, mutta kommentoin paremmin, huomenna...
Program Ristinolla;
uses winmouse,graph, wincrt;
CONST
maxind=20;
TYPE indtype = 1..maxind;
solmuos = ^solmu;
solmu = RECORD
arvo:Integer; {pelitilanteen arvo laiton x,y jälkeen. Saa joko arvon -32768 jos pelaaja}
{voittaa tai arvon 32767 jos kone voittaa, tao arvon nolla jos kumpikaan ei voita}
x :SmallInt; {20x20 ruudukon x ja y koordnaatat}
y :SmallInt;
oikveli:solmuos; {saman tason muut mahdolliset siirrot}
END;
puu = ^puutaso;
puutaso = RECORD
ylataso:puu;
siirrot:solmuos;
parasarvo:INTEGER; {Ristinolla pelissä tutkitaan vain voittoja}
END;
VAR pelipuu, apuylataso : puu;
solmumuuttuja : solmuos;
taso : SmallInt;
pelitilanne: ARRAY [1..maxind,1..maxind] OF SmallInt; {0=nolla, 1=risti ja 2=tyhjä}
i,j,voittomerkki,maxtaso : SmallInt;
olivoitto : BOOLEAN;
gd,gm: integer;
ch:char;
merkit: ARRAY [0..1] OF char;
mposx, mposy, state: longint;
x1,y1,x2,y2: SmallInt;
siirrax, siirray : indtype;
PROCEDURE Nolla(x1,y1,x2,y2:SmallInt);
BEGIN
MoveTo(x1,y1);
Ellipse(x1+16,y1+12,0,360,15,11);
end;
PROCEDURE Risti(x1,y1,x2,y2:SmallInt);
BEGIN
MoveTo(x1,y1);
LineRel(32,24);
MoveTo(x2,y1);
LineRel(-32,24);
MoveTo(x1+1,y1+1);
LineRel(32,24);
MoveTo(x2+1,y1+1);
LineRel(-32,24);
end;
PROCEDURE piirra;
var ip,jp: SmallInt;
BEGIN
for ip:=1 to maxind do
for jp:=1 to maxind do
begin
x1:=(ip-1)*32;
y1:=(jp-1)*24;
x2:=ip*32;
y2:=jp*24;
IF (pelitilanne[ip,jp]=1) THEN Risti(x1,y1,x2,y2);
IF (pelitilanne[ip,jp]=0) THEN Nolla(x1,y1,x2,y2);
Rectangle(x1,y1,x2,y2);
end;
end;
PROCEDURE ALUSTA;
BEGIN
gd := d4bit;
gm := m640x480;
initgraph(gd,gm,'');
initmouse;
IF pelipuu = NIL THEN
BEGIN
New(pelipuu);
New(solmumuuttuja);
pelipuu^.siirrot:=solmumuuttuja;
pelipuu^.siirrot^.x:=10; {yllä luotiin muuttujalle pelipuu osoitin puuhun, mikä on osoitin tietueeseen, }
{missä on siirrot sarake, mikä osoitta solmu tietueeseen, missä on x ja y sarake. SEKAVAA!!}
pelipuu^.siirrot^.y:=10;
pelipuu^.ylataso:=NIL;
END;
FOR i:=1 TO maxind DO
FOR j:=1 TO maxind DO
pelitilanne[i,j]:=2;
pelitilanne[10,10]:=0;
merkit[0]:='0';
merkit[1]:='X';
piirra;
maxtaso:=3;
END;
FUNCTION viisiperakkain(i,j,merkki,xsuunta,ysuunta: SmallInt):BOOLEAN;
{palauttaa arvon TRUE jos koordinaateista suuntaan xsuunta, ysuunta löytyy viisi peräkkäin}
VAR x,y,lkm:SmallInt;
BEGIN
x:=i;
y:=j;
lkm:=0;
REPEAT
IF pelitilanne[x,y]=merkki THEN
BEGIN
lkm:=lkm+1;
y:=y+ysuunta;
x:=x+xsuunta;
END;
UNTIL ((lkm=5) OR (x>maxind) OR (y>maxind) OR (x<1) OR (y<1) OR (pelitilanne[x,y]<>merkki));
IF lkm=5 THEN BEGIN
viisiperakkain:=TRUE;
voittomerkki:=merkki;
END
ELSE viisiperakkain:=FALSE;
END;
FUNCTION voitto: BOOLEAN; {tutkitaan onko pelipöydällä voittotilannetta}
var i,j,merkki: SmallInt;
VAR voittoapu: BOOLEAN;
BEGIN
voittoapu:=FALSE;
FOR merkki:=0 TO 1 DO
FOR i:=1 TO maxind DO
FOR j:=1 TO maxind DO
BEGIN
{tämä ehtolause on tosi pitkä.............}
IF ((viisiperakkain(i, j, merkki,-1,1)) OR (viisiperakkain(i, j, merkki,-1,0)) OR (viisiperakkain(i, j, merkki,-1,-1)) OR (viisiperakkain(i, j, merkki,0,-1)) OR (viisiperakkain(i, j, merkki,1,-1)) OR (viisiperakkain(i, j, merkki,-1,0)) OR (viisiperakkain(i,j, merkki,-1,-1)) OR (viisiperakkain(i, j, merkki,0,1))) THEN
BEGIN
voittomerkki:=merkki;
voittoapu:=TRUE;
END;
END;
voitto:=voittoapu;
END;
PROCEDURE tuhoakokopuu; {tuhotaan kaikki osoitinmuuttujat eli koko puu, ettei se jää muistiin 'roikkumaan'.}
{TÄMÄ ALIOHJELMA ON VARMASTI VIRHEELLINEN...VIELÄ. EN HALLITSE OSOITTIMIA...VEILÄ!}
VAR osoitin: puu;
apuoikea, oikea : solmuos;
BEGIN
osoitin:=pelipuu; {osoittaa pelipuun alimpaan tasoon eli riviin siirtoja}
REPEAT
apuylataso:=pelipuu; {otetaan osoitin ylätasoon talteen}
oikea:=pelipuu^.siirrot^.oikveli;
REPEAT
apuoikea:= oikea;
DISPOSE(oikea);
oikea:=apuoikea
UNTIL (apuoikea = NIL);
oikea:=osoitin^.siirrot^.oikveli;
UNTIL (osoitin = NIL);
END;
FUNCTION tasoparillinen: BOOLEAN;
BEGIN
tasoparillinen:=(taso MOD 2=0)
END;
PROCEDURE konesiirtaa;
VAR olikoneenvoitto: BOOLEAN; {jos pelipuun rakentelussa törmätään koneen voittotilanteeseen, niin otetaan siirtotalteen}
BEGIN {rakennetaan pelipuuta ja valitaan seuraava siirto. Kone valitse lähimmän haaran, mikä johtaa voittoon}
Writeln('odota mietin...');
taso:=1;
olivoitto:=FALSE;
olikoneenvoitto:=FALSE;
{Tehdään pelipuun tasoja maxtaso verran rivi eli oikeitten velien jono ja pelipuu oosittajien pino, missä kaikki mahdolliset siirrot}
tuhoakokopuu; {tuhotaan ensin koko edellisen pelitilanteen pelipuupuu ja aletaan rakentamaan uutta}
new(pelipuu);
REPEAT {käydään kaikki mahdoolliset laitot läpi}
FOR i:=1 TO maxind DO
FOR j:=1 TO maxind DO
IF (pelitilanne[i,j] = 2) THEN {jos kohdassa i,j ei ole merkkiä siihen voi kone laittaa 0:n tai pelaaja 1:en}
BEGIN
New(solmumuuttuja);
pelipuu^.siirrot^.x:=i;
pelipuu^.siirrot^.y:=j;
pelipuu^.siirrot^.oikveli:=NIL;
IF tasoparillinen THEN pelitilanne[i,j]:=1 ELSE pelitilanne[i,j]:=0;
IF voitto THEN BEGIN
IF tasoparillinen THEN pelipuu^.siirrot^.arvo:=-32768 ELSE BEGIN
pelipuu^.siirrot^.arvo:=32767;
siirrax:=i;
siirray:=j;
olikoneenvoitto:=TRUE;
END;
END
ELSE
pelipuu^.siirrot^.arvo:=0; {ei johtanut voittoon. Solmun arvo on merkityksetön nolla}
pelipuu^.siirrot^.oikveli:=solmumuuttuja;
pelitilanne[i,j]:=2; {tutkittiin vain saavuttiko pelaaja tai kone voiton. palautetaan tyhja paikka}
END;
{aletaan rakentamaan seuraavaa tasoa}
apuylataso:=pelipuu; {otetaan osoitin edellä rakennettuun puun tasoon talteen,}
{jotta se voidaan laittaa seuraavan tason ylätasoksi}
new(pelipuu);
pelipuu^.ylataso:=apuylataso;
taso:=taso+1;
UNTIL ((taso = maxtaso) OR olikoneenvoitto);
pelitilanne[siirrax, siirray]:=0;
END;
PROCEDURE laitaristi; {Missä kohti pelaaaja painoi? - siihen risti}
var Reali, Realj: Real;
sisalto: SmallInt;
begin
REPEAT
repeat until lpressed;
getmousestate(mposx,mposy,state);
Reali:=Int(mposx/32);
Realj:=Int(mposy/24);
sisalto:=pelitilanne[trunc(Reali)+1,trunc(Realj)+1];
if sisalto=2 THEN BEGIN
pelitilanne[trunc(Reali)+1,trunc(Realj)+1]:=1;
New(solmumuuttuja);
solmumuuttuja^.x:=SmallInt(trunc(Reali));
solmumuuttuja^.y:=SmallInt(trunc(Realj));
IF voitto THEN solmumuuttuja^.arvo:=-32768 {pelaaja voittaa siirrolla x y}
ELSE solmumuuttuja^.arvo:=0;
pelipuu^.siirrot^.oikveli:=solmumuuttuja;
END;
repeat until not lpressed;
UNTIL sisalto=2;
END;
begin
repeat;
alusta;
repeat
if Keypressed THEN ch:= Readkey;
repeat until lpressed;
if not voitto THEN
BEGIN
laitaristi;
piirra;
END;
repeat until not lpressed;
if not voitto THEN
BEGIN
konesiirtaa;
piirra;
END;
until (ch = #27) OR voitto;
WRITELN(merkit[voittomerkki], ' VOITTI!');
ch:=Readkey;
UNTIL ((ch=#28) or olivoitto);
end.Ohjelma kääntyy ilman virheilmoituksia, mutta tulee ajoaikaiset virheilmoitukset heti oman X:n laiton jälkeen pelipöydälle, kun kone alkaa miettiä siirtoaan:
Ohjelma kaatuu kirjoitti:
odota mietin...
Runtime error 204 at $0040545B
$0040545B
$0040545B
$00401E52
$0040229B
$004080D7
Ilmiselvästi siis osoittimien käsittelystä. Yritin tuhota käyttämäni pelipuun aina ennen seuraavan rakentamista. Yritin myös laittaa kommentiksi aliohjelman kutsun, eli etten kutsuisikaan solmuja tuhoavaa aliohjelmaa. Tällöin virheilmoituksia tuli kaksi vähemmän.
Varmasti joku Ohjelmointiputkalainen näkee heti mikä menee ihan persiilleen. Olisi kiva, jos jaksaisitte antaa jotain neuvoja. Tehdään ristinollapeli yhteistyössä :) Yleensähän koodailu on yksinäistä nörtin puurtamista.
Mullahan oli logiikka ihan pielessä! :) Valitsin koneen laiton x ja y koordinaateiksi viimeisimmän voittoon johtaneen siirron koordinaatat, kun pitää tietysti selata puuta ylöspäin tähän tapaan:
PROCEDURE etsiekasiirto;
VAR osoitin: puu;
{selataan pelipuuta niin kaun kunnes päästään ensimmäiseen tasoon ja valitaan sieltä x ja y koordinaatat}
BEGIN
osoitin:=pelipuu;
REPEAT
osoitin:=osoitin^.ylataso;
UNTIL (osoitin^.ylataso = NIL);
siirrax:=osoitin^.siirrot^.x;
siirray:=osoitin^.siirrot^.y;
END;Väliraportti. Kyllä tästä ristinolla pelistä voisi vielä ehkä jotain tullakin! :)
https://petke.info/ristinolla7.exe
Nyt sillä voi jo pelata, vaikka ohjelma on toooodella hiiiidaaas ja silti se on voitettavissa tosi helposti. Eli todellisuudessa sen tekoäly ei toimi! :( Mutta en anna vielä periksi.
Ne jotka peliä kokeilevat kannattaa samalla tehdä jotain muuta eikä tuijottaa vaan pelipöytää. Peli muuttuu pelin edetessä vain entistä hitaammaksi. Aluksi tutkittava alue on pieni, mutta mitä useampi merkki ruudukossa on, sitä laajempi on tutkittava alue. :( Jokin muukin syy ongelmaan täytyy kyllä olla. Täytyy tutkia syitä...joskus.
Ristinolla ohjelma tulosti kirjoitti:
E:\ohjelmointiputka\ristinolla>ristinolla7
Odota, mietin. Kauan......
Sori, ettõ mietin naaaiiin kauan :( 1.20000000000000000000E+0001 sekuntia.
No niin! Sinun vuoro
Odota, mietin. Kauan......
Sori, ettõ mietin naaaiiin kauan :( 4.90000000000000000000E+0001 sekuntia.
No niin! Sinun vuoro
Odota, mietin. Kauan......
Sori, ettõ mietin naaaiiin kauan :( 1.71000000000000000000E+0002 sekuntia.
No niin! Sinun vuoro
Odota, mietin. Kauan......
Sori, ettõ mietin naaaiiin kauan :( 5.15000000000000000000E+0002 sekuntia.
No niin! Sinun vuoro
X VOITTI!
Olin käsittänyt numeropelin tekoälyn tietorakenteet ja algoritmit täysin väärin. Tuo ylemmässä viestissä ollut kuva oli melko lailla päin prinkkalaa. Oleellista tässä tavassa käsitellä pelipuuta on se, että koko pelipuuta ei rakenneta kerralla, vaan mennään perille saakka lehtisolmuun tai kunnes tasoja on yhtäpaljon kuin maxtaso. Tällöinhän muistin tarve on minimaalisen pieni verrattuna siihen tapaan, missä rakennetaan pelipuu ensin kokonaan. Muistin tarve on yksinkertaisesti verrannollinen siihen, kuinka monta siirtoa eteenpäin kone miettii. En tiedä: voi jopa olla, että aikoinaan HY:ssa kehitin kätsyn uuden tavan käsitellä pelipuuta, kun en rekursiota osannut :) Tosin en tiedä rakennetaanko rekuriossakaan koko pelipuuta ensin - ei taideta.
Ohjelman ajan tarve toki kasvaa tähtitieteelliseksi 20x20 ruudukossa nopeasti, vaikka kaikkia 20x20 ruudukon paikkoja ei käsitelläkään, vaan oletuksena on, että X tai O laitetaan väli-muuttujan päähän jo vallatusta pelialueesta.
Ohjelmalistaus on niin pitkä, että en tiedä onko sitä tarkoituksenmukaista täällä julkaista. yp ottakoon pois, jos katsoo, että on liian pitkä ja että kannattaisi julkaista vasta sitten, kun ohjelma todella toimii.
Program Ristinolla;
uses winmouse,graph, wincrt,math,sysutils,DateUtils;
CONST
maxind=20;
TYPE indtype = 1..maxind;
solmuos = ^solmu;
solmu = RECORD
arvo:LongInt; {pelitilanteen arvo laiton x,y jälkeen. Saa joko arvon -32768 jos pelaaja}
{voittaa tai arvon 32767 jos kone voittaa, tai arvon nolla jos kumpikaan ei voita}
x :SmallInt; {20x20 ruudukon x ja y koordnaatat}
y :SmallInt;
oikveli:solmuos; {saman tason muut mahdolliset siirrot}
END;
puu = ^puutaso;
puutaso = RECORD
ylataso:puu;
siirrot:solmuos;
parasarvo:INTEGER; {Ristinolla pelissä tutkitaan vain voittoja}
END;
laittos = ^laitto; {lista laitoille, jotta nopeasti löydetään mix, miny,maxx ja maxy}
laitto = RECORD
x: SmallInt;
y: SmallInt;
seur: laittos;
END;
VAR pelipuu : puu;
kayttamattomat: puu; {Solmuja ei tuhota ja luoda yhtenään, vaan laitetaan ja}
{otetaan kayttamattomat listaan}
solmumuuttuja: solmuos;
kayttamattsolmut: solmuos;
laitot, apulaittoso , alku: laittos;
taso : SmallInt;
pelitilanne,alkutilanne: ARRAY [1..maxind,1..maxind] OF SmallInt; {0=nolla, 1=risti ja 2=tyhjä}
i,j,voittomerkki,maxtaso : SmallInt;
olivoitto : BOOLEAN;
gd,gm: integer;
ch:char;
merkit: ARRAY [0..1] OF char;
mposx, mposy, state: longint;
x1,y1,x2,y2,x,y: SmallInt;
ero : SmallInt; {ei kannata tutkia koko ruudukkoa, vaan minx-ero,maxxx+ero jne...}
now1, now2 , s : TDateTime;
PROCEDURE Nolla(x1,y1,x2,y2:SmallInt);
BEGIN
MoveTo(x1,y1);
Ellipse(x1+16,y1+12,0,360,15,11);
end;
PROCEDURE Risti(x1,y1,x2,y2:SmallInt);
BEGIN
MoveTo(x1,y1);
LineRel(32,24);
MoveTo(x2,y1);
LineRel(-32,24);
MoveTo(x1+1,y1+1);
LineRel(32,24);
MoveTo(x2+1,y1+1);
LineRel(-32,24);
end;
PROCEDURE piirra;
var ip,jp: SmallInt;
BEGIN
for ip:=1 to maxind do
for jp:=1 to maxind do
begin
x1:=(ip-1)*32;
y1:=(jp-1)*24;
x2:=ip*32;
y2:=jp*24;
IF (pelitilanne[ip,jp]=1) THEN Risti(x1,y1,x2,y2);
IF (pelitilanne[ip,jp]=0) THEN Nolla(x1,y1,x2,y2);
Rectangle(x1,y1,x2,y2);
end;
end;
procedure tulostalaitot;
begin
writeln('laitot x ja y:');
laitot:=alku;
WHILE (laitot^.seur<>NIL) DO BEGIN
WRITELN(laitot^.x:6,laitot^.y:6);
laitot:=laitot^.seur;
END;
end;
PROCEDURE ALUSTA;
BEGIN
gd := d4bit;
gm := m640x480;
initgraph(gd,gm,'');
initmouse;
New(pelipuu);
New(solmumuuttuja);
pelipuu^.siirrot:=solmumuuttuja;
pelipuu^.siirrot^.x:=10; {yllä luotiin muuttujalle pelipuu osoitin puuhun, mikä on osoitin tietueeseen, }
{missä on siirrot sarake, mikä osoitta solmu tietueeseen, missä on x ja y sarake. SEKAVAA!!}
pelipuu^.siirrot^.y:=10;
pelipuu^.ylataso:=NIL;
pelipuu^.parasarvo:=0;
pelipuu^.siirrot^.oikveli:=NIL;
new(laitot);
new(alku);
alku:=laitot;
laitot^.x:=10;
laitot^.y:=10;
laitot^.seur:=NIL;
{tulostalaitot;}
FOR i:=1 TO maxind DO
FOR j:=1 TO maxind DO BEGIN
pelitilanne[i,j]:=2;
alkutilanne[i,j]:=2;
END;
pelitilanne[10,10]:=0;
alkutilanne[10,10]:=0;
merkit[0]:='0';
merkit[1]:='X';
piirra;
maxtaso:=5;
ero:=2;
kayttamattomat:=NIL;
kayttamattsolmut:=NIL;
olivoitto:=false;
END;
{pelitilannetta ei kannata tarkastella koko laudalta vaan alueelta MIN(0:n laitot tai X:n laitot) -5 TO MIN(0:n laitot tai X:n laitot)+5}
FUNCTION pieninx: SmallInt;
VAR pieninapu : SmallInt;
BEGIN
pieninapu:=9999;
laitot:=alku;
WHILE (laitot^.seur<>NIL) DO BEGIN
pieninapu:=Min(pieninapu,laitot^.x);
laitot:=laitot^.seur;
END;
pieninapu:=pieninapu-ero;
if pieninapu < 1 then pieninapu:=1;
pieninx:=pieninapu;
END;
FUNCTION suurinx: SmallInt;
VAR suurinapu : SmallInt;
BEGIN
suurinapu:=-9999;
laitot:=alku;
WHILE (laitot^.seur<>NIL) DO BEGIN
suurinapu:=Max(suurinapu,laitot^.x);
laitot:=laitot^.seur;
END;
{if suurin>=(21-ero) THEN suurin:=20-ero;}
suurinapu:=suurinapu+ero;
IF suurinapu>20 THEN suurinapu:=20;
suurinx:=suurinapu;
END;
FUNCTION pieniny: SmallInt;
VAR pieninapu : SmallInt;
BEGIN
pieninapu:=9999;
laitot:=alku;
WHILE (laitot^.seur<>NIL) DO BEGIN
pieninapu:=Min(pieninapu,laitot^.y);
laitot:=laitot^.seur;
END;
{if pienin<=ero+1 THEN pienin:=ero;}
pieninapu:=pieninapu-ero;
if pieninapu<1 THEN pieninapu:=1;
pieniny:=pieninapu;
END;
FUNCTION suuriny: SmallInt;
VAR suurinapu : SmallInt;
BEGIN
suurinapu:=-9999;
laitot:=alku;
WHILE (laitot^.seur<>NIL) DO BEGIN
suurinapu:=Max(suurinapu,laitot^.y);
laitot:=laitot^.seur;
END;
{IF suurin>=21-ero THEN suurin:=20-ero;}
suurinapu:=suurinapu+ero;
IF suurinapu>20 then suurinapu:=20;
suuriny:=suurinapu;
END;
FUNCTION viisiperakkain(i,j,merkki,xsuunta,ysuunta: SmallInt):BOOLEAN;
{palauttaa arvon TRUE jos koordinaateista suuntaan xsuunta, ysuunta löytyy viisi peräkkäin}
VAR x,y,lkm:SmallInt;
BEGIN
x:=i;
y:=j;
lkm:=0;
REPEAT
IF pelitilanne[x,y]=merkki THEN
BEGIN
lkm:=lkm+1;
y:=y+ysuunta;
x:=x+xsuunta;
END;
UNTIL ((lkm=5) OR (x>maxind) OR (y>maxind) OR (x<1) OR (y<1) OR (pelitilanne[x,y]<>merkki));
IF lkm=5 THEN BEGIN
viisiperakkain:=TRUE;
voittomerkki:=merkki;
END
ELSE viisiperakkain:=FALSE;
END;
FUNCTION voitto: BOOLEAN; {tutkitaan onko pelipöydällä voittotilannetta}
var i,j,merkki: SmallInt;
VAR voittoapu: BOOLEAN;
BEGIN
voittoapu:=FALSE;
FOR merkki:=0 TO 1 DO
FOR i:=1 TO maxind DO
FOR j:=1 TO maxind DO
BEGIN
{tämä ehtolause on tosi pitkä.............}
IF ((viisiperakkain(i, j, merkki,-1,1)) OR (viisiperakkain(i, j, merkki,-1,0)) OR (viisiperakkain(i, j, merkki,-1,-1)) OR (viisiperakkain(i, j, merkki,0,-1)) OR (viisiperakkain(i, j, merkki,1,-1)) OR (viisiperakkain(i, j, merkki,-1,0)) OR (viisiperakkain(i,j, merkki,-1,-1)) OR (viisiperakkain(i, j, merkki,0,1))) THEN
BEGIN
voittomerkki:=merkki;
voittoapu:=TRUE;
END;
END;
voitto:=voittoapu;
END;
FUNCTION analysoipelitilannekoneenkannalta: Integer;
VAR palauta : SmallInt;
BEGIN
palauta:=0;
if (voitto) THEN BEGIN
IF (voittomerkki=1) THEN palauta:=32767
ELSE palauta:=-32768;
END;
analysoipelitilannekoneenkannalta:=palauta;
END;
FUNCTION analysoipelitilannepelaajankannalta: Integer;
VAR palauta : SmallInt;
BEGIN
palauta:=0;
if (voitto) THEN BEGIN
IF (voittomerkki=1) THEN palauta:=32767
ELSE palauta:=-32768;
END;
analysoipelitilannepelaajankannalta:=palauta;
END;
FUNCTION tasoparillinen: BOOLEAN;
BEGIN
tasoparillinen:=(taso MOD 2=0)
END;
FUNCTION koneenvuoro :BOOLEAN;
BEGIN
IF TASOPARILLINEN THEN koneenvuoro:=FALSE;
END;
PROCEDURE KONESIIRTAA;
VAR alkuindx,alkuindy:indtype;
pelipuu,
uusitaso:puu;
pojat:solmuos;
parasindx,parasindy:indtype;
PROCEDURE PERULAUTATILANNE(siirtox,siirtoy:indtype);
BEGIN
pelitilanne[siirtox,siirtoy]:=alkutilanne[siirtox,siirtoy];
END;
PROCEDURE TUHOATASOSOLMU(VAR os:puu);
BEGIN
os^.ylataso:=kayttamattomat;
kayttamattomat:=os;
END;
PROCEDURE UUSITASOSOLMU(VAR os:puu);
BEGIN
IF kayttamattomat=NIL THEN NEW(os)
ELSE BEGIN
os:=kayttamattomat;
kayttamattomat:=kayttamattomat^.ylataso;
os^.ylataso:=NIL;
END;
END;
PROCEDURE UUSISOLMU(VAR os:solmuos);
BEGIN
IF kayttamattsolmut=NIL THEN NEW(os)
ELSE
BEGIN
os:=kayttamattsolmut;
kayttamattsolmut:=kayttamattsolmut^.oikveli;
os^.oikveli:=NIL;
END;
END;
PROCEDURE TUHOASOLMU(VAR os:solmuos);
BEGIN
os^.oikveli:=kayttamattsolmut;
kayttamattsolmut:=os;
END;
PROCEDURE RAKENNASEURAAVATASO;
VAR solmu,vika:solmuos;
indx, indy : Smallint;
BEGIN
{writeln('RAKENNASEURAAVA TASO');}
pojat:=NIL;
taso:=taso+1;
FOR indx:=pieninx TO suurinx DO
BEGIN
FOR indy:=pieniny TO suuriny DO
BEGIN
{write('1');}
IF pelitilanne[indx,indy]=2 THEN
BEGIN
UUSISOLMU(solmu);
{writeln('TEHDAAN UUSISOLMU');}
IF koneenvuoro THEN
solmu^.arvo:=pelipuu^.siirrot^.arvo+analysoipelitilannekoneenkannalta
ELSE solmu^.arvo:=pelipuu^.siirrot^.arvo-analysoipelitilannepelaajankannalta;
solmu^.x:=indx;
solmu^.y:=indy;
IF pojat=NIL THEN { Vasta ensimmäinen solmu jonoon }
BEGIN
pojat:=solmu;
vika:=pojat;
END
ELSE
BEGIN
vika^.oikveli:=solmu;
solmu^.oikveli:=NIL;
vika:=solmu;
END;
END;
END;
END;
IF pojat=NIL THEN { Ei päästy enää jatkamaan eli päädyttiin }
BEGIN { lehtisolmuun, jonka arvo kerrotaan kymme- }
taso:=taso-1;{ nellä, koska se on pelin päätös solmu }
{Tällaista tilannetta ei kyllä tule ristinollassa, eli että ruudukko olisi täysi}
{, mutta koodi on copy/pastattu numeropelistä :)}
{WRITELN('taalla pojat=nil');}
pelipuu^.siirrot^.arvo:=pelipuu^.siirrot^.arvo*10;
END
ELSE
BEGIN
UUSITASOSOLMU(uusitaso);
uusitaso^.ylataso:=pelipuu;
uusitaso^.siirrot:=pojat;
IF TASOPARILLINEN THEN uusitaso^.parasarvo:= -32768
ELSE uusitaso^.parasarvo:= 3276;
pelipuu:=uusitaso;
END;
END;
PROCEDURE PURAPUUTA;
PROCEDURE POISTASOLMU;
VAR apusolmu:solmuos;
arvo:Integer;
BEGIN
arvo:=pelipuu^.siirrot^.arvo;
IF TASOPARILLINEN THEN
BEGIN IF arvo>pelipuu^.parasarvo THEN
BEGIN
pelipuu^.parasarvo:=arvo;
IF taso=2 THEN BEGIN
parasindx:=pelipuu^.siirrot^.x;
parasindy:=pelipuu^.siirrot^.y;
END;
END;
END
ELSE
IF arvo<pelipuu^.parasarvo THEN pelipuu^.parasarvo:=arvo;
apusolmu:=pelipuu^.siirrot;
pelipuu^.siirrot:=pelipuu^.siirrot^.oikveli;
TUHOASOLMU(apusolmu);
END;
PROCEDURE NOUSETASOLTAYLOS;
VAR apu:puu;
BEGIN
IF taso>1 THEN
BEGIN
pelipuu^.ylataso^.siirrot^.arvo:=pelipuu^.parasarvo;
apu:=pelipuu;
pelipuu:=pelipuu^.ylataso;
TUHOATASOSOLMU(apu);
taso:=taso-1;
POISTASOLMU; { Poistetaan myos isasolmu }
IF taso>1 THEN IF taso=2 THEN PERULAUTATILANNE(alkuindx,alkuindy)
ELSE BEGIN PERULAUTATILANNE(pelipuu^.ylataso^.ylataso^.siirrot^.x,pelipuu^.ylataso^.ylataso^.siirrot^.y);
END;
END;
END;
BEGIN { purapuuta }
IF taso=maxtaso THEN
BEGIN
WHILE pelipuu^.siirrot<>NIL DO POISTASOLMU;
PERULAUTATILANNE(pelipuu^.ylataso^.ylataso^.siirrot^.x,pelipuu^.ylataso^.ylataso^.siirrot^.y);
NOUSETASOLTAYLOS;
pojat:=pelipuu^.siirrot;
END
ELSE
BEGIN
IF pelipuu^.siirrot=NIL THEN
WHILE (pelipuu^.siirrot=NIL)AND(taso>1) DO NOUSETASOLTAYLOS
ELSE BEGIN
POISTASOLMU;
IF taso=2 THEN PERULAUTATILANNE(alkuindx,alkuindy)
ELSE PERULAUTATILANNE(pelipuu^.ylataso^.ylataso^.siirrot^.x,pelipuu^.ylataso^.ylataso^.siirrot^.y);
END;
pojat:=pelipuu^.siirrot;
END;
END;
BEGIN { konesiirtaa }
writeln('Odota, mietin. Kauan......');
taso:=1;
alkuindx:=1; alkuindy:=1;
UUSITASOSOLMU(pelipuu);
UUSISOLMU(pojat);
pojat^.arvo:=analysoipelitilannekoneenkannalta-analysoipelitilannepelaajankannalta;
pojat^.x:=alkuindx;
pojat^.y:=alkuindy;
pelipuu^.siirrot:=pojat;
pelipuu^.parasarvo:= 32767;
RAKENNASEURAAVATASO;
IF pojat<>NIL THEN
BEGIN
{WRITELN('POJAT<>NIL');}
IF pojat^.oikveli=NIL THEN BEGIN
parasindx:=pojat^.x;
parasindy:=pojat^.y;
WRITELN('POJAT^.OIKVELI=nil');
if pelitilanne[parasindx,parasindy]=2 THEN pelitilanne[parasindx,parasindy]:=0;
END
ELSE
WHILE taso>1 DO
BEGIN
WHILE (pojat<>NIL)AND(taso<maxtaso) DO
{WRITELN('pojat<>NIL');}
RAKENNASEURAAVATASO;
PURAPUUTA;
END; {poistatähti}
TUHOATASOSOLMU(pelipuu);
taso:=0;
pelitilanne[parasindx,parasindy]:=0;
END ELSE BEGIN
WRITELN('TAALLLA 2');
{pelipaattyi:=TRUE;}
END;
END;
PROCEDURE laitaristi; {Missä kohti pelaaaja painoi? - siihen risti}
var Reali, Realj: Real;
sisalto: SmallInt;
begin
REPEAT
repeat until lpressed;
getmousestate(mposx,mposy,state);
Reali:=Int(mposx/32);
Realj:=Int(mposy/24);
sisalto:=pelitilanne[trunc(Reali)+1,trunc(Realj)+1];
if sisalto=2 THEN BEGIN
pelitilanne[trunc(Reali)+1,trunc(Realj)+1]:=1;
New(solmumuuttuja);
x:=SmallInt(trunc(Reali));
solmumuuttuja^.x:=x;
y:=SmallInt(trunc(Realj));;
solmumuuttuja^.y:=y;
IF voitto THEN solmumuuttuja^.arvo:=-32768 {pelaaja voittaa siirrolla x y}
ELSE solmumuuttuja^.arvo:=0;
pelipuu^.siirrot:=@solmumuuttuja;
apulaittoso:=alku;
New(laitot);
laitot^.x:=x;
laitot^.y:=y;
laitot^.seur:=apulaittoso;
alku:=laitot;
END;
repeat until not lpressed;
UNTIL sisalto=2;
{tulostalaitot;}
END;
PROCEDURE Tuhoapelipuu;
BEGIN
New(pelipuu);
New(solmumuuttuja);
pelipuu^.siirrot:=solmumuuttuja;
pelipuu^.siirrot^.x:=10;
pelipuu^.siirrot^.y:=10;
pelipuu^.ylataso:=NIL;
pelipuu^.parasarvo:=0;
pelipuu^.siirrot^.oikveli:=NIL;
kayttamattomat:=NIL;
kayttamattsolmut:=NIL;
END;
begin {PÄÄOHJELMA}
repeat;
alusta;
repeat
if Keypressed THEN ch:= Readkey;
repeat until lpressed;
if not voitto THEN
BEGIN
laitaristi;
piirra;
END;
repeat until not lpressed;
if not voitto THEN
BEGIN
now1:=Now;
konesiirtaa;
now2:=Now;
s:=SecondsBetween (now2, now1);
WRITELN('Sori, että mietin naaaiiin kauan :( ',Int(s), ' sekuntia.');
piirra;
writeln('No niin! Sinun vuoro');
Tuhoapelipuu;
END;
until (ch = #27) OR voitto;
WRITELN(merkit[voittomerkki], ' VOITTI!');
ch:=Readkey;
UNTIL ((ch=#28) or olivoitto);
end.Oli pari järjetöntä pientä bugia. Tämä pelaa jo paljon nopeammin ja vähän paremmin. Hölmö kävin läpi kaikki ruudut kun tutkin onko viisi peräkkäin, kun tietysti pitää käydä läpi vain ne ruudut, joissa on joko X tai 0.
https://petke.info/ristinolla9.exe
Tekoälyssä on vielä häikkää vaikka korjasin sieltäkin yhden pahan bugin.