NOVINKA - Online rekvalifikační kurz Java programátor. Oblíbená a studenty ověřená rekvalifikace - nyní i online.
NOVINKA – Víkendový online kurz Software tester, který tě posune dál. Zjisti, jak na to!

Diskuze: Algoritmus minimax pro piškovrky 10x10

V předchozím kvízu, Online test znalostí JavaScript, jsme si ověřili nabyté zkušenosti z kurzu.

Aktivity
Avatar
adder
Člen
Avatar
adder:18.5.2016 13:11

Zdravím,
zkouším algoritmus v piškvorkách, ale někdy mi to hází nějaké divné výsledky. V hloubce 1 si i zahraji, ale není to úplně to ořechové, ale když půjdu do 2 nebo 3, tak to hazí bullshitty. Možná mám blbě vyhledávání v tom stromu, ale nejsem si jist. Čím víc se na to dívám, tím víc se v tom už ztrácím. Ohodnocovací funkce, taky není úplně parádní, ale myslím, že stačí.

Děkuji za případnou pomoc. :)

// strom

function Tree(ohodnoceni, radek, sloupec, child) {
    this.ohodnoceni = ohodnoceni;
    this.radek = radek;
    this.sloupec = sloupec;

    this.children = child || [];

    this.addChild = function (ohodnoceni, radek, sloupec){
        this.children.push(new Tree(ohodnoceni, radek, sloupec));
    }

    this.searchTree = function (radek, sloupec){
                if(this.radek == radek && this.sloupec == sloupec) {
                        return this;
                } else if (this.children != null) {
                        var vysledek = null;
                        for(var i = 0; vysledek == null && i < this.children.length; i++) {
                        vysledek = this.children[i].searchTree(radek, sloupec);
                        }
                        // vraáti this
                        return vysledek;
                }
                // jinak nic
                return null;
        }
}

// hodnitící funkce

function hodnoticiFunkce(radek, sloupec, matice, hrac) {

        var testovaciMatice = [];

        // vytvoření testovací matice pro možnost výběru a ohodnocení dalšího zakliknutého pole

        for(var i = 0; i < matice.length; i++) {
                testovaciMatice[i] = [];
                for(var j = 0; j < matice[0].length; j++) {
                        if(matice[i][j] !== null) {
                                testovaciMatice[i][j] = matice[i][j];
                        } else {
                                testovaciMatice[i][j] = null
                        }
                }
        }

        testovaciMatice[radek][sloupec] = hrac;

        // kontrolaVitezstvi vrací 1, 2, 3, 4, 5 podle toho, kolik je v řadě křížků resp. koleček

        switch(kontrolaVitezstvi(radek, sloupec, testovaciMatice)) {

                case 1:
                        return 1;
                case 2:
                        return 10;
                case 3:
                        return 50;
                case 4:
                        return 200;
                case 5:
                        return 500;
                default:
                        return 1;
        }
}

// minimax

function minimax(hloubka, hrac, matice, uzel) {

        if(hloubka == 0) {
                uzel.ohodnoceni = hodnoticiFunkce(uzel.radek, uzel.sloupec, matice, hrac);
                return uzel;
        }

        if(!hrac) {
                uzel.ohodnoceni = -1000;
                var v, r, s;
                for(var i = 0; i < matice.length; i++) {
                        for(var j = 0; j < matice[0].length; j++) {
                                if(matice[i][j] == null) {
                                        r = i;
                                        s = j;
                                        uzel.addChild(uzel.ohodnoceni, i, j);
                                        v = minimax(hloubka - 1, true, matice, uzel.searchTree(i, j));

                                        if(v.ohodnoceni >= uzel.ohodnoceni) {
                                                uzel.ohodnoceni = v.ohodnoceni;
                                                uzel.radek = r;
                                                uzel.sloupec = s;
                                        }
                                }
                        }
                }
        } else {
                uzel.ohodnoceni = 1000;
                var     v;
                for(var i = 0; i < matice.length; i++) {
                        for(var j = 0; j < matice[0].length; j++) {
                                if(matice[i][j] == null) {
                                        r = i;
                                        s = j;
                                        uzel.addChild(uzel.ohodnoceni, i, j);
                                        v = minimax(hloubka - 1, false, matice, uzel.searchTree(i, j));

                                        if(v.ohodnoceni <= uzel.ohodnoceni) {
                                                uzel.ohodnoceni = -v.ohodnoceni;
                                                uzel.radek = r;
                                                uzel.sloupec = s;
                                        }
                                }
                        }
                }
        }

        return uzel;
}
Odpovědět
18.5.2016 13:11
I’m going to lay this brick as perfectly as a brick can be laid.
Děláme co je v našich silách, aby byly zdejší diskuze co nejkvalitnější. Proto do nich také mohou přispívat pouze registrovaní členové. Pro zapojení do diskuze se přihlas. Pokud ještě nemáš účet, zaregistruj se, je to zdarma.

Zobrazeno 1 zpráv z 1.