Keskustelu: Koodit: C, HTML: Ristinolla nettisivuna

"HTML ei ole ohjelmointia!" julistaa moni. Mutta HTML soveltuu mainiosti mm. erilaisten pelien ohjelmointiin. Tässä esitellään tekoälyllä varustettu ristinolla, ja samalla menetelmällä on periaatteessa mahdollista toteuttaa esimerkiksi shakkia pelaava HTML-sivu.

Lopputulos on nähtävissä ja pelattavissa osoitteessa:

http://koti.mbnet.fi/pllk/muut/rnolla.html

Useista muista kielistä tuttuja komentoja (if, for, return) HTML:stä on tietenkin turha etsiä. Mutta ohjelman suoritus voidaan kuvata aina siirtymisinä tilasta toiseen. Tavallisen ohjelman tilaan voivat kuulua sen muuttujien arvot ja suorituskohta. Esim. yksi tila voi olla "muuttuja a:n arvo on 3 ja ollaan rivillä 3", josta siirrytään aina tilaan "muuttuja a:n arvo on 4 ja ollaan rivillä 6".

Kun ohjelman rivejä, muuttujia ja muuttujien mahdollisia arvoja on äärellinen määrä, myös mahdollisia tiloja on äärellinen määrä. Kun tila sisältää kaiken ohjelman käytössä olevan tiedon, voidaan myös suoraan ilmoittaa, mihin tilaan siirrytään seuraavaksi. Tästä seuraa, että ohjelma voidaan esittää HTML-muodossa kirjaamalla muistiin kaikki tilat ja niiden väliset siirtymät.

Ristinollan tapauksessa jokainen mahdollinen ruudukko on ohjelman yksi tila. Kun ruudukossa on yhdeksän ruutua ja jokaisessa ruudussa voi olla kolme eri merkkiä (tyhjä, risti tai nolla), eri tiloja on 3⁹ eli 19683. Tilojen määrä vähenee kuitenkin reilusti, kun tiedetään, että pelaajat tekevät merkintöjä vuorotellen, ja päätetään, kumpi pelaaja aloittaa. Kun vielä tunnetaan tekoälyn toiminta, mahdollisia tiloja on vielä vähemmän.

Kun tutkitaan kaikki mahdolliset pelinkulut tyhjästä ruudukosta aloittaen, saadaan selville, että 2755 tilaa eli ruudukkoa riittää täydellisen ohjelman toteutukseen. Tilojen siirtymät määritetään käyttäjän valinnoista riippuviksi. Näin ohjelma voidaan muuttaa HTML-sivuksi, joka sisältää kaikki mahdolliset ruudukot toisiinsa linkitettyinä. Ohessa on HTML-sivun muodostava C-ohjelma, koska sivun kirjoitus käsin olisi hyvin työlästä.

HTML:llä voi siis laatia ohjelmia siinä missä muillakin kielillä, mutta ongelmia alkaa tulla siinä vaiheessa, kun mahdollisten tilojen määrä kasvaa suureksi. Esim. jos ohjelmassa on muuttuja, jolle käyttäjä voi antaa minkä tahansa arvon, jokainen arvo pitää merkitä pahimmassa tapauksessa erikseen HTML-sivulle. Sekä sivujen koko että niiden muodostamiseen kuluva aika saattavat kasvaa tietyissä tapauksissa kohtuuttoman suuriksi.

#include <stdio.h>
#include <stdlib.h>

#define TYHJA 0
#define KESKEN 1
#define VOITTO 2
#define TASAPELI 3

#define RISTI 1
#define NOLLA 2

/* sallitut voittosuorat ruudukossa */
int suorat[8][3] = {{0, 1, 2}, {3, 4, 5}, {6, 7, 8},
                    {0, 3, 6}, {1, 4, 7}, {2, 5, 8},
                    {0, 4, 8}, {2, 4, 6}};
/* kertoimet tunnuksen laskua varten */
int kertoimet[9] = {1, 3, 9, 27, 81, 243, 729, 2187, 6561};
/* sivulla näytettävät merkinnät */
char merkinnat[3] = {'_', 'X', 'O'};

/* lasketut pelitilanteet */
int tilanteet[20000] = {0};
/* ruudukoissa olevat merkinnät */
int ruudukot[20000][9];
/* seuraavat pelitilanteet */
int seuraavat[20000][9];

/* tutkii, onko pelitilanne päättynyt voittoon */
int voitto(int peli[9], int oma) {
    int i;

    for (i = 0; i < 8; i++) {
        if (peli[suorat[i][0]] == peli[suorat[i][1]] &&
            peli[suorat[i][0]] == oma &&
            peli[suorat[i][2]] == oma) {
            return 1;
        }
    }

    return 0;
}

/* laskee tunnuksen pelitilanteen merkinnöistä */
int tunnus(int peli[9]) {
    int i, t = 0;

    for (i = 0; i < 9; i++) {
        t += (kertoimet[i] * peli[i]);
    }

    return t;
}

/* kopioi pelitilanteen sisällön toiseen */
void kopioi(int mista[9], int minne[9]) {
    memcpy(minne, mista, sizeof(int) * 9);
}

/* lisää pelitilanteeseen uuden ristin */
int risti(int peli[9], int maara) {
    int i, pienin = 1, arvo;
    int uusi[9];

    tilanteet[tunnus(peli)] = KESKEN;

    kopioi(peli, uusi);
    kopioi(peli, ruudukot[tunnus(peli)]);

    if (voitto(peli, NOLLA)) {
        tilanteet[tunnus(peli)] = VOITTO;
        return 1;
    }

    for (i = 0; i < 9; i++) {
        if (uusi[i] != TYHJA) {
            continue;
        }

        uusi[i] = RISTI;

        arvo = nolla(uusi, maara + 1, tunnus(peli), i);
        if (arvo < pienin) {
            pienin = arvo;
        }

        uusi[i] = TYHJA;
    }

    return pienin;
}

/* lisää pelitilanteeseen uuden nollan */
int nolla(int peli[9], int maara, int vanha, int kohta) {
    int i, suurin = -1, arvo;
    int uusi[9];

    kopioi(peli, uusi);
    kopioi(peli, ruudukot[tunnus(peli)]);

    if (voitto(peli, RISTI)) {
        return -1;
    }

    if (maara == 9) {
        seuraavat[vanha][kohta] = tunnus(peli);
        tilanteet[tunnus(peli)] = TASAPELI;
        return 0;
    }

    for (i = 0; i < 9; i++) {
        if (uusi[i] != TYHJA) {
            continue;
        }

        uusi[i] = NOLLA;

        arvo = risti(uusi, maara + 1);
        if (arvo > suurin) {
            suurin = arvo;
            seuraavat[vanha][kohta] = tunnus(uusi);
        }

        uusi[i] = TYHJA;
    }

    return suurin;
}

int main(void) {
    int i, j, laskuri = 0;
    int alku[9] = {0};
    FILE *html;

    risti(alku, 0);

    html = fopen("rnolla.html", "w");
    fprintf(html, "<pre>\n"
                  "HTML-ristinolla\n\n"
                  "<a href=\"#0\">Aloita peli</a>");

    for (i = 0; i < 20000; i++) {
        if (tilanteet[i] == TYHJA) {
            continue;
        }

        laskuri++;

        fprintf(html, "<div style=\"height:2000px\"></div>\n"
                      "<a name=\"%i\">\n", i);

        for (j = 0; j < 9; j++) {
            if (ruudukot[i][j] == TYHJA && tilanteet[i] == KESKEN) {
                fprintf(html, "<a href=\"#%i\">%c</a> ",
                        seuraavat[i][j], merkinnat[ruudukot[i][j]]);
            } else {
                fprintf(html, "%c ", merkinnat[ruudukot[i][j]]);
            }
            if (j % 3 == 2) {
                fprintf(html, "\n");
            }
        }

        if (tilanteet[i] == VOITTO) {
            fprintf(html, "\nHävisit!\n\n"
                          "<a href=\"#0\">Uusi peli</a>");
        }

        if (tilanteet[i] == TASAPELI) {
            fprintf(html, "\nTasapeli!\n\n"
                          "<a href=\"#0\">Uusi peli</a>");
        }
    }

    fprintf(html, "</pre>\n");
    fclose(html);

    printf("Tilanteet: %i\n", laskuri);

    return 0;
}

Aika ovela.

En tiennyt, että HTML:lällä voisi tuollaisiakin tehdä :) Ihan mukava tälläinen.

EDIT: Nyt vasta huomasin, miten tämä toimii =)

Mutta tuotahan ei voi edes voittaa!

Tätä on kyllä mietitty ajan kanssa :)
Ei ole tullut mieleenkään tehdä ennen mitään controlleria C:llä etenkään HTML:lle..

sivuhistoria menee vaan aika sekasin tästä

Ei näin. Ei todellakaan näin. 1) HTML ei ole ohjelmointikieli vaikka kuinka generoisit sitä C:llä. Jos ohjelmalla generoitu mikä tahansa tulostus muuttuu yhtäkkiä "ohjelmointikieleksi" niin sittenhän mikä tahansa voi olla ohjelmointikieltä. 2) Ristinolla ehkä onnistuu mutta shakki?! Tajuat kai että erilaisia shakkipelejä on aivan järjettömän paljon. ( http://mathworld.wolfram.com/Chess.html antaa arvioksi 10^10^50) Minkälaisen koneen muisti riittää esittämään kaikki shakkipelit kun shakkipelejä on enemmän kuin atomeja universumissa?

Muuten kyllä ihan hassu idea.

EI näin, 10*10 ruudukko ristinollaa tarvitsisi 25 tavua/kpl ja niitä tarvitsisi (ilman karsintaa) pyöreät 3**100 = 5e47 => tilaa pelkkiin ruudukkoihin vaadittaisiin hulppeat 5e35 teratavua.

PS.Tuolla on muuten turhia asetelmia, esim. tuota viimeistä (19560) ei voi saavuttaa.

(Tätä ei ole tarkoitettu kritiikiksi sinänsä kekseliästä ohjelmaesimerkkiä kohtaan, vaan ihan vaan tuosta määrittelystä keskustelemiseksi.)

lainaus:

Mutta HTML soveltuu mainiosti mm. erilaisten pelien ohjelmointiin.

Tästä en ole samaa mieltä. On siinä ja siinä että suostunko kutsumaan tuota ohjelmoinniksi. Vastaavan hommanhan voisi painaa kirjaankin. Eli kuhunkin käyttäjän valittavissa olevaan ruutuun vaan "mene sivulle x" jossa olisi sitten seuraava siirto.

Jos nyt välttämättä halutaan määritellä että tuo on ohjelmointia, niin sitten olen ainakin eri mieltä siitä, että se soveltuisi pelien ohjelmointiin mainiosti.

Ilmaus "mainiosti" ja muutama muukin kohta kuvauksessa ovat kieltämättä hieman kaunisteltuja. Halusin kuitenkin esittää asian näin, koska usein ajatus HTML:stä ohjelmointina tyrmätään suoralta kädeltä, vaikka asia ei tosiaankaan ole niin mustavalkoinen. Tässä esitetyllä tavalla on mahdollista toteuttaa jopa pelkkään HTML:ään perustuva Turingin kone.

Tarvittavien tilojen suuri määrä esim. shakissa on tietysti ongelma, jos peliä alkaisi käytännössä toteuttaa, mutta nykyisten tietokoneiden riittämättömyys ei ole HTML:n vika. Siinä missä perinteisessä ohjelmoinnissa aika voi loppua kesken, HTML-ohjelmoinnissa tila voi loppua kesken. Jos kaikkia tiloja ei ehdi käydä läpi, niin ei niitä myöskään voi tallentaa muistiin.

Grez kirjoitti:

Vastaavan hommanhan voisi painaa kirjaankin. Eli kuhunkin käyttäjän valittavissa olevaan ruutuun vaan "mene sivulle x" jossa olisi sitten seuraava siirto.

Minäkin tulin ajatelleeksi samaa asiaa. Olisi aika huvittavaa, jos vaikka shakin kaikki tilanteet saisi jotenkin mahdutettua kirjaan. Sitten voisi tosiaan vain "pelata" "tekoälyä" vastaan selaamalla kirjaa. Tämä olisi ainakin hyvä näyte siitä, mitä tietokoneen älykkyys on...

L2-K2 kirjoitti:

Tuolla on muuten turhia asetelmia, esim. tuota viimeistä (19560) ei voi saavuttaa.

Tarkasti havaittu, ohjelma todellakin erehtyy ottamaan mukaan joitakin tiloja, jotka myöhemmin voisi jättää pois tarpeettomina. Voisin joskus parannella ohjelmaa tältä osin.

lainaus:

Halusin kuitenkin esittää asian näin, koska usein ajatus HTML:stä ohjelmointina tyrmätään suoralta kädeltä, vaikka asia ei tosiaankaan ole niin mustavalkoinen.

Ei se toki ole siinä mielessä mustavalkoinen, että ohjelmointi perustasolla tarkoittaa toimintaohjeiden antamista. Ne voi antaa ihmiselle kirjassa tai videonauhurille kaukosäätimellä kun ajastaa kauniit ja rohkeat, niin miksei sitten tietokoneelle HTML:nä.

Kuitenkin tässä on se ero että jos joku sanoo että harrastaa ohjelmointia, niin hänen ei normaalisti ymmärretä naputtelevan televisio-ohjelman alku- ja loppuaikoja videonauhuriin, kirjoittavan käyttöohjeita tai nysväävän satoja sivuja HTML-koodia.

Myöskin normaalisti sillä mitä ohjelmoinnilla ymmärretään päästään siihen, että muuttujien määrä voi olla äärimmäisen suuri ja silti ohjelma pystytään toteuttamaan. Jos ohjelmointi toteutettaisiin ennakkoon laskemalla kaikki mahdolliset tilanteet, niin "ohjelman" monimutkaisuus kasvaisi eksponentiaalisesti.

Sanoit että ei ole HTML:n vika jos tila ei riitä, mutta en sitten tiedä minkä vika on jos suht yksinkertainen ohjelma alkaisi vaatia tilaa bitteinä enemmän kuin maailmankaikkeudessa on atomeja.

Tottahan se on, että käytännössä moni ohjelma jäisi HTML:nä toteuttamatta, vaikka teoriassa melkein kaikki olisikin mahdollista. HTML-ohjelma on kuin leikkikehässä, jossa se saa eteensä vain tiloja, jotka joku muu on jo tutkinut etukäteen. Eli esimerkiksi jonkin ongelman ratkaisua etsivä HTML-ohjelma on melko typerä ajatus, sillä ensin ratkaisu pitäisi kuitenkin kirjata jonnekin ja HTML-sivu saisi sitten etsiä sen uudestaan valmiiksi rakennettua seikkailurataa pitkin. Parhaimmillaan HTML taas on tällaisissa ristinollan kaltaisissa peleissä, joissa pelaaja vuorostaan etenee valmiita reittejä.

Tuota voisi pikemminkin kutsua tietokannaksi, josta löytyy vastaukset ristinollan pelin kulkuun.

Ei todellakaan voi sanoa ohjelmoinniksi. Itse ohjelmointi tapahtui tuossa C-ohjelmassasi. >__<

No yhtä hyvin kyseessä voisi olla tekstiseikkailupeli. Moisen voi kirjoittaa HTML:llä, mutta sen voi myös kirjoittaa C:llä tai QB:lla tai miltei millä vain (Brainfuck on vähän rajoilla). Jos sellaisen kirjottaisi C:llä, niin se on yht'äkkiä ohjelmointia, kun HTML:llä taasen ei - vaikka peli olisikin pelaajan kannalta täysin sama, niinkö?

"Ohjelmaa voidaan ajatella komentosarjana, jonka tietokone suorittaa ohjelman käyttäjän pyynnöstä."

Eli tuossa HTML-tapauksessa ohjelma on nettiselaimesi, ja sinä olet käyttäjä, ja annat ohjelmalle (nettiselaimellesi) käskyn kun klikkaat linkkiä.

Missään vaiheessa ei tapahdu minkäänlaista komentojen käsittelyä (siis tuossa HTML-koodissa). Tuossa vain siirrytään siihen kohtaan sivua johon käyttäjä haluaa siirtyvän. (ja siirtyminen tapahtuu nettiselaimesi ansiosta).

HTML:ää ei saa eikä voi ajatella ohjelmana eikä asiasta tulisi enää koskaan väitellä.

Eipä se C:kään itsekseen mitään tee. Teknisestihän kaiken takana on tietokone itse.

:DDDDDDDDDDDDDDDddddddd Trolli.

Jos C:ssä ei olisi muuttujia, niin ei se eroaisi juurikaan HTML:stä ohjelmoinnin suhteen.

Niin, ja missäpä ohjelmointikielessä ei muuttujia olisi...

Riippuu ohjelmointikielen määrittelystä. Jos ohjelmointikieli määritellään niin, että sen täytyy sisältää muuttujia, niin silloin HTML ei ole ohjelmointikieli ja suoraan määrittelystä johtuen mitään muutakaan muuttujatonta ohjelmointikieltä ei ole.

Mikäli taas ohjelmointikielen määritelmä ei sisällä vaatimusta muuttujien olemassa olosta niin silloin HTML:nkin voidaan katsoa olevan ohjelmointikieli.

Tässä juuri oli edellisen viestini pointti, mutta näköjään ei pidä tiivistää liikaa.

Eiks ohjelmointikielen voisi määritellä niin, että sillä voi ratkoa äärellisen määrän ongelmia. Kuvauskieli olisi sivun rakenteen kuvaukseen.

Ei näin...

Muuten aivan mahtava vinkki, mutta myöhästyi viikolla.

Tämähän periatteessa ei eroa normaaliin PHP-säätöön mitenkään muuten kuin kielen osalta. HTML on kuvauskieli (ML = Markup Language) eikä sitä voi sanoa ohjelmointikieleksi. Eihän HTML tee mitään muuta kuin kuvaa sivun rakennetta. Mikäli tämä määritelmä riittää, niin tämä kommentti on ohjelmointikieltä, koska sehän voidaan generoida ohjelmointikielellä. Samoin kuin tietokannat ja vaikkapa CSS.

Eli siis kaikki on ohjelmointia! \o/

Ehtorakenteiden olemassaolon / suuren puutteen perusteella HTML on ohjelmointikieli. Onhan conditional comments olemassa. :)

Jännä, mutta ei uusi idea. En enää linkkiä löytänyt, mutta putkan ristinollakilpailun aikoihin muistan pelanneeni vastaavanlaista html-ristinollaa vastaan.

KingOfTheWorld kirjoitti:

Ehtorakenteiden olemassaolon / suuren puutteen perusteella HTML on ohjelmointikieli. Onhan conditional comments olemassa. :)

Käsittääkseni nämä eivät kuulu HTML:ään.

Ai niin hitto, tietystikin. Nehän ovat Micro$oftin oma tekniikka. *tyhmä minä*

Ehkäpä ohjelmointikielen pitäisi täyttää ehto: ohjelman saadessa parametrejä se kykenee suorittamaan tehtävää itsenäisesti sen jälkeen, kunnes haluttu tehtävä on suoritettu.

Tähänhän ei tällä html kielellä pystytä, vaan se vaatii ulkoisen tekoälyn ("Käyttäjä") käyttämistä päätös tilanteissa.

Jokainen saa halutessaan kokeilla koodata puhtaalla html merkkauksella vaikkapa yksinkertaista automaattia jolle kerrotaan parametrinä ohjelma numero ja sen jälkeen se suorittaa haluttua ohjelma sekvenssiä. Lisäpiste jokaiselle joka keksi kuinka vaikkapa hätäpysäytys signaaliin saadaan automaattinen reagointi "html-ohjelmoinnilla".

Itse en ole ajatellut HTML:ää ohjelmointikielenä, sitäkin on hieman tullut kirjoiteltua, mutta en laskisi sitä ohjelmointikieleksi.

Ristinollasi on kyllä vaikuttava, itsekin pascalilla yritän sellaista kyhätä. Pohjan olen saanut valmiiksi, vielä jos saisin ohjelmoitua tietokoneen pelaamaan, tällä hetkellä siinä pelaisi kaksi käyttäjää. Sen lisäksi vielä pitäisi saada ohjelma tunnistamaan millon on viiden suora saatu aikaiseksi.

Tämä vissin on sillee et jos vähän käpälöi tekstiä niin saa tehtyä esm tasot vauva(helppo voittaa) normaali(no siis normaali vaikeustaso) mahdoton(nykyinen versio tuossa ylhäällä)??? on vissiin mahdollista ku olis kiva voittaakki tuo.

Nyt näyttää paljon paremmalta, katson vielä lähiaikoina uudestaan läpi ja julkaisen.

Koodia (ja kommentteja) minusta selventäisi aika paljon, jos olisi erikseen funktio pelkästään nousevalle vertailulle ja CompareTo palauttaisi suoraan jotain tällaista:

if (this.M_Direction == SortDirection.Descending) {
  return AscendingCompareTo(b, a);
} else {
  return AscendingCompareTo(a, b);
}

Toinen (ehkä muuten vielä parempi!) vaihtoehto on käyttää vain yhtä funktiota mutta vaihtaa alussa a ja b keskenään, jos suunta on laskeva. Molemmilla tavoilla päästäisiin eroon tuosta toistuvasta ?:-rumiluksesta, joka luultavasti säikyttää aloittelijat.