A* Algoritması (A yıldız arama algoritması)

Amacı : Bir düğümden, diğer düğüme en az maliyetli çözümü bulmak

Türü : Arama Algoritması, Sezgisel Algoritma (Yapay zeka)

Kâşifleri : Nils Nilsson,Bertram Raphael , Peter E. Hart

Kullanım yerleri :

  • Yol bulma
  • Oyunlarda aktörün hedefe doğru izleyeceği yolların tespiti
  • Gezgin satıcı probleminin çözümü
  • Labirentten en kısa çıkışı bulma

 

f(x) : durum fonksiyonu. Az olması, o durumun daha az maliyetli olduğunu belirtir.

f(x) = g(x) + h(x)

g(x) : Başlangıç durumuna göre maliyetimiz.

h(x) : Bitiş duruma olan sezgisel maliyet.

Algoritma

OPEN -> // fCost'a göre sıralı dizi

OPEN.ekle(başlangıç_düğümü)

DÖNGÜ - OPEN dizi boyutu 0 olmadığı müddetçe
    şuanki_düğüm <- OPEN.ilk elemanı
    OPEN.sil(şuanki düğüm)
    EĞER şuanki_düğüm, hedef düğüm ise
        DÖNGÜden çık // HEDEFE ULAŞTI
    şuanki_düğüm.closed=true
    şuanki_düğüm.gCostHesapla()
    komşular = şuanki_düğüm.komşular
    DÖNGÜ komşu <- komşular
        EĞER komşu.closed ise SONRAKİ_KOMŞUYA_GEÇ
        maliyet = şuanki_düğüm.gCost + komşuya_uzaklık
        komşu.gCostHesapla()
        EĞER komşu.OPENdaDeğilse veya maliyet<komşu.gCost ise
            komşu.gCost = maliyet
            komşu.hCostHesapla()
            komşu.ebeveyn = şuanki_düğüm
            EĞER komşu.OPENdaDeğilse
                OPEN.ekle(komşu)
OPEN dizi boyutu 0 olduğu için DÖNGÜden çıkıldıysa // HEDEFE ULAŞAMADI

Javascript Kodu

FIND (Yol bulmayı başlat)
RELOAD (Gridi yeniden yükle)
ilk tık -> başlangıç karesi
2. tık -> hedef kare
sonraki tıklar -> engel oluştur

See the Pen A* Algoritması by farukcan (@farukcan) on CodePen.

3 taş oyunu için Yapay Zeka

Bu oyunda YZ, oyuncunun yaptığı hamlenin ardından, kendi yapacağı hamlelerin durum uzayını oluşturup sezgisel fonksiyon ile ileriye yönelik hamleleri bir puan vermektedir. Bunu yaparken, rakibinin bir sonraki hamlesini de göz önüne alır.

/**
 * Created by Faruk Can on 6.4.2016.
 */
 
var ç = new CanvasRender("canvas1");
 
var canvasboyut = 500;
 
var tahta = [
    [0,0,0],
    [0,0,0],
    [0,0,0]
];
// 1 : X
// diğer : O
// 0 : boş
 
 
 
// kontrol mekanizması
ç.addClickListener(function(x,y){
    console.log(x,y);
});
var hamleyapmakiçinarray = [];
for(var m=0;m<3;m++)
    for(var n=0;n<3;n++){
        hamleyapmakiçinarray.push({
            "height" : canvasboyut/3,
            "width" : canvasboyut/3,
            "top" : canvasboyut/3*m,
            "left" : canvasboyut/3*n
        });
    }
hamleyapmakiçinarray[0].func = function (){hamleyap(0,0)};
hamleyapmakiçinarray[1].func = function (){hamleyap(0,1)};
hamleyapmakiçinarray[2].func = function (){hamleyap(0,2)};
hamleyapmakiçinarray[3].func = function (){hamleyap(1,0)};
hamleyapmakiçinarray[4].func = function (){hamleyap(1,1)};
hamleyapmakiçinarray[5].func = function (){hamleyap(1,2)};
hamleyapmakiçinarray[6].func = function (){hamleyap(2,0)};
hamleyapmakiçinarray[7].func = function (){hamleyap(2,1)};
hamleyapmakiçinarray[8].func = function (){hamleyap(2,2)};
ç.clickElement = hamleyapmakiçinarray;
 
 
 
// ilk durum
var oyunKimde = "X";
var sıra = 0;
tahtayıÇiz();
hamleleriÇiz(true);
 
 
 
 
 
function hamleyap(m,n){
    if(oyunKimde == "X" && tahta[m][n]==0){
        tahta[m][n] = 1;
        oyunKimde = "O";
        ç.clear();
        tahtayıÇiz();
        hamleleriÇiz();
        sıra++;
        if(!oyunsonu())
            setTimeout(YZhamleyap,500);
    }
}
 
function oyunsonu(){
    if(sıra>8) return beraber();
    var taraf = 1;
    kontrolEdilecekYerler.forEach(function(yerler){
        var kactane1var = 0;
        yerler.every(function(y){
            var n= (y-1)%3;
            var m= Math.floor((y-1)/3);
            if(tahta[m][n]*taraf==-1) {
                kactane1var=0;
                return false;
            }
            if(tahta[m][n]*taraf==1) kactane1var++;
            return true;
        });
        if(kactane1var==3) {
            Xkazandı();
        }
    });
    var taraf = -1;
    kontrolEdilecekYerler.forEach(function(yerler){
        var kactane1var = 0;
        yerler.every(function(y){
            var n= (y-1)%3;
            var m= Math.floor((y-1)/3);
            if(tahta[m][n]*taraf==-1) {
                kactane1var=0;
                return false;
            }
            if(tahta[m][n]*taraf==1) kactane1var++;
            return true;
        });
        if(kactane1var==3) {
            Okazandı();
        }
    });
 
}
 
function Xkazandı(){
    alert("X kazandı");
    reload();
}
function Okazandı(){
    alert("O kazandı");
    reload();
}
function beraber(){
    alert("Berabere");
    reload();
}
 
function reload(){
    setTimeout(function(){location.reload();},2000);
}
 
 
var kontrolEdilecekYerler = [
    [1,2,3],
    [4,5,6],
    [7,8,9],
    [1,4,7],
    [2,5,8],
    [3,6,9],
    [1,5,9],
    [3,5,7]
];
 
// # tek taraf sezgisel fonksiyon h2
// -- her satır, sutun ve 2çarpraz için
// --- Eğer -1 varsa : 0 puan
// --- Eğer 1 tane 1 varsa : 1 puan
// --- Eğer 2 tane 1 varsa : 3 puan
// --- Eğer 3 tane 1 varsa : 99 puan
function h2(taraf,durum){
    var puan=0;
    kontrolEdilecekYerler.forEach(function(yerler){
        var kactane1var = 0;
        yerler.every(function(y){
            var n= (y-1)%3;
            var m= Math.floor((y-1)/3);
            if(durum[m][n]*taraf==-1) {
                kactane1var=0;
                return false;
            }
            if(durum[m][n]*taraf==1) kactane1var++;
            return true;
        });
        if(kactane1var==3) puan+=999;
        else if(kactane1var==2)  puan+=3;
        else puan+=kactane1var;
    });
    return puan;
}
 
// rahibin sonraki el en iyi hamlesinin puanını belirle
var h3iterasyon=0;
function h3(taraf,durum){
 
    if(++h3iterasyon==100) return 0;
 
    var olasıHamleler = [];
    /*
     {
     m: (x)
     n: (y)
     h:(sayı) // hamlenin sezgisel fonksiyon değeri
     }
     */
    for(var m=0;m<3;m++)
        for(var n=0;n<3;n++){
            if(durum[m][n]==0){
                // boş olan yerlere hamle yapılabilir
                var d = JSON.parse(JSON.stringify(durum)) // dunyayı klonla
                d[m][n] = taraf; //hamleyi duruma dahil et
                olasıHamleler.push(
                    {
                        "m" : m,
                        "n" : n,
                        "h" : h(taraf,d)
                    }
                );
            }
        }
 
    // en iyi hamleleri sırala
    olasıHamleler.sort(function(a,b){
        return b.h - a.h;
    });
    if(typeof olasıHamleler[0] == "undefined") return 0;
    return olasıHamleler[0].h;
}
 
// # çift taraf sezgisel fonksiyon h
// -- h = h2 - h3
function h(taraf,durum){
    return h2(taraf,durum) - h3(-taraf,durum);
}
 
function YZhamleyap(){
 
    h3iterasyon=0;
    sıra++;
 
    var olasıHamleler = [];
    /*
    {
        m: (x)
        n: (y)
        h:(sayı) // hamlenin sezgisel fonksiyon değeri
    }
     */
    for(var m=0;m<3;m++)
        for(var n=0;n<3;n++){
            if(tahta[m][n]==0){
                // boş olan yerlere hamle yapılabilir
                var durum = JSON.parse(JSON.stringify(tahta)) // dunyayı klonla
                durum[m][n] = -1; //hamleyi duruma dahil et
                olasıHamleler.push(
                    {
                        "m" : m,
                        "n" : n,
                        "h" : h(-1,durum)
                    }
                );
            }
        }
 
    // en iyi hamleleri sırala
    olasıHamleler.sort(function(a,b){
       return b.h - a.h;
    });
 
    tahta[olasıHamleler[0].m][olasıHamleler[0].n] = -1;
    console.log(olasıHamleler);
    oyunKimde = "X";
    ç.clear();
    tahtayıÇiz();
    hamleleriÇiz(true);
    oyunsonu();
}
 
 
function tahtayıÇiz(){
    // tik tak to tahtası
    for(var i=1;i<3;i++){
        ç.line(canvasboyut/3*i,20,canvasboyut/3*i,canvasboyut-20);
        ç.line(20,canvasboyut/3*i,canvasboyut-20,canvasboyut/3*i);
    }
 
}
 
function hamleleriÇiz(num){
    // tahta üzerinde yazan meretler
    var sira = 0;
    for(var m=0;m<3;m++)
        for(var n=0;n<3;n++){
            sira++;
            if(tahta[m][n]==0){
                if(num){
                    ç.font(ç.standartFont);
                    ç.text(sira,canvasboyut/6+canvasboyut/3*n,canvasboyut/6+canvasboyut/3*m);
                }
            }
            else if(tahta[m][n]==1){
                ç.font("233px Arial");
                ç.text("X",canvasboyut/3*n,canvasboyut/3+canvasboyut/3*m);
            }else{
                ç.font("213px Arial");
                ç.text("O",canvasboyut/3*n,canvasboyut/3+canvasboyut/3*m-5);
            }
        }
 
 
    ç.font(ç.standartFont);
}

Perceptron Eğitimi – Yapay Sinir Ağları

 
 
    var w, // ağırlık
            A, B, // girişler
            dA,dB; // istenenler
 
 
    function calculate(){
        $('#console').html('');
        MAXLOOP=Number($("#maxloop").val());
 
        var data = [];
        data.push(A);
        data.push(B);
        var beklenen = [];
        beklenen.push(dA);
        beklenen.push(dB);
 
        var c=Number($("#c").val());
        var k=1; // itarasyon ks
        var E=1; //ERROR
        var o=0; //sign(toplam)
        var p=0; // adım sayısı
        while (E>0 && p < MAXLOOP) {
 
 
 
            E = 0;
            p++;
            if (p == MAXLOOP - 1){
                alert("MAX LOOP Aşıldı");
                break;
            }
 
 
            for (var j = 0; j < data.length; j++) {
                o = sign(toplam(data[j], w));
 
                if (o == beklenen[j]) {
                    //ok
                } else {
 
                    for (var i = 0; i < w.length; i++) {
                        w[i] = w[i] + c * (beklenen[j] - o) * data[j][i] / 2;
                    }
                }
 
                E = E + 1 / 2 * (Math.pow(beklenen[j] - o, 2));
 
            }
            k++;
 
            print("<br>w = "+w.toString()+"[ E= "+E+" ]");
 
 
        }
 
        alert("w = "+w.toString());
 
 
 
 
 
 
 
 
    }
 
 
 
 
 
    function toplam(x,w){
        var toplam=0;
        for(key in w){
            toplam+=w[key]*x[key];
        }
        return toplam;
    }
 
    function sign(x){
        return Math.sign(x);
    }
 
    function f(x){
        return 2/(1+Math.exp(-1*x))-1;
    }