Yazan : Şadi Evren ŞEKER

Bu yazının amacı, PROLOG diline giriş yapmak ve basit bazı yapay zeka problemlerinin PROLOG dilinde nasıl kodlanarak çözüldüğünü göstermektir.

Kurulum ve çalıştırma:

Bu yazı kapsamında SWI-PROLOG programı kullanılacaktır. Programı, www.swi-prolog.org adresinden temin etmek mümkündür.

Yazı kapsamında MAC OSX üzerinde örnekler çalıştırılarak gösterilecektir ancak kurulum ve sonrasında başarılı bir çalıştırma yapılabiliyorsa hangi işletim sisteminde olduğunuzun bir önemi yoktur, bütün sistemlerde aynı PROLOG komutları çalışır.

Siteden indirilip kurulum yapıldıktan sonra,

$ /opt/local/bin/swipl 

Dizini altında bulunan swipl komutu çalıştırılarak, PROLOG komut satırı açılabilir.

Program çalıştırıldığında, aşağıdakine benzer bir komut satırı ile komut girilmesini bekleyecektir:

?- _

Yardım

İlk ve en önemli komutumuz olan yardım komutu ile başlayabiliriz.

?- help(help).

Bu komut, X11 ekranında, yardım dokümanını görüntüleyecektir. Basitçe herhangi bir komut hakkında bilgi alınmak istendiğinde bu komutu help fonksiyonuna parametre olarak vermek yeterlidir. Yukarıdaki kullanımda help komutunun kendisi için yardım alınmıştır.

Çıkış

Prolog komut satırından çıkmak için

?- halt.

Yazılması yeterlidir. Bu komut programı sonlandıracaktır.

Basit Kaziyeler

Aşağıdaki komutları PROLOG üzerinde çalıştıralım ve ardından burada yapılan işlemleri yorumlayalım.

Sistemimizde kayıtlı olan bir dosyayı program tarafından açıp çalıştırılır bir şekilde yüklemek için dosya ismi köşeli parantezler içerisinde verilmelidir:

?- [‘ilkdosya.pl’].

Yukarıda, bilgisayarımızda bulunan “ilkdosya.pl” isimli dosyayı sisteme tanıtarak yükledik. Bu dosyada bulunan tanımlar da otomatik olarak yüklenmiş ve sorgulanmaya / çalışmaya hazır hale getirilmiş olacaktır. Ayrıca bu dosyada bulunan genel hatalar, yükleme sırasında ekrana basılır.

PROLOG ile Faktöriyel Kodu

PROLOG dili, yapısal olarak özyineli (recursive) bir yapıdadır ve döngülerin yerine özyineli fonksiyon (recursive function) kullanılması gerekir. Bu kullanımı göreceğimiz en basit uygulamalardan birisi olan faktöriyel kodunu yazıp kodlamaya çalışalım.

Herhangi bir editör açılarak (ben tercihen vi kullanıyorum, siz de istediğiniz bir editör ile dosyayı açıp içeriğini ) aşağıdaki şekilde yazabilirsiniz:

factorial(0,1).      
factorial(A,B) :- 
             A > 0,
             C is A-1,
            factorial(C,D),
            B is A*D. 

Ardından aşağıdaki şekilde dosyamızı sisteme yükleyelim:

?- [‘ilkdosya.pl’].

% ilkdosya.pl compiled 0.00 sec, 732 bytes

true.

 

Komut satırında dosyamızın yüklendiği ve yükleme süresi ve dosya boyutu gösterilmektedir. Son satırda yer alan true bilgisine kadar bir hata bulunmamış olması, dosyamızda bir hata olmadığını gösterir. Şimdi artık ilk fonksiyonumuzu kullanmaya başlayabiliriz.

?- factorial(5,X).

X = 120 ;

false.

 

Komut satırında, factorial(5,X) komutu verilerek, 5! Değerinin X değişkenine döndürülmesi istenmiştir. Burada öğrenilen birkaç önemli noktayı belirtelim. Birincisi X ile gösterilen değer bir değişkendir ve PROLOG dünyasında buna unbounded variable (bağlanmamış değişken) ismi verilir. Basitçe Prolog kodlarındaki bütün büyük harf ile başlayan ifadeler birer değişkendir ve ayrıca bir değişken tanımı yapılmaz. İkinci bir nokta, Prolog dilinde kod yazılırken girilen her satır bir emirdir ( declaration) ve yapısal olarak Prolog dili, haber mantığını (predicate calculus) barındırır. Buna göre yüklü olan dosyada bulunan komutlar yukarıdan aşağıya doğru çalıştırılırken üstte bulunan satır, alttakine gore öncelikli olur ve aynı zamanda birden fazla satırda emirin tanımlanması durumunda, sırasıyla bu emirler işlenir.

Örneğin yukarıdaki kodda, ilk satırda bulunan factorial (0,1). İfadesi, 0! = 1 anlamındadır ve bir şekilde birisi bize sıfır faktöriyeli sorarsa, ikinci değer olarak 1 sonucunu döndürmeyi gerektirir.

İkinci satırdan sonra başlayan tanımda ise, sırasıyla A>0 kontrolü yapılmış, ardından C değişkenine değer olarak A-1 değeri konmuş ve yeni bulunan C değerinin faktöriyeli hesaplanarak, B sonucuna hesaplanan bu C faktöriyel değeri ile A’nın çarpımı eklenmiştir.

Yukarıdaki şekilde kodumuzu ilkdosya.pl  dosyasına yazıp kaydettikten sonra prolog komut satırında dosyamızı yükleyip çalıştırabiliriz:

 

Yukarıda görüldüğü üzere faktöriyel kodumuz çalışmış ve sonucu doğru şekilde bulmuştur.

Kodun çalışmasını takip etmek için trace komutu kullanılabilir. Basitçe komut satırında:

trace.

Yazıldıktan sonra çalışmaya başlar ve bu çalışmadan sonra çağrılan fonksiyonların detayları ekrana basılır:

Görüldüğü üzere factorial fonksiyonumuzun her adımı ekrana basılmıştır.

Hanoi Kuleleri (Towers of Hanoi)

İkinci bir uygulama olarak çok klasik bilgisayar bilimleri problemlerinden olan Hanoi Kulelerini ( tower of hanoi ) kodlamaya çalışalım.

Oyunun kuralı gayet basit. Başlangıçta bir çubukta dizili olan bütün diskler her adımda tek bir disk hareket ettirerek diğer iki çubuktan birisine taşınacaktır. Bu taşıma işlemleri sırasında büyük bir disk, küçük olan bir diskin üzerine gelmeyecektir.

Ayrıca oyunun internetten oynan bir denemesi için daha önce hazırladığım aşağıdaki ödev sayfasına bakabilirsiniz:

http://www.sadievrenseker.com/c/odev5.html

Problemin çözümünde kullanacağımız kod aşağıdaki şekildedir:

SADIs-MacBook-Air:prolog sadievrenseker$ vi hanoi.pl

oyna(1,X,Y,_) :-

    write(X),

    write(‘ en üstteki diskini ‘),

    write(Y),

    write(‘ oynat ‘),

    nl.

oyna(N,X,Y,Z) :-

    N>1,

    M is N-1,

    oyna(M,X,Z,Y),

    oyna(1,X,Y,_),

    oyna(M,Z,Y,X).

Kod örneği yukarıda verilmiştir. Kodumuzun çalışmasını görüp ardından nasıl çalıştığını açıklamaya geçebiliriz.

 

?- oyna(4,a,b,c).

a en üstteki diskini c oynat

a en üstteki diskini b oynat

c en üstteki diskini b oynat

a en üstteki diskini c oynat

b en üstteki diskini a oynat

b en üstteki diskini c oynat

a en üstteki diskini c oynat

a en üstteki diskini b oynat

c en üstteki diskini b oynat

c en üstteki diskini a oynat

b en üstteki diskini a oynat

c en üstteki diskini b oynat

a en üstteki diskini c oynat

a en üstteki diskini b oynat

c en üstteki diskini b oynat

true .

?-

Yukarıdaki çalışmadan da görüldüğü üzere ilk baştaki 4 diskin dizili olduğu a çubuğundan bütün diskler sırasıyla b çubuğuna taşınmıştır.

Kodumuz, doğru sıra ile oynama yaklaşımı ile kodlanmıştır. Hanoi kulelerinin farklı çözümleri bulunur. Örneğin geri izleme algoritması (backtracking) kullanarak kaba kuvvetle (brute force) bütün ihtimallerin denendiği ve başarısızlık olması halinde en son iyi duruma geri dönen yaklaşımları kodlamak da mümkündür.

Bizim kodlamamızda ise her seferinde doğru çubuktan doğru diskin oynatılması esası kullanılmıştı. Bu yüzden hiç geri oynama veya yapılan hamleden vaz geçme olmamıştır.

Bu oynama esasını daha iyi anlatabilmek için daha ufak bir örnek üzerinden çalışmayı gösterelim :

?- oyna(2,a,b,c).

a en üstteki diskini c oynat

a en üstteki diskini b oynat

c en üstteki diskini b oynat

true

 

Görüldüğü üzere iki disklik bir dizilimde, c çubuğu geçici olarak kullanılmakta, esas büyük diskin b çubuğuna oynanması sırasında, küçük diskleri depolamak için kullanılmaktadır.

Bu durum disk sayısı artsa da değişmez. En büyük diskin a çubuğundan b çubuğuna oynanması sırasında,  diğer bütün küçük diskleri depolamak için c çubuğunu kullanırız. Buradan anlaşılacağı üzere ikinci büyük diskin c çubuğuna oynaması gerekir. Bunun için de b çubuğunu geçici depolama için kullanırız. Bu yaklaşım en büyük diskten en küçüğüne kadar aynı mantıkla işleyerek devam eder.

8 Vezir Problemi (8 Queens Problem)

Yeni bir problem olarak klasik sorulardan birisi olan 8 vezir problemini ( eight queens problem) ele alalım. Problem basitçe bir satranç tahtasına 8 veziri, birbirini yemeden nasıl yerleştireceğimizdir.

 

Problemin çözümü olan PROLOG kodu aşağıda verilmiştir.

perm([X|Y],Z) :- perm(Y,W), birinial(X,Z,W).

perm([],[]).

 

birinial(X,[X|R],R).

birinial(X,[F|R],[F|S]) :- birinial(X,R,S).

 

cozum(P) :-

     perm([1,2,3,4,5,6,7,8],P),

     birlestir([1,2,3,4,5,6,7,8],P,S,D),

     hepsifarkli(S),

     hepsifarkli(D).

 

birlestir([X1|X],[Y1|Y],[S1|S],[D1|D]) :-

     S1 is X1 +Y1,

     D1 is X1 – Y1,

     birlestir(X,Y,S,D).

birlestir([],[],[],[]).

 

hepsifarkli([X|Y]) :-  +member(X,Y), hepsifarkli(Y).

hepsifarkli([X]).

 

Kodun çalışan örneği aşağıdaki şekildedir:

?- cozum(P).

P = [5, 2, 6, 1, 7, 4, 8, 3] ;

P = [6, 3, 5, 7, 1, 4, 2, 8] ;

P = [6, 4, 7, 1, 3, 5, 2, 8] ;

P = [3, 6, 2, 7, 5, 1, 8, 4] ;

P = [6, 3, 1, 7, 5, 8, 2, 4] ;

P = [6, 2, 7, 1, 3, 5, 8, 4] ;

P = [6, 4, 7, 1, 8, 2, 5, 3] ;

P = [3, 6, 2, 7, 1, 4, 8, 5] ;

P = [6, 3, 7, 2, 4, 8, 1, 5] ;

 

Yukarıdaki örneklerde görüldüğü üzere her kolon için, o kolondaki kaçıncı satıra vezir yerleştirilebileceği ve bu yerleştirme işlemine göre bütün kuralları sağlayan bir dizilimin nasıl elde edileceği listelenmiştir. Problemin birden fazla çözümü olduğu için her satır, çözümlerden birisini göstermektedir. Örneğin ilk çözüm satırını ele alırsak, aşağıdaki gibi bir satranç tahtası elde ederiz.

 

P = [5, 2, 6, 1, 7, 4, 8, 3] ;

Kodda, kabaca bütün ihtimalleri deneyen bir permütasyon algoritması geliştirilmiştir. Ardından koşulların sağlanıp sağlanmadığı kontrol edilmiş ve buna göre koşulları sağlayan ihtimaller sonuç olarak döndürülmüştür.

Algoritma, bir arama algoritması (search algorithm) şeklinde probleme yaklaştığı için, problemin çözümü sırasındaki bütün ihtimaller sadece bir kere denenecek ve denenen bir ihtimal tekrar etmeyecektir. Bu deneme sırası, permütasyon fonksiyonu ile sağlanır.

Yorumlar

  1. tuğçe

    Proje ödevim prolog programlama dilinde 8 vezir probleminin çözümü.Araştırma yaparken sizin sayfanızda projemle ilgili veriler buldum ancak anlamakta güçlük çektim.Sizden rica etsem problemin çözümü için yazdığınız kodlamaları bana biraz anlatabilir misiniz?Yazdığınız basamakların ne demek olduğunu anlatabilir misiniz?

  2. Şadi Evren ŞEKER Article Author

    Bakın, yukarıdaki algoritma, literatürde kaba kuvvet algoritması (brute force algorithm) olarak anılan ve bilgisayarın hızlı çalışması sayesinde, kısa sürede çok fazla ihtimali deneyen yapıdadır. Yani tahta üzerine 8 vezirin yerleştirilebileceği bütün ihtimalleri dener. Bu denemelerden şartı sağlayanları da ekrana basar.

    Adım adım gidecek olursak öncelikle permutasyonun nasıl çalıştığını anlamamız gerekir. Yani 8 vezirin her birisinin farklı bir sutünda olacağını düşünürsek, her sütundaki satırını tutan bir vektör elde edip bunu permute edeceğiz.

    Diğer bir deyişle 8 vezirin 8ininde farklı satır ve sütunlarda olacağını biliyoruz. O halde 1’den 8’e kadar olan sayıların dizilimi bizim için sonuç olacaktır. Yukarıdaki yazıda buna örnek olarak
    P = [5, 2, 6, 1, 7, 4, 8, 3] ;
    satırının nasıl yorumlanması gerektiğini gösterdim. Şimdi bu satırı nasıl permüte ettiğimize bir bakalım:

    perm([X|Y],Z) :- perm(Y,W), birinial(X,Z,W).
    
    perm([],[]).
    
    birinial(X,[X|R],R).
    
    birinial(X,[F|R],[F|S]) :- birinial(X,R,S).
    

    Yukaırda görüldüğü üzere [X|Y] komutu ile liste ikiye bölünmüş ve ilk elemanı X geri kalan elemanları ise Y olarak atanmıştır. Şimdi burada sonuç Z değişkeni ile alınmakta olup Z sadece sonucu döndüren parametredir.

    Özyineli olarak (recursive) geri kalan elemanların da permutasyonunu alıyoruz. Yani elimizde sadece 3 harf olsa permutasyon şu şekilde çalışır:

    permütasyon( a b c ) = a , permütasyon ( b, c) ve permütasyons (b,c) ,a

    Yani listenin ilk elemanı ve geri kalanların permütasyonunu iki farklı şekilde birleştirmek yeterlidir.

    bu işlemler yukarıdaki birinial fonksiyonu tarafından 5. satırda yapılır. Ayrıca listenin daha uzun olması durumunda, alt listelerin de permütasyonları gerekmektedir. Bu da 7. satırda yapılmaktadır. Listenin ilk elemanı haricindekilerinin de ilk elemanı alınarak devam eder.

    Gelelim yukarıdaki 3. satıra, bu satır bir listenin boş olması durumunda permütasyonunun boş liste olduğunu söylemektedir ki bu durum doğrudur.

    Permütasyonları oluşturduktan sonra listedeki elemanların koşulu sağlaması kontrol edilir. Burada birleştir fonksiyonumuz devreye giriyor. Vezirlerin çarpraz olarak birbirini yememesini garanti ediyoruz:

    birlestir([X1|X],[Y1|Y],[S1|S],[D1|D]) :-
    
         S1 is X1 +Y1,
    
         D1 is X1 – Y1,
    
         birlestir(X,Y,S,D).
    
    birlestir([],[],[],[]).
    

    Yukarıdaki kodda, 3. ve 5. satırlarda bir vezirin çarprazları + ve – durumu ile kontrol edilmektedir yani örneğin iki ardışık sayı yan yana gelemez. ve bu durum listenin tamamı için geçerlidir.

    çözüm fonksiyonu ise herşeyin başladığı fonksiyondur:

    cozum(P) :-
    
         perm([1,2,3,4,5,6,7,8],P),
    
         birlestir([1,2,3,4,5,6,7,8],P,S,D),
    
         hepsifarkli(S),
    
         hepsifarkli(D).
    

    burada 3. satırda 1’den 8’e kadar olan sayıların permütasyonu oluşturulmakta sonra bu değer P değişkeninde tutulmaktadır. Ardından çarprazlık kontrolü için birlestir fonksiyonuna verilmekte ve son olarak çarprazlık şartını sağlayan S veya D alt listelerinin elemanlarının tamamını farklı olması kontrol edilmektedir.

  3. Volkan

    Merhaba, yazınızı okudum.Uzun süredir hayalim olan ve her ne kadar uzun sürerse sürsün katlanacağım bir proje yapmak istiyorum.Prolog hakkında hiçbir fikrim yok. Daha önce delphi 7 üzerinde çalıştım %50 oranında hakimim diyebilirim.Fakat yapmak istediğim şey gerçek bir yapay zeka. Yani sorularıma düşünerek cevap verebilen,araştırma yapabilen bilgileri kaydeden vb insana ait özellikleri olan program yazmak istiyorum.Biliyorum biraz çocukça bi fikir gibi gelebilir ama ben yapmak istiyorum. Yaşım 18.Benim ihtiyacım olan şey bu işe temel olarak nasıl başlayabilirim?Prolog dilini nasıl öğrenebilirim?Programımda görsellikte olmasını istiyorum ve sanırım bunun için prolog değil visual prolog kullanmam gerekiyor bu doğru mu? Bu soruların cevaplarını verebilirseniz sevinirim.Araştırmak yetmiyo bunu fark ettim çünkü dışarıdaki bilgiler hep aynı.Sorup öğrenmek daha iyi olur diye düşündüm.Cevaplarsanız sevinirim.

  4. Şadi Evren ŞEKER Article Author

    Ne yalan söyliyeyim, ne diyeceğimi bilemiyorum. Yani moralinizi kırmak istemem, çok büyük ihtimalle, bu yaşlardaki hedefleriniz ve meraklarınız hayatınızın geri kalanını etkileyecek, bu yaşlardan birşeye imkansız demek yapılacak en büyük kötülük olur.

    Kısaca durum şu şekilde, turing testi denilen bir test var, basitçe bir duvarın arkasında iki bilgisayar olduğunu düşünün. Bu bilgisayarlardan birisinde sizin yazdığınız bir yazılım, diğerinde ise bir insan oturuyor olsun. İkisinin de duvarın diğer tarafında bir monitor ve klavyeden ulaşılabildiğini düşünelim. Duvarın diğer tarafındaki bu monitor ve klavyeleri kullanarak birisi hangi monitordekinin insan hangisindekinin yazılım olduğunu bulmak istiyor olsun.

    Bir yazılım ne kadar insan gibi davranıp bu duvarın diğer tarafındaki kişiyi kandırabilir? Şayet tamamen kandırabilirse ve kişi ayırım yapamazsa Turing testi geçilmiş olur.

    Şimdiye kadar geçilemedi. Bunun hiçbir zaman geçilemeyeceğine inananların yanında (ki ben de geçilemeyeceğine inanıyorum) bir gün geçileceğini düşünenler de var. Çok detaya girmek ve teorik açıklamalar yapmak istemiyorum ama basitçe amacınız şayet insan gibi bir bilgisayar yapmak ise, en azından Turing makineleri (Turing Machines) üzerine kurulu günümüz bilgisayar teknolojisi ile yapılamayacağını söyleyebilirim.

    Zaten bu yüzden kuantum bilgisayarları (quantum computing) veya biyolojijk bilgisayarlar üretmeye çalışıyorlar. Gelecek neler gösterecek bilmiyoruz ama bir programlama dili ile (ProLog, LISP veya herhangi başka bir dil de olabilir) basit yapay zeka projeleri ile başlayabilirsiniz.

    Bu sitede yapay zeka başlığı altında çok sayıda algoritma ve problem bulunuyor, bunlara bakabilirsiniz, merakınızı koruduğunuz ve bu konuda araştırdığınız sürece de oldukça iyi bir bilgi birikiminizin olacağını ve bu konuda yapılan çalışmalara katkıda bulunabileceğinizi temin ederim. Basitçe algoritma temellerinden başlayın, yapay zekaya girmeden önce temel algoritmaları (arama, sıralama vs.) ve veri yapılarını öğrenin ardından problemler ve basit yapay zeka algoritmaları ile devam edebilirsiniz.

    Başarılar

  5. Volkan

    Tavsiyeleriniz için çok teşekkür ederim.Fakat beni yanlış anladınız.Benim yapmak istedğim muhteşem ,kusursuz tamamen insan modeli değil.Mesela bir örnekle açıklayabilirim.Ali Murat Erkorkmaz tarafından geliştirilen Compishco adlı programı duymuşsunuzdur.Benim istediğimde böyle bişey yapmak.En azından bir kısmını yapmak.Bunu yaptıktan sonra ,yapabilecek kadar geliştikten sonra daha ileriye götürebilirim ama şimdilik böyle birşey yapmak istiyorum.Bana zaman ayırıp açıkladığınız için teşekkür ederim.

  6. Elif

    Sistemimizde kayıtlı olan bir dosyayı program tarafından açıp çalıştırılır bir şekilde yüklemek için dosya ismi köşeli parantezler içerisinde verilmelidir:

    ?- [‘ilkdosya.pl’].

    Yukarıda, bilgisayarımızda bulunan “ilkdosya.pl” isimli dosyayı sisteme tanıtarak yükledik.

    burayı anlayamadım, dosyanın tanınması için tam yolu nerede olmalı?

Bir cevap yazın

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir