Zeka nedir? Bu kavramın tanımı uzun süre filozofları, matematikçileri ve en sonunda yazılım bilim adamlarını uğraştırdı.
Yapay Zeka olgusu, uzun bir değişim ve ne olduğunu tam bilmeyen bir süreçten geçerek bu günlere geldi. En sonunda üzerinde mutabakat kurulan tanım, yapay zekayı genel ve temel olarak iki kategoriye ayırdı.
Genel zeka altında, insanların bütün zihni güçlerini ve özelliklerini birgün bilgisayar ile kopyalama, yapabilme çabası var. Tabii ki bu arayış uzun bir zaman alacak.
Öteki dal temel zeka adı altında “sadece belli problemler için özel” algoritmalar yaratarak, problem çözebilen bir zeka türü peşinde koşmaktadır. Yani zeki bir vekil yaratıp onu problemin üzerine atmak, ya da ufak bir temsilcimizi, bize benzeyen ufak bir kısmımızı yaratıp, onu problem çözmek ile görevlendirmek diye nitelendirebileceğimiz bir zeka türüdür aranan.
Teknik olarak detaya inersek, gerçek zamanda, sürekli girdi bilgisi işleyerek hareket etmek zorunda olan zeka şeklini temel zeka altında inceliyoruz. Karar verme olgusu bu vekil zeka için çok önemlidir, özellikle belirsizlik altında bile karar verebilmek, vekil sistemler hayati önem taşır.
Örnek Problem
Araştırmacılar, yapay zeka kodlarını denemek için bir deney ortamı ararken, şunu düşündüler. Eğer hayat bir problemler dizisi, çözüm bekleyen sorunlar, takip etmemiz gereken kurallar, ve plan gerektiren çözümler içeriyorsa, bu ortamı benzetimlemenin en rahat yolu nedir?
Şans oyunları! Öyle ya, bir oyun hayatın ufak bir kopyası gibidir, kurallar içerir, bir amaç vardır, plan gerektirir. Yapay zeka araştırmalarının oyun oynamak üzerinde bu kadar durmasının sebebi budur.
8 Taş Oyunu
Yukarıdaki 8 taş oyununu, bilgisayara şöyle tanımlayabiliriz. Başlangıç durumu olan taşları (solda) sonuç durumuna (sağa) dönüştürmek için gerekli olan taş hareketleri bul ve raporla kullanıcıya bildir. Bilgisayar bu sonuca birkac değişik algoritma takip ederek ulaşabilir.
Kör Arama
Kör, ya da mekanik, bir şekilde arama algoritmaları, başlangıç tahta durumu üzerinde yapılabilecek bütün taş hareketlerini işletir ve sonuç tahtasını kayıt eder. Mesela, başlangıç tahtasında 8 yukarı çıkabilir, 4 sağa gidebilir. (Not: Kodlama açısından daha rahat olması için her taşın hareketini değil, boşluğun hareketini baz almak daha rahat olur. Sonuç aynı, ama kodlama daha rahat. Yani, boşluk sola gidebilir, aşagı inebilir). Bu iki mümkün işlemden sonuç olarak iki yeni tahta çıkacak. Onların da üzerinde olası bütün işlemleri yaparsak, daha da fazla tahtalar çıkacak, vs. Bunu yaparken bir yandan sonuç tahtasına gelip gelmediğimizi kontrol edersek, kör bir arama algoritması yazmış olacağız.
Bu işlemlerin sonuçlarını bir ağaç veri yapısı olarak temsil etmek uygun olacak. Yani resimde görülen soldaki tahta üst düğüm, iki hareketten çıkan olası yeni tahtalar o üst düğümün iki çocuğu olarak gösterilebilir. Böyle giderek elimize bir ağaç yapısı çıkacak. Örneği aşağıda,
Ağaç yapısı, birazdan göreceğimiz bütün arama algoritmalarının temelini oluşturacak. Ama, bu ağacı yaratmanın değişik yolları var. Mesela, ağacın her katını mı önce oluşturmak istersiniz, yoksa bir dalı sonuna kadar derinliğine takip etmek, yoksa geri dönüp başka bir dalı mı tekrar derinliğine aramak istersiniz.
LISP’e Giriş
Bu iki yolu, LİSP örnek kodu ile derinliğine inceleyelim. LİSP en eski 2. bilgisayar dilidir, ve Yapay Zeka araştırmaları için yaratılmıştır. LİSP, fonksiyonları bile dinamik olarak yaratıp bildirgeç olarak işlemlere verebilen bir dildir. Bu esnek yapısı yapay zeka araştırmacılarının çok işine yaramıştır.
LISP dilinde temel veri yapısı “listedir”. Mesela, yukarıdaki başlangıç tahtasını LISP’de şöyle tanımlanabiliriz.
-baslangic '((5 4 nil)(6 1 8)(7 3 2))) (setf tahta
Bu kullanımda dikkat ederseniz, bir listenin listesini tanımladık. Yani, liste içeren bir liste. LISP referans kaynaklarından rahatça öğrenilebilir, böylece LISP’in çoğu işleminin liste yapısı üzerinde tanımlanan işlemler için olduğunu göreceksiniz. Zaten LISP’in ismi bile buradan gelir, LIST Processing, türkçesi “liste işlemek”.
Örnek diğer bazı liste işlemleri: (car liste) komutu listenin başındaki değeri, (cdr liste) listenin geri kalan kısmını verir. (nth 2 liste) listenin baştan 3. değerini getirir, (setf liste (append ’a liste)) liste değişkenine ’a harfini ekler, vs..
Ağac yapısındaki her düğümün, arama algoritması için, üst düğümünü hatırlaması gerekiyor. Ayrıca hangi taş kaydırma ile o tahta durumuna geldiğini de hatırlaması gerekiyor. Çünkü sonuca geldiğimizde, oradan tekrar başlangıca dönerek (üstü izleyerek) kaydırma işlemlerini ekrana basarak göstereceğiz. Algoritmanın da amacı bu değil mi? Bilgisayarın sonuca nasıl geldiğini bize göstermesi!
Bu sebeple, yeni büyütülmüş liste (listenin listesi) şu hale geldi. Örnek olarak boşluğu aşağı kaydırarak, geldiğimiz bir tahtayı şöyle gösterelim.
;; listenin icine bakabilen islemler
(Defun Durum (dugum) (first dugum))
(Defun Kaydir (dugum) (second dugum))
(Defun Ust (dugum) (third dugum))
;; ornek bir tahta
1 3 2)(5 4 6)(7 8 nil))
(setq baslangic ((('asagi (((1 3 2)(5 4 nil)(7 8 6))))
;; tahtayi ve islemleri kullanarak dugum hakkinda bazi raporlar
print "kaydir islemi")
(
(kaydir baslangic)
print "ust dugum")
(
(ust baslangic)
print "tahta durumu")
( (durum baslangic)
“Üst” düğümün, çocuk düğümü içine nasıl konduğunu görüyoruz. Ağaçta daha derine indikçe, liste içinde liste, onun içinde liste, onun da içinde liste gibi bu yapı daha da derinleşecektir. C ya da Java gibi dillerinde imleç (pointer) kullanarak aynı şey yapılabilir. Ama LISP bu ağaç yapısı için bile liste kullanıyor. Merak etmeyin, imleç kullanımı kadar da etkili oluyor.
Önce Genişliğine (Breadth-First) ve Önce Derinliğine (Depth-First) Arama
Ağaç yapısını tanımladıktan sonra, algoritmaya gelelim. Kat kat arama algoritmasında, çocuk düğümleri yarattıktan sonra onları “işlenmek üzere beklettiğimiz” bir listeye koyarız. (gene mi liste?) :)
Evet. Bu yapı üzerine ekleme yaparken, ya sonra, ya başa ekleme yapmak mümkün. Eğer sona koyarsak, çocuklar en son girdiği yerden en son çıkacak, eğer başa koyarsak girdiği gibi hemen çıkacaktır. Bu şekilde kullanımın birincisi, listeyi kuyruk (queue) olarak, ikincisi yığıt (stack) olarak kullanmak anlamına gelir. Yazılım bilimde bu iki olgu çok temeldir. Her algoritma kitabında kuyruklar ve yığıtlar hakkında bilgi alabilirsiniz. Sonuçta, çocukları yığıt üzerinde bekletmişsek, arama önce genişliğine arama olur, kuyruk olarak bekletmişsek arama “önce derinliğine” arama olur.
Bu iki arama şeklinin farkı niçin önemlidir? Burada esas sormamız gereken şu olacak. Hangi arama şekli daha başarılıdır?
Bu sorunun cevabı algoritmik analiz ile verilebilir, fakat özet olarak belirtmek gerekir ki, önce genişliğine aramak istatistiki olarak daha başarılı oluyor. Derinliğine arama, ek başka algoritmalar ile destekli olarak da başarılı olabiliyor.
Gereken Kodlar ve Programlar
Ekteki dosyalar LISP derleyicisi/yorumlayıcısi ve örnek kodlar içeriyor.
Önce genişliğine aramayı, derinliğine aramaya çevirmek için tek yapmanız gereken yığıtı, kuyruğa çevirmektir.
Bir önceki yapay zeka yazısı, akıllı bilgisayarlar hakkında hayal kırıklığı yaratmış olabilir. Sonuçta gösterdiğimiz algoritma, derinliğine ya da önce genişliğine arasa bile, “bütün” sonuçları deniyor! Yani insan ile yarışmak için aslında hafıza genişliğinden ve hesap hızından yararlanıyor. Peki nerede zeka?
Bunu düşündüyseniz haklısınız. Hakikaten de, bu ilk bahsettiğimiz algoritmalar “kaba-kuvvet algoritmaları” diye anılır. Direk ileri giderler, ve gayet mekanik şekilde sonuca ulaşmaya uğraşırlar.
Fakat, bir insan olarak biliyoruz ki, akıllı olmanın bir özelliği de öğrenmektir. Yani, bazı kısa yollar bulmak, bir takım dersler çıkartarak sonuca daha hızlı ulaşmayı sağlamak insanların gayet doğal yaptığı şeylerdir. Eğer bunlar kodlanmamışsa, oyun oynayan algoritmamız kaba kuvvetten daha ileri gidemeyecek. Üstelik büyük problemler için o üstün hızı bile yetişmeyebilir!
Pekala. Hadi o zaman şu programa biraz akıl verelim.
İzlenen Yolun Fiyatı
Algoritmamızın “arama” algoritmasını olarak isimlendirilmesinin sebebi, mümkün olan birçok seçenek arasından kısa olanı bulmak için “arama” yapmasıdır. Bilgisayarın önünde olan birçok seçeneğin her birinin fiyatı, yani uzunluğu, birbirinden farklıdır. Akıllı bir programa lazım olan, bu yollardan en kısa olanını bulmaktır. İnsanlar da, kendi düşüncelerini hızlandırmak için birtakım yan algoritmalar geliştirirler ve çabuk sonuca ulaşmaya uğraşırlar.
Bu fiyatı iki türlü ölçebiliriz. Birincisi, karar ağacında çözümü ararken o an üzerinde bulunduğumuz düğüme gelmek için ödediğimiz fiyat (katedilen yol), öteki de önümüzde katedeceğimiz geri kalan yoldur.
Katedilen yolun seçimde (arayışta) ne yararı var diye düşünebilirsiniz. Eklemek gerekir ki, özellikle önce-derinliğine arama algoritması bazen aynı düğüme değişik yollardan ulaşabiliyor. Bu gibi durumlarda tuttuğumuz kayıtlarda aynı düğümü bulursak, ve bu düğümün içerdiği yol daha pahalı ise, eskiyi listeden atıp, yerine yeni düğümü koymamız gerekiyor.
Nihayet akıllı bir “seçim” yaptık.
Fakat hala geriye bakıyoruz. İleriye bakarak, bilgili bir tahminde hala bulunmadık. İleriye dönük bir tahmin fonksiyonunu nasıl bilgisayarda kodlarız? 8’li Bulmaca oyununu düşünürsek; oyunun herhangi bir seviyesinde tahtaya bakarak, en iyi yapılacak hareketi nasıl bulabiliriz?
Akıllı Tahmin
Öyle bir fonksiyon bulalım ki, elimizde olan düğümden yarattığımız çocuk düğümler arasında hangisini takip edeceğimizi bize söylesin. Sözde program şöyle olabilir.
Pekala, nedir bu uzaklık değeri? İşte akıl devreye burada giriyor.
Her tahta durumunun sonuca uzaklığı, tahmini olarak şöyle hesaplanabilir. Mesela, başlangıçtaki her taşı, sonuç tahtasına bakarak bulalım. Eğer sonuç tahtasındaki taş, başlangıçtaki aynı yerde değil ise, ne kadar uzakta olduğunu bulalım.
Üstteki iki tahta arasında, bu uzaklık değeri “5” taşı için “4” olacaktır. Çünkü 1,1 eksen konumundan 3,3 konumuna gitmiştir. Ve aradaki fark 2 aşağı 2 sağa gittiğimiz için 4’tür. Bu tür uzaklık hesabına Manhattan uzaklığı deniyor, çünkü hepsi eşit bloklar arasında yürüyerek giderken ölçülen türden bir hesap çeşididir.
Bu uzaklık hesabı, bir nevi şunu beyan etmektir - bu tahtayı, sonuç tahtasına çevirmek için bu kadar hamle yapmak gerekiyor. Tabii ki bu hesap kesin bir hesap değildir. Tam doğru da değildir, ama, olması da gerekmez. Yeteri kadar doğru, ve en önemlisi, hiç bir zaman fazla keseden atmayan bir hesap doğru seçim için yeterlidir. Çünkü, aynı şekilde “tam doğru olmayan hesapları” öteki seçenekler için de yapıyoruz! Yani, birbirine olan izafi bir doğruluk, sayının tamamen doğru olması etkisi yapar.
LISP kodu
Ekteki kodlarda göreceğiniz gibi, LISP kodu için 2 tane fonksiyon tanımlamak gerekti. G-güncel değişkeni ‘geriye bakan’ türden olan fiyatı-sabit-arama algoritması için zaten gerekiyordu. Ekte olmayan, ama konu hakkında görebileceğiniz bir algoritma sırf tahmine dayanarak seçim yapmaya uğraşır, yani sadece t-guncel değerini kullanır. En güçlü olan yöntem, g-guncel ve t-guncel’in ‘toplamına’ dayanarak seçim yapmaktır. Böylece hem o ana kadar gözlediğimiz ölçümü, hem de ileriye bakarak yaptığımız tahmini aynı anda gözönüne almıs oluyoruz.
İki hesabın birleşimine dayanarak seçim yapan arama algoritmasına A* (a yıldız) algoritması denir. Bu kodu da a-yildiz-arama.lisp altında bulabilirsiniz.
Ayrıca, ödev olarak (yapay zeka dersi için) bizim kodladığımız, A*’ı kendi akıl fonksiyonu ile genişletip, kendi t-guncel kodunu yazmamız gerekiyordu.
Bu yeni A* t-guncel hesabı, hem taş uzaklığına dayanıyor, fakat bir toplam daha ekliyor. Eğer iki taşı değiş tokuş yaptırmamız gerekiyorsa, bu normal uzaklıktan çok daha pahalı bir işlemdir, ve 2 sayılması gerekir! Bu şekilde yapılan toplamın, ve akabinde t-guncel değerinin, algoritmayı daha geliştirdiğini göreceksiniz.
Yani biraz daha akıl kullanarak, işimizi kolaylaştırmış oluyoruz.
(defvar s0)
(defvar s1)-bulma-seansi nil)
(defvar hata-sayisi 0)
(defvar kaydir
(Defun Durum (dugum) (first dugum))
(Defun Kaydir (dugum) (second dugum))
(Defun Ust (dugum) (third dugum)) 0 (nth 4 durum)) )
(defun nx (durum) (nth 1 (nth 4 durum)) )
(defun ny (durum) (nth
-yerini-guncellestir (dugum x y)
(defun nillist (nx dugum) (ny dugum))
(setf dugum (remove (#'equal ))
dugum :test list (list x y))))
(setf dugum (append dugum (
)
;;
;; X ve Y eksen degerlerine bore liste uzerinde degis tokus
;; yap. Boylece LISP'de cok kullanilan bir suru car ve cdr
;; kullanmaya gerek kalmiyor.
;;
-tokus-xy (matris x1 y1 x2 y2)
(defun degis
(let (( gecici (nth y1 (nth x1 matris))))
(setf (nth y1 (nth x1 matris)) (nth y2 (nth x2 matris)))
(setf (nth y2 (nth x2 matris)) gecici)
matris
))
;;
;; Eger verilen noktada MIL var ise, geriye T (dogru) cevabi gonder.
-xy(matris x y)
(defun null
(null (nth y (nth x matris))))
;;
;; cocuklari toplayan (yaratan) islem.
;;
-getiren-islem (dugum)
(defun cocuklari-son-dugums nil) (son-durum nil) (durum (first dugum)) )
(let ( (result
-durum (kaydir-yukari durum))
(setf son-son-dugums (list (list son-durum 'yukari dugum)))
(setf result
(setf son-durum (kaydir-asagi durum))
(setf result-son-dugums
(append result-son-dugums (list (list son-durum 'asagi dugum))))
(setf son-durum (kaydir-saga durum))
(setf result-son-dugums
(append result-son-dugums (list (list son-durum 'saga dugum))))
(setf son-durum (kaydir-sola durum))
(setf result-son-dugums
(append result-son-dugums (list (list son-durum 'sola dugum))))
(setq kaydir-sayisi (+ kaydir-sayisi (length result-son-dugums)))
result-son-dugums)) ;;and that's it Son-dugums is returned
;;by the function
;;
;; copy wan't provided in my version of lisp.
;;
(defun copy (obj)
(cond ( (null obj) nil)
( (listp obj) (cons (copy (first obj)) (copy (rest obj))))
( t obj) ) )
;;
;; My lisp has not defined this macro
;;
(defun caadddr (x)
(car(car(cdr(cdr(cdr x))))))
;;
;; the yukari kaydir
-yukari (Ust-durum)
(defun kaydir-durum)))
(let ((durum (copy Ust
(cond 0) nil)
((eql (nx durum)
(t-tokus-xy durum
(degis- (nx durum) 1)
(
(ny durum)
(nx durum)
(ny durum))-yerini-guncellestir durum (- (nx durum) 1)
(setf durum (nil
(ny durum)))
)
)
durum))
;;
;; the asagi kaydir
-asagi (Ust-durum)
(defun kaydir-durum)))
(let ((durum (copy Ust
(cond 3) nil)
((eql (nx durum)
(t-tokus-xy durum
(degis+ 1 (nx durum))
(
(ny durum)
(nx durum)
(ny durum))-yerini-guncellestir
(setf durum (nil+ (nx durum) 1) (ny durum)))))
durum (
durum))
;;
;; the saga kaydir
-saga (Ust-durum)
(defun kaydir-durum)))
(let ((durum (copy Ust
(cond 3) nil)
((eql (ny durum)
(t-tokus-xy durum
(degis
(nx durum)+ 1 (ny durum))
(
(nx durum)
(ny durum))-yerini-guncellestir
(setf durum (nil+ 1 (ny durum))))))
durum (nx durum) (
durum))
;;
;; the sola kaydir
-sola (Ust-durum)
(defun kaydir-durum)))
(let ((durum (copy Ust
(cond 0) nil)
((eql (ny durum)
(t-tokus-xy durum
(degis
(nx durum)- (ny durum) 1)
(
(nx durum)
(ny durum))-yerini-guncellestir
(setf durum (nil- (ny durum) 1) ))))
durum (nx durum) (
durum))
;;
;; Trace
-izini-bul (dugum)
(defun sonucprint "Cozumun Baslangici") nil)
(cond ((null dugum) (
(t -izini-bul (Ust dugum))
(sonucprint (Kaydir dugum)))))
(
;;
;; funds the difference between two sets
(defun diff (x y)
(cond ((null x) nil)not (member (first x) y :test #'equal ))
((
(cons (first x)
(diff (rest x) y)))
(t (diff (rest x) y))))
;;
;; show # of elements in lists and number of dugums generated.
-raporu-ver (acik tamamlanan baslangic)
(defun sonucprint "ACIK listesindeki dugum sayisi")
(print (length acik))
(print "TAMAMLANAN listesindeki dugum sayisi")
(print (length tamamlanan))
(print "Toplam Yaratilan Dugum Sayisi")
(print kaydir-sayisi)
(
)
;;
;; show # of elements depending on the debug flag status
-dugum-yarattik()
(defun kac-bulma-seansi T)
(when (eql hataprint "Su anda hafizada bu kadar dugum var")
(print kaydir-sayisi))
(
)
;;
;; test evaluator function
(defun test (isim exp sonuc)
(cond
((equal exp sonuc) t)print isim) (error "HATA! Birim test calismadi! "))
(t (
))
;;
;; tests
;;
'((1 3 3 1) (2 6 4 1) (5 8 2 1)))
(setq s0 (test "copy" (copy s0) '((1 3 3 1) (2 6 4 1) (5 8 2 1)))
(setq s0 '((1 3 3) (2 6 4) (5 8 nil)(2 2)))
(test "degis-tokus xy 1" (degis-tokus-xy s0 2 2 1 2)
'((1 3 3) (2 6 NIL) (5 8 4)(2 2)))
'((1 3 3) (2 6 4) (5 8 nil)(2 2)))
(setq s0 (test "null xy" (null-xy s0 2 2) t)
(setq s0 '((1 3 3 1) (2 6 4 1) (5 8 nil 1)(1 1 1 1)(2 2)))
(test "yukari kaydir 1 test" (kaydir-yukari s0)
'((1 3 3 1)(2 6 nil 1)(5 8 4 1)(1 1 1 1)(1 2)))
'((1 3 3 1) (2 6 4 1) (5 nil 4 1)(1 1 1 1)(2 1)))
(setq s0 (test "yukari kaydir 2 test" (kaydir-yukari s0)
'((1 3 3 1)(2 nil 4 1)(5 6 4 1)(1 1 1 1)(1 1)))
'((1 3 nil 1) (2 6 4 1) (5 8 4 1)(1 1 1 1)(0 2)))
(setq s0 (test "asagi kaydir 1 test" (kaydir-asagi s0)
'((1 3 4 1)(2 6 nil 1)(5 8 4 1)(1 1 1 1)(1 2)))
'((1 3 3 1)(2 6 4 1)(5 8 nil 1)(1 1 1 1)(2 2)))
(setq s0 (test "degis-tokus xy 2" (degis-tokus-xy s0 1 1 2 1)
'((1 3 3 1)(2 8 4 1)(5 6 nil 1)(1 1 1 1)(2 2)))
'((1 3 3 1) (2 nil 4 1) (5 5 4 1)(1 1 1 1)(1 1)))
(setq s0 (test "asagi kaydir 2 test" (kaydir-asagi s0)
'((1 3 3 1)(2 5 4 1)(5 nil 4 1)(1 1 1 1)(2 1)))
'((1 nil 3 1) (2 3 4 1) (5 5 4 1)(1 1 1 1)(0 1)))
(setq s0 (test "saga kaydir 1 test" (kaydir-saga s0)
'((1 3 nil 1)(2 3 4 1)(5 5 4 1)(1 1 1 1)(0 2)))
'((1 3 3 1) (2 nil 4 1) (5 5 4 1)(1 1 1 1)(1 1)))
(setq s0 (test "saga kaydir 2 test" (kaydir-saga s0)
'((1 3 3 1)(2 4 nil 1)(5 5 4 1)(1 1 1 1)(1 2)))
'((1 nil 3 1) (2 3 4 1) (5 5 4 1)(1 1 1 1)(0 1)))
(setq s0 (test "sola kaydir 1 test" (kaydir-sola s0)
'((nil 1 3 1)(2 3 4 1)(5 5 4 1)(1 1 1 1)(0 0)))
'((1 3 3 1) (2 nil 4 1)(5 5 4 1)(1 1 1 1)(1 1)))
(setq s0 (test "sola kaydir 2 test" (kaydir-sola s0)
'((1 3 3 1)(nil 2 4 1)(5 5 4 1)(1 1 1 1)(1 0)))
'((1 3 3) (2 nil 4) (5 5 4)))
(setq s0 (setq s0 (append s0 '((2 3 4))))
(test "ekleme testi" s0 '((1 3 3) (2 nil 4) (5 5 4)(2 3 4)) )
(setq s0 '((1 3 3 1) (2 nil 4 1) (5 5 4 1)(1 1 1 1)(1 1)))
(setq s0 (list s0 nil nil))
(setq s1 '((((1 NIL 3 1) (2 3 4 1) (5 5 4 1) (1 1 1 1) (0 1)) YUKARI
(((1 3 3 1) (2 NIL 4 1) (5 5 4 1) (1 1 1 1) (1 1)) NIL NIL))
1 3 3 1) (2 5 4 1) (5 NIL 4 1) (1 1 1 1) (2 1)) ASAGI
(((1 3 3 1) (2 NIL 4 1) (5 5 4 1) (1 1 1 1) (1 1)) NIL NIL))
(((1 3 3 1) (2 4 NIL 1) (5 5 4 1) (1 1 1 1) (1 2)) SAGA
(((1 3 3 1) (2 NIL 4 1) (5 5 4 1) (1 1 1 1) (1 1)) NIL NIL))
(((1 3 3 1) (NIL 2 4 1) (5 5 4 1) (1 1 1 1) (1 0)) SOLA
(((1 3 3 1) (2 NIL 4 1) (5 5 4 1) (1 1 1 1) (1 1)) NIL NIL))))
((("cocuk dugum bulucu islemi test" (cocuklari-getiren-islem s0) s1)
(test
'((1 NIL 3 1) (2 3 4 1) (5 5 4 1)(1 1 1 1)(0 1)))
(setq s0 (setq s1 '((1 NIL 3 1) (2 3 4 1) (5 5 4 1)(1 1 1 1)(0 1)))
(test "durum equality" (equal s0 s1) t)
(setq s0 '(((1 NIL 3 1) (2 3 4 1) (5 5 4 1)(1 1 1 1))
YUKARI (((1 3 3 1) (2 NIL 4 1) (5 5 4 1)(1 1 1 1)) NIL NIL)))
"durum test" (equal (durum s0)
(test '((1 NIL 3 1) (2 3 4 1) (5 5 4 1)(1 1 1 1))) t)
(setf s0 '((((1 3 3 1) (2 NIL 4 1) (5 5 4 1)(1 1 1 1 )(1 1)) NIL NIL)
(((1 3 3 1) (2 3 4 1) (5 5 4 1)(1 1 1 1)(1 1)) NIL NIL)
1 3 3 1) (2 5 4 1) (5 5 4 1)(1 1 1 1)(1 1)) NIL NIL)))
((('((((1 3 3 1) (2 NIL 4 1) (5 5 4 1)(1 1 1 1)(1 1)) NIL NIL)
(setq s1 (((1 3 3 1) (2 5 4 1) (6 6 6 1)(1 1 1 1)(1 1)) NIL NIL)) )
"diff test" (diff s1 s0)
(test '((((1 3 3 1) (2 5 4 1) (6 6 6 1)(1 1 1 1)(1 1)) NIL NIL)) )
(print "OLDU. Ortak Birim Testler Basari Ile Calisti")
"ortak.lisp")
(load
;;
;; her kati arayip, bitince sonraki katta arama yapmak.
-kat-ara (d0 ds cocuklar)
(defun kat
;; dikkat edin, icerideki liste bir dugum
list (list d0 nil nil) ) )
(let ( ( acik (
( tamamlanmis nil )
( n nil )
( kizlar nil )) -sayisi 0)
(setq kaydir
(loop if (null acik) (return 'hata)) ;;hata var, geri rapor ver
(
;; ilk dugumu cikart
(setf n (pop acik))
;; tamamlanmis listesine n dugumunu koy, cunku birazdan onu
;; isleyecegiz
(push n tamamlanmis)
;; sonuc dugumune geldik mi? (bulduk mu?)
(when (equal (durum n) ds)print "Sonuc bulundu. Nasil buldugumuz asagida")
(-raporu-ver acik tamamlanmis d0)
(sonucreturn (sonuc-izini-bul n))
(
)
;; iste burada yeni cocuk dugumler cikartiyoruz
apply cocuklar (list n)))
(setf kizlar (
;; hata ayiklama icin lazim olabilir
-dugum-yarattik)
(kac
;; iki kere tekrar eden dugumleri cikar. (DIFF=fark demektir, iki
;; liste arasindaki benzerleri cikartir, farki getirir.
(setf kizlar
(DIFF kizlar (append acik tamamlanmis)))
;; dikkat: yeni dugumleri listenin SONUNA koyuyoruz yazilim
;; bilimde buna 'kuyruk' veri yapisi denir. Yani, kuyruga son
;; giren, son cikar. Yukarida 'pop (cikart)' deyince su anda
;; koydugumuz deger gelmeyecek. (liste dolu ise). Eger bu noktada
;; kuyruk yapisi kullaniliyorsa, bu algoritmayi kat-kat arama
;; haline cevirecek.
(setf acik (append acik kizlar))
)))
;;
;; testler
;;
'((1 NIL 3 1) (2 3 4 1) (5 5 4 1)(1 1 1 1)(0 1)))
(setq d0 (setq ds '((1 3 4 1) (2 3 NIL 1) (5 5 4 1)(1 1 1 1)(1 2)))
(test "basit kat-kat-ara"
(not (eql (kat-kat-ara d0 ds #'cocuklari-getiren-islem) 'hata)) t )
print "OLDU. KAT-KAT-ARA Testleri Calisti") (
"ortak.lisp")
(load
-engelli-da (node goal succesors depth)
(defun kat
;;Hmmmm...where did Open, Closed and N go?
(block
DBDFS (let ((daughters nil) )
if (equal (durum node) goal)
(return-from DBDFS (sonuc-izini-bul node)))
(
;;bottomed out in the search space
if (= depth 1) (return-from DBDFS nil))
(;;without finding a goal down this path
;;presumably we have a LIST of derived
-getiren-islem node))
(setf daughters (cocuklari;;here we generate new derived durums
;; debugging
-dugum-yarattik)
(kac
;;so we iterate down them looking for
(loop ;;a solution path...this could easily
;;be changed to a do form....
;;failed to find a solution
if (null daughters) (return-from DBDFS nil))
(
if (kat-engelli-da ;;recursive call with
(;;the first of daughters& daughters updated
(pop daughters) ;;same old goal durum
goal ;;same old set of operators
daughters - depth 1)) ;;but a shallower depth!
(
;;here we did find a solution so we leave happy
return-from DBDFS t)
(
;;;;end if
) ;;;;ends loop
) ;;ends let
) ;; ends block
) ;;ends defun {otherwise known as "]" :) }
)
;;
;; outside method
;;
-kat-arama (d0 ds cocuklar derinlik-limiti)
(defun kat-sayisi 0)
(setf kaydir-engelli-da (list d0 nil nil) ds cocuklar derinlik-limiti)
(katprint "kac dugum yaratildi")
(print kaydir-sayisi)
(
)
;;
;; outside method for iterative deepening
;;
-icin-kka (d0 dg cocuklar derinlik-limiti)
(defun gitgide-engelli-da (list d0 nil nil) ds cocuklar derinlik-limiti)
(kat
)
;;
;; tests
;;
'((1 NIL 3 1) (2 3 4 1) (5 5 4 1)(1 1 1 1)(0 1)))
(setq s0 (setq s1 '((1 3 4 1) (2 3 NIL 1) (5 5 4 1)(1 1 1 1)(1 2)))
(test "kka derinlik limiti" (not (eql (kat-kat-arama s0 s1 nil 3) 'fail)) t )
(print "OLDU. Kat Engelli Kat-Kat Arama Basari Ile Gecti")
"ortak.lisp")
(load
-yonlu-ara (di ds ileriden-cocuklar geriden-cocuklar)
(defun iki-i (list (list di nil nil) ) ) ;;dikkat ic liste bir
(let ( ( acik;;dugum
-g (list (list ds nil nil) ) )
( acik;;tamamlanan listesine ihtiyac yok
( nf nil )
( nb nil )-i nil )
( kizlar-g nil )
( kizlar-dugum nil ))
( ortak
-sayisi 0)
(setq kaydir
(loop
(condor (null acik-i) (null acik-g)) ;;arama uzayini bitirdik mi?
((print "Sorry, the problem posed is insoluable")
(return nil)))
(
;;Evet. Ilk dugumu cikart ve Acik listeyi guncellestir
-i))
(setf nf (pop acik
;;agaclar icin tamamlanan listesine ihtiyac yok
-dugum (member nf acik-g :test #'durum-karsilastirici))
(setf ortak-dugum
(when ortak;; bu dugumu, geri gelen tarafta bulduk mu?
print "Harika. Sonuc Bulundu:")
(-izini-bul nf)
(sonuc-izini-bul-geri (first ortak-dugum))
(sonuc-raporu-ver acik-i acik-g nil nil)
(sonucreturn ortak-dugum))
(
;; burada yeni dugumler cikartiyoruz
-i (apply ileriden-cocuklar (list nf)))
(setf kizlar
;; hata bulmak icin rapor
-dugum-yarattik)
(kac
;; acik liste kuyruk olarak kullaniliyor, o yuzden algoritma
;; esasen kat-kat arama.
-i (append acik-i kizlar-i))
(setf acik
;;Tamam, ilk dugumu cikar, acik listeyi guncellestir
-g))
(setf nb (pop acik
-dugum (member nb acik-i :test #'durum-karsilastirici))
(setf ortak-dugum
(when ortak;; durum, ileri giden kisimda bulundu mu?
print "Harika. Sonuc Bulundu:")
(-izini-bul nb)
(sonuc-izini-bul-geri (first ortak-dugum))
(sonuc-raporu-ver acik-i acik-g nil nil)
(sonucreturn ortak-dugum))
(
;;burada yeni cocuklar yaratiyoruz
-g (apply geriden-cocuklar (list nb)))
(setf kizlar
;; hata bulmak icin rapor
-dugum-yarattik)
(kac
;;acik kuyruk olarak kullaniliyor, o yuzden kat-kat arama yapmis
;;oluyoruz
-g (append acik-g kizlar-g))
(setf acik
;;closes loop
) ;;closes let
) ;; closes defun
)
;;
;; geri giden algorithmanin izini buluyor
;;
-izini-bul-geri (dugum)
(defun sonucprint "Geri giden sonucu izliyoruz") nil)
(cond ((null dugum) (
(t if (equal 'north (Kaydir dugum)) (print 'asagi))
(if (equal 'east (Kaydir dugum)) (print 'sola))
(if (equal 'west (Kaydir dugum)) (print 'saga))
(if (equal 'south (Kaydir dugum)) (print 'yukari))
(-izini-bul-geri (Ust dugum))
(sonuc
)))
;;
;; iki dugumun 'icine bakarak' durumlarini karsilastiriyor
;;
-karsilastirici (a b)
(defun durumif (equal (durum a)(durum b)) b))
(
;;
;; iki yonlu arama icin bu islemi tekrar tanimlamak gerekti..
;;
-raporu-ver (acik-i acik-g start end)
(defun sonucprint "# of items in OPEN FORWARD")
(print (length acik-i))
(print "# of items in OPEN BACKWARD")
(print (length acik-g))
(print "# of items in TOTAL nodes")
(print kaydir-sayisi)
(
)
;;
;; testler
;;
'((1 2 3 4) (5 6 0 8) (9 10 7 11) (13 14 15 12) (1 2)))
(setq d0 (setq ds '((1 2 3 4) (5 6 7 8) (9 10 11 12) (13 14 15 0) (3 3)))
(test "bi-directional"
(not (eql (iki-yonlu-ara d0
ds'cocuklari-getiren-islem
'cocuklari-getiren-islem) 'hata)) t )
print "Oldu. Iki Yonlu Arama Testleri Gecti") (
"ortak.lisp")
(load "kat-engelli-da.lisp")
(load
;;
;; Bu sekilde kat-kat arama, kat-engelli-kka islemini cagiriyor. Bu
;; cagirmayi yaparken, her seferinde yeni bir derinlik limiti veriyor.
;; Yani, kat engeli 1 ile cagiriyoruz, sonuc bulursak guzel.
;; Bulamazsak, kat engeli 2 ile.. vs, vs.
-derinlesen-kka (s0 sg sons depth ARTIS-OLCUSU)
(defun gitgide
(block Bif (gitgide-icin-kka s0 sg sons depth) ;call dfs directly to depth
(return-from B t)) ;solution found if dfs is true, so return t
(
-derinlesen-kka ;else, try again but more deeply!
(gitgide;the same initial state
s0 ;the same old goal state
sg ;the same old set of operators
sons + depth ARTIS-OLCUSU) ;but now a deeper search!
(-OLCUSU) ;and increment again later if you don't succeed
ARTIS
) ;; ends block
);ends defun
(defun gitgide-derinlesen-kka-disyuz (s0 sg sons depth ARTIS-OLCUSU)
(setf kaydir-sayisi 0)
(gitgide-derinlesen-kka s0 sg sons depth ARTIS-OLCUSU)
(print "# of nodes")
(print kaydir-sayisi)
)
;;
;; tests
;;
'((1 NIL 3 1) (2 3 4 1) (5 5 4 1)(1 1 1 1)(0 1)))
(setq s0 (setq s1 '((1 3 4 1) (2 3 NIL 1) (5 5 4 1)(1 1 1 1)(1 2)))
(test "dfs iterative deepening"
(not (eql (gitgide-derinlesen-kka-disyuz s0 s1 nil 1 1) 'fail)) t )
(print "OK. Gitgide Derinlesen DA Testleri Isliyor")
"ortak.lisp")
(load
;; Fiyati sabit arama islemi, baslangictan sonuca giden en kisa yolu
;; bulmaya ugrasir. En kisa derken, bahsettigimiz, algoritmanin daldan
;; dala atlarken (dugumleri takip ederken) her dal fiyatinin 1 degeri
;; tasidigi algoritmadan bahsediyoruz. Bu '1' degerleri her atlayista
;; toplanir, ve, ayni dugume degisik bir yoldan gelinecek olursa, eski
;; deger (ve eski dugumun) atilip, en kisa dugumun, yani yolun,
;; kullanilmasi gerekir. Katedilen yol miktari, G-Guncel
;; degiskeninde, her dugum icinde saklanir.
;; Dugum temsil seklini
;; (Durum Kaydir-Ismi G-Guncel Ust-Dugum)
;; olarak degistirmemiz gerekiyor.
;; bu yuzden yeni erisim islemlerini tanimlayalim.
(Defun Durum (node) (first node))
(Defun Kaydir (node) (second node))-guncel (node) (third node))
(Defun G
(Defun Ust (node) (fourth node))
;;
;; Fiyati sabit arama sirasinda her dugumun fiyati, ust dugum
;; fiyati + 1 olarak hesaplanir. Burada sadece 1 degeri geri veriyoruz.
1)
(defun FIYAT (ust cocuk)
;;
;; Unutmayalim; cocuklari-yaratan islemi de degistirmemiz gerekecek.
;; Cunku artik FIYAT degeri, problem cozumunun bir parcasi oldu.
;;
-sabit-arama (d0 ds cocuklar)
(defun fiyati;; ic-liste aslinda bir dugum
(let ( ( acik list (list s0 nil 0 nil)))
(;;g-guncel burada 0
( tamamlanan nil )
( n nil )
( kizlar nil ))
-sayisi 0)
(setq kaydir
(loopif (null acik) (return 'hata))
(
;; Oldu. Ilk dugumu cikart.
(setf n (pop acik))
;; acik listesini guncellestir
;; n dugumunu tamamlanan listesine ekle
(push n tamamlanan)
;; Dikkat ederseniz, acik ve tamamlanan listelerini tutmamizin
;; sebebi, ayni dugumlere tekrar tekrar gelmeyi engellemek. Bu
;; listelerde kaydedilmis dugumleri bir daha islemiyoruz.
if (equal (durum n) ds) ;;have we found our goal state?
(
(let () print "Sonuc Bulundu. Iste Asagida:")
(return (sonuc-izini-bul n))))
(
;; yeni cocuk dugumler yaratiyoruz
apply cocuklar (list n)))
(setf kizlar (
;; rapor verme kismi
-dugum-yarattik)
(kac
(setf kizlar;; Tekrar eden dugumleri cikart.
(DIFF kizlar tamamlanan))
;; Unutmayin, ayni dugume tekrar geldiysek, bu yeni yol
;; mutlaka eskisinden daha uzun olacaktir. Boylece, tek yapmamiz
;; gereken bu dugumu acik listesinden cikartmak.
(setf acik (UPDATE kizlar acik))
;; Acik listesini her dugumun G-guncel degerine gore
;; siraya diz. En azdan, en coga gore.
(setf acik #'(lambda(dugum1 dugum2)
(sort acik < (g-guncel dugum1) (g-guncel dugum2))) ))
(
;; Boylece ilk dugumu aldigimizda, bu dugumun fiyati en az
;; olan dugum oldugu garanti.
;; loop sonu
) ;;let sonu
) ;;defun sonu
)
(defun UPDATE (kizlar acik)
-eski-m nil) )
(let ( ( m nil ) (bulunmus
(loop
;; hepsini islediysek, isimiz bitti..
if (null kizlar) (return acik))
(
;;ilk dugum uzerinde islem yapalim
(setf m (pop kizlar))
-eski-m
(setf bulunmus-DURUM (durum m) acik)) ;; acikta bulduk mu?
(MEMBER
;; oyle ise, bulunmus-eski-m degeri acik listesinin bir
;; alt-listesi olacak.
if bulunmus-eski-m ;; eski m acik listede bulundu ise
(;; durum degeri ayni olan dugumu al
-m (first bulunmus-eski-m)))
(let ((old;;yeni cocuk degeri g-guncel degeri
if (< (g-guncel m) (g-guncel old-m))
(;; daha ucuz ise yeni dugumu tutmak lazim
;; eski dugumu ise yaramaz haline cevir
;; yeni cocuk m ile degistir
;; Dikkat edelim, bu sonuc ACIK listesine
;; kalici bir degisiklik yapacak.
-eski-m) m) ))
(setf (first bulunmus
;; yoksa ayni degerde eski dugum bulamadik
(push m acik)
)
;; o zaman m dugumunu acik listeye ekle.
;; loop sonu, sonraki dugumu dene
) ;;let sonu
) ;;defun sonu
)
;;
;;Bu islem, sadece icinde dugum bulunan alt-listeyi geri getiriyor.
;;Yani bu listenin icindeki 'durum' bildirgec olarak verilen durum
;;ile ayni ise geri veriliyor
-DURUM (durum dugum-listesi)
(Defun MEMBERif (null dugum-listesi) ;;if exhausted then
(;;return nil
nil if (equal durum (first dugum-listesi)) ;;else if we find one
(-listesi ;;return where we found it
dugum;;else keep looking recursively
-DURUM durum (rest dugum-listesi)))))
(MEMBER
-getiren-islem (dugum)
(defun cocuklari-cocuk-dugumler nil)
(let ( (butun-dugumler nil)
(cocuk-durumlar nil)
(cocuk
(durum (first dugum)) )
;;Dikkat: Yeni ogul dugumun G-guncel degeri nasil degistiriliyor.
;;Ust dugumun g-guncel degeri, arti oglan dugume gelmenin fiyati
;;Bu FIYAT formulu her algoritmaya gore degisik
;;olabilir. Fiyati-sabit-arama icin tanim boyledir.
;; yukari
;;apply problem dependent operator 1
-durumlar (kaydir-yukari durum))
(setf cocuk
-dugumler (list (list
(setf cocuk-durumlar 'north
cocuk (+ (g-guncel dugum)
-durumlar))
(FIYAT (durum dugum) cocuk
dugum)))
-cocuk-dugumler (append butun-cocuk-dugumler cocuk-dugumler))
(setf butun
;; south
;;apply problem dependent operator 1
-durumlar (kaydir-asagi durum))
(setf cocuk
-dugumler (list (list
(setf cocuk-durumlar 'south
cocuk (+ (g-guncel dugum)
-durumlar))
(FIYAT (durum dugum) cocuk
dugum)))
-cocuk-dugumler
(setf butun-cocuk-dugumler cocuk-dugumler))
(append butun
;; east
;;apply problem dependent operator 1
-durumlar (kaydir-saga durum))
(setf cocuk
-dugumler (list (list
(setf cocuk-durumlar 'east
cocuk (+ (g-guncel dugum)
-durumlar))
(FIYAT (durum dugum) cocuk
dugum)))
-cocuk-dugumler (append butun-cocuk-dugumler cocuk-dugumler))
(setf butun
;; west
;;apply problem dependent operator 1
-durumlar (kaydir-sola durum))
(setf cocuk
-dugumler (list (list
(setf cocuk-durumlar 'west
cocuk (+ (g-guncel dugum)
-durumlar))
(FIYAT (durum dugum) cocuk
dugum)))
-cocuk-dugumler
(setf butun-cocuk-dugumler cocuk-dugumler))
(append butun
-sayisi
(setq kaydir+ kaydir-sayisi (length butun-cocuk-dugumler)))
(
;;and that's it. cocuk-dugumler is returned by the function
butun-cocuk-dugumler))
;;
;; tests
;;
'((1 NIL 3 1) (2 3 4 1) (5 5 4 1)(1 1 1 1)(0 1)))
(setq s0 (setq s1 '((1 3 4 1) (2 3 NIL 1) (5 5 4 1)(1 1 1 1)(1 2)))
(test "uniform cost search"
(not (eql (fiyati-sabit-arama s0 s1 #'cocuklari-getiren-islem) 'fail)) t)
print "OK. Uniform Cost Tests Passed") (
"ortak.lisp")
(load
(Defun Durum (dugum) (first dugum))
(Defun Kaydir (dugum) (second dugum))-guncel (dugum) (third dugum))
(Defun G;; tguncel 'tahmin guncel' den
;; geliyor.
-guncel (dugum) (fourth dugum))
(Defun t
(Defun Ust (dugum) (fifth dugum))
1)
(defun FIYAT (ust cocuk)
;;
;; sinifta tanimlanan tahmin islevi (function). baslangic
;; tahtasindaki her tas icin, ayni tasin sonuc tahtasindaki
;; pozisyonuna olan uzakliklari toplayan bir islev.
;;
-hesapla (su-anki-durum sonuc-durumu)
(defun tguncel0)(j 0)(toplam 0)(su-anki nil)(uzaklik 0))
(let ((i
(loop0)
(setq i
(loop-anki (nth i (nth j su-anki-durum)))
(setf su
-anki (first sonuc-durumu))
(cond ((member su
(setf
uzaklik+ (abs (- 0 j))
(abs (- i (position su-anki
(-durumu)))))))
(first sonuc
-anki (second sonuc-durumu))
((member su
(setf
uzaklik+ (abs (- 1 j))
(abs (- i (position su-anki
(-durumu)))))))
(second sonuc
-anki (third sonuc-durumu))
((member su
(setf
uzaklik+ (abs (- 2 j))
(abs (- i (position su-anki
(-durumu)))))))
(third sonuc
-anki (fourth sonuc-durumu))
((member su
(setf
uzaklik+ (abs (- 3 j))
(abs (- i (position su-anki
(-durumu)))))))
(fourth sonuc
)
+ toplam uzaklik))
(setf toplam (
;; increment
(setq i (incf i)) if (eql i 4) (return)))
(
(setq j (incf j))if (eql j 4) (return))
(
) toplam)
)
;; bu algoritma, fiyati-sabit-arama islevi temel alinarak yazilmistir.
;; yani, algoritma asagi yukari aynidir. Tek fark, FIYAT islevinin
;; hesaplanmasi.
-yildiz-arama (s0 sg sons)
(defun alist (list s0 nil 0 0 nil) ) )
(let ( ( acik (;;g-guncel set to 0
( tamamlanan nil )
( n nil )
( kizlar nil )) -count 0)
(setq kaydir
(loopif (null acik) (return 'hata))
(
(setf n (pop acik))
(push n tamamlanan)
if (equal (durum n) sg)
(
(let () print "Great. I found a solution. Here it is:")
(-raporu-ver acik tamamlanan s0)
(sonucreturn (sonuc-izini-bul n))))
(
-getiren-islem n))
(setf kizlar (cocuklari
-dugum-yarattik)
(kac
(setf kizlar
(DIFF kizlar tamamlanan))
(setf acik (UPDATE kizlar acik))
(setf acik #'(lambda(dugum1 dugum2)
(sort acik < (+ (g-guncel dugum1) (t-guncel dugum1))
(+ (g-guncel dugum2) (t-guncel dugum2))
(
))))
)
)
)
(defun UPDATE (kizlar acik)
-eski-d nil) )
(let ( ( m nil ) (bulunan
(loop
if (null kizlar) (return acik))
(
(setf m (pop kizlar))
-eski-d (MEMBER-DURUM (durum m) acik))
(setf bulunan
if bulunan-eski-d
(-d (first bulunan-eski-d)))
(let ((eski
if (< (g-guncel m) (g-guncel eski-d))
(-eski-d) m) ))
(setf (first bulunan
(push m acik)
)
)
)
)
-DURUM (durum list-of-nodes)
(Defun MEMBERif (null list-of-nodes)
(
nil if (equal durum (first list-of-nodes))
(list-of-nodes
-DURUM durum (rest list-of-nodes)))))
(MEMBER
-getiren-islem (dugum)
(defun cocuklari-cocuklar nil)
(let ( (butun-dugumler nil)
(cocuk-dugumler nil)
(ogul
(durum (first dugum)) )
-dugumler (kaydir-yukari durum))
(setf ogul-dugumler (list (list
(setf cocuk-dugumler
ogul'yukari
(+ (g-guncel dugum)
-dugumler))
(FIYAT (durum dugum) ogul-hesapla (durum dugum) sg )
(tguncel
dugum)))
-cocuklar (append butun-cocuklar cocuk-dugumler))
(setf butun
-dugumler (kaydir-asagi durum))
(setf ogul
-dugumler (list (list
(setf cocuk-dugumler
ogul'asagi
(+ (g-guncel dugum)
-dugumler))
(FIYAT (durum dugum) ogul-hesapla (durum dugum) sg)
(tguncel
dugum)))
-cocuklar (append butun-cocuklar cocuk-dugumler))
(setf butun
-dugumler (kaydir-saga durum))
(setf ogul
-dugumler (list (list
(setf cocuk-dugumler
ogul'saga
(+ (g-guncel dugum)
-dugumler))
(FIYAT (durum dugum) ogul-hesapla (durum dugum) sg)
(tguncel
dugum)))
-cocuklar (append butun-cocuklar cocuk-dugumler))
(setf butun
-dugumler (kaydir-sola durum))
(setf ogul
-dugumler (list (list
(setf cocuk-dugumler
ogul'sola
(+ (g-guncel dugum)
-dugumler))
(FIYAT (durum dugum) ogul-hesapla (durum dugum) sg)
(tguncel
dugum)))
-cocuklar (append butun-cocuklar cocuk-dugumler))
(setf butun
-count (+ kaydir-count (length butun-cocuklar)))
(setq kaydir
-cocuklar))
butun
'((1 2 3 4) (5 6 0 8) (9 10 7 11) (13 14 15 12) (1 2)))
(setq s0 (setq sg '((1 2 3 4) (5 6 7 8) (9 10 11 12) (13 15 14 0) (3 3)))
(test "calc hhat test A*" (tguncel-hesapla s0 sg) 8)
(setq s0 '((1 2 3 4) (5 6 0 8) (9 10 7 11) (13 14 15 12) (1 2)))
(setq sg '((1 2 3 4) (5 6 7 8) (9 10 11 12) (13 14 15 0) (3 3)))
(test "A* Search test"
(not (eql (a-yildiz-arama s0 sg nil) 'hata)) t )
(print "OK. A* Tests Passed")
Yapay Zeka ve Müsabaka
Bilgisayarlar bir problemi yapay zeka kullanarak çözerken, kullandıkları teknikler; Karar ağacı, akıllı tahmin yeteneği ve o ana kadar geçilen yolu hatırlamaktır.
Karar ağacı kullanırken, seçeceğimiz yolun doğru yol mu olup olmadığı tahmin etmek için değerlendirme fonksiyonuna sorarız. Bu fonksiyon gerçek bir tahmin mantığına ne kadar yakın ise, (yani uzman bir insana) arama da o kadar başarılı olur.
Bu örnekten yola çıkarsak, karşılıklı müsabakalar da bir arama problemi gibi görülebilir. Bir başlangıç noktası vardır, belli seçenekler vardır, bu seçenekleri takip etmek için karar ağacı tekniği uygulanabilir.
Tek bir değişiklik ile: Artık kararların hepsi bize ait değil.
Altüst (Minimax) Algoritması
Mesela müsabaka, bir dama oyunu olsun. Oyun sırasında sıra bir bilgisayara, bir karşı tarafa geçer. Bu yüzden iyi bir yapay zeka algoritması, hem kendi hareketlerinin arasında “değerlendirme fonksiyonunun” en iyi bulduğunu seçmeli, hem de, aynı zamanda rakibi için en kötü olacak yolu takip etmelidir.
Bu iki seçeneğe göre karar arama yapan algoritmaya altüst algoritması diyoruz. Çünkü rakip için an alt değer ile, bilgisayar için en üst değeri aynı anda arıyoruz.
Normal tek kişili arama algoritmalarında sadece “bir” ileriye bakarak değerlendirme yapmış, ve en fazla olan seçeneği takip etmiştik. Altüst için arama yaparken derinliğine ineceğiz, ve bu derinliği hafızamızın elverdiği kadar yapabileceğiz. Çünkü, hamleye karşı hamle, ona karşı hamle derken en iyi seçeneği bulabilmek için bazen oldukça derinlere inmek gerekebilir. 10 seviye altta çok iyi gözüken bir birleşim olabilir, ama belki de 11. seviyede maçı kaybediyoruz! Tabii dallanma seviyesi fazla olan oyunlarda (mesela satranç) bu şekilde derinlik birçok bilgisayarı donanım olarak zorlayacaktır. Bu yüzden Kasparov gibi bir ustayla ancak IBM’in satranç için özel yapılmış makinesi rekabet edebiliyor.
Oyun: İtalyan Daması
Altüst algoritmasını dallanma faktörünün fazla olmadığı bir oyun üzerinde göreceğiz. Bu oyunun ismi italyan daması. Bildiğimiz dama oyununa çok benziyor, sadece taşlar düz olarak ileri, geri, sağa, sola gitmek yerine çapraz hareket ediyorlar. Aynen damada olduğu gibi, en sona ulaşan taş kral oluyor ve uzun sıçramalar yapabiliyor.
Ekte verilen LISP kodu üzerinde göreceğimiz gibi, programı temel hareketler, değerlendirme fonksiyonu, algoritma ve ekrandan giriş yaparak oynanabilen kısımlara ayırdık.
Altüst algoritması, özyineli olarak çalışan bir algoritmadır. Altüst, önce derinliğine bir sekilde müsaade edildiği kadar (programcı tarafından) derinliğe iner, ve vardığı en uç noktalardaki tahtaları değerlendirir. Geri dönerken, bu değerlerden bazen “en az” olanı bazen “en fazla” olanı seçer. En az/en fazla kıstası her seviyede bir değişir. Rakip hareketlerini gösteren seviyede bulunuyorsak, enalt, kendi seviyemizde bulunuyorsak enüst seçimi yaparız.
Üzerinde karşılaştırma yaptığımız sayı, değerlendirme fonksiyonunun tahta hakkında biçtiği değerden başkası değildir. Bu tür değerlendirme fonksiyonlarını A* algoritması altında görmüştük.
Tahta değerlerinin arasındaki seçimi özyineden geriye “dönerken”
yaptığımıza özellikle dikkat edin. Yani, 10. seviyeye indiysek ve bütün
önce-derinliğine olarak bir dalı açmış isek, ancak ondan sonra değerleri
birbirleri ile karşılaştırarak ve seçerek döndürmeye başlıyoruz.
Değerlendirme işleminin kendisi, derinliğin en sonundaki tahtalar
üzerinde yapılıyor. “Ara tahtaların” üzerinde değerlendirme yapmıyoruz.
(Bkz. tahta-degerlendir
fonksiyonu).
Örnekteki resimde 2. seviyeye 99 ve 100’ün dönmüş olduğunu görüyoruz. 1. seviye de sırasıyla önce 99, sonra 100’ün dönmesi gerekir, ve bunlardan 100 değeri 99’un üzerine çıkacaktır. Çünkü 1. seviye ‘üst’ seviyesidir. Alt seviyesi olsa idi, 99 seçilecekti.
Ayrıca, seviyeye göre bazen alt, bazen üst değerler aradığımız için, hangi seviyede olduğumuza bağlı olarak <> operatörlerini kullanmak yerine, hep aynı operatörü (>) kullansak, ve karşılaştırma yaptığımız değeri sonraki seviyeye aktarmadan önce eksi (-) ile çarpsak kod daha temiz olacak. Bunu ufak bir algoritma numarası olarak görebilirsiniz. Değeri eksiye dönen bir değerin üzerinde uygulanan büyüktür/küçüktür karşılaştırmalarının sonucu otomatikman tersine döner (basit aritmetik). Eksiyi eksi ile çarpınca sayı tekrar artıya döndüğü için özyineli olarak bu çarpımı tekrar tekrar yapmamız mümkün olabiliyor. Ne güzel. Böylece iki tane if (ya da LISP cond) ifadesi yazmaktan kurtulmuş olduk. Kod daha temiz hale geldi. Bahsedilen çağırım şekli dama-alg.lisp dosyasındaki aşağıdaki satırda.
-hareket (tas-oynat
(setf dene (eniyi-listesi) konumn)
(first hareket- derinlik 1)
(* onun-eniyi -1) ;; eksi carpimina dikkat
(* enyuksek-deger -1))) ;; ;; eksi carpimina dikkat (
Bir başka ilginç bir nokta da şudur: Rakibimizin tahtalarını ve kendi
tahtalarına değer biçerken hep aynı fonksiyonu kullanıyoruz. (Kod
üzerinde tahta-degeri(tahta)
LISP fonksiyonu). Bunun
demektir ki Kendi oyun bilgimize dayanarak rakibimizin ne yapacağını
tahmin etmeye uğraşıyoruz. Yani zihnen, sanal bir alemde “rakibimizin
yerine” hamle yapıyoruz ve bu sanal hamleye kendimize göre bir cevap
veriyoruz. Hakikaten de satranç, dama, kağıt oynarken yaptığımız da bu
değil midir?
Eniyileştirme
Gördüğümüz gibi, altüst’ün temeli oldukça basit. Bundan sonrası, altüst’ü hız ve hafıza bakımından eniyileştirme için yapılmıştır. Alfa-beta budaması denen altüst uzantısı bu çerçevede düşünülmüştür.
Dama tahtaları arasında alt/üst irdelemesi yaparken, şunu düşünebiliriz: Ağacın herhangi yerindeki oyuncunun varabileceği bir yer olarak bir n adlı bir düğüm olduğunu düşünün; Eğer oyuncunun n’in bir üstü ya da daha tepesinde (dallanma olarak) m adında daha iyi seçeneği var ise, n düğümü oyun sırasında asla erişilmeyecektir. Bu yüzden n hakkında yeteri kadar bilgiye sahip olduğumuzda (cocuklarından birkaçına bakarak), bu düğümü tümden budayabiliriz.
Daha detaylı (ve matematiksel) bir örnekte göstermemiz gerekirse:
-degeri(en tepe) =
altust3, 12, 8), alt(2, x, y), alt(14, 5, 2) )
üst ( alt(-degeri(en tepe) =
altust3, alt(2, x, y), 2)
üst ( -degeri(en tepe) =
altust3, z, 2)
üst ( -degeri(en tepe) = 3 altust
Alt (2, x, y) fonksiyonunun değeri Z’ye eşitlendi (ve atıldı), x ve y’nin ne olduğuna bile bakılmadan. Çünkü alt(2, x, y) dediğimiz zaman aynı anda şunu söylemiş oluyoruz: “alt (2, x, y) en fazla 2 olabilir”. Değil mi? Çünkü alt fonksiyonunun gereği olarak zaten en aşağı olan değeri seçeceğiz. X ya da y daha az olsa, onları seçerdik, daha fazla olsalar 2’yi seçeceğiz. Fakat, elimizde KESİN bir 2 değeri “zaten” var ise, alt(2, x, y)’yi bir tarafa atabiliriz, çünkü nasıl olsa alt(2, x, y)’nin sonucu 2’den daha iyi olamazdı. DAHA İYİ’den kastımız üst fonksiyonu bakımından daha iyi demektir, çünkü alt() fonksiyonlarının sonucu üst() fonksiyonuna gidiyor, biliyorsunuz.
Sonuçta, soyut olarak düşünerek alt(2, x, y)’nin üzerinde 2 yönlü bir traşlama yapıyoruz denebilir. X ve Y’nin 2’den fazla olmasını fonksiyonun kendisi traşlıyor. Daha az olabilme ihtimallerini’de, elimizde zaten olan 2 değeri traşlıyor, çünkü bu iki değerinin ne yaparsak yapalım üstüne çıkamayacağız. Alt değerleri, üstte toplandığı için…
Alfa beta budaması ismini ağaçta gezinirken o ana kadar en üst bulunmuş olan değeri alfa değişkeninde, ve en alt bulunmuş değeri beta değişkeninde sürekli olarak yanında gezdirmesinden alır. En alt ve en üst değerler aranırken sürekli alfa ve beta’ya karşılaştırma yapılır. Alfa/beta penceresinin içine düşmeyen seçenekler ve onların alt-ağaçları tamamen budanır. Bu şekilde yer ve zamandan oldukça istifade etmemiz mümkündür.
"dama-temel.lisp")
(load
;;
;; Cok basit bir degerlendirme fonksiyonu. Degerlendirme islemleri
;; tahtaya bakarak bu tahtanin bilgisayar icin ne kadar iyi durdugunu
;; (oldugunu) bir rakam ile rapor ederler. *enust-renk* bilgisayarin
;; hangi oyuncuyu oynadigini gosterir. Burada kullanilan degerlendirme
;; cok basit, "daha zoru" degerlendirme icin ozel olan dosyada olacak.
;; Bu islevin raporladigi rakam, zaten tahtanin en sonunda tutulmakta.
-degeri(tahta)
(defun tahta*enust-renk* *beyaz*)
(cond ((equal
(caadr tahta))
(t (cadadr tahta))
))
;;
;; disardan cagirilan islev
-arama(dugum)
(defun altust-eniyi -999999)
(setf benim-eniyi +999999)
(setf onun-hareket (copy-tree dugum) 10 benim-eniyi onun-eniyi)
(eniyi
)
;; Simdi, altust (minimax) algoritmasinin alfa-beta seklini gosteriyoruz.
-hareket(konumn derinlik benim-eniyi onun-eniyi)
(defun eniyi
;; Dikkat ederseniz normal altust algoritmasina iki yeni
;; bildirgec ekledik. Baslarken Benim-Eniyi -sonsuz'a (eksi sonsuz)
;; esitlenmeli. Onun-eniyi ise +sonsuz'a esitlenmeli.
-listesi nil)(enyuksek-deger nil)
(let ((hareket-deger nil))
(eniyim nil)(dene nil)(denenen
;; Bu kontrol, ozyineli cagirimi karar agacin sonuna geldigimizde
;; bitirebilmek icindir. Iki elemanli bir liste geriye
;; getiriyoruz.
if (eql derinlik 0)
(return-from eniyi-hareket (list (tahta-degeri konumn) nil)))
(
;; Oyun kurallarina gore uygun olan, tahta'nin o anki konumuna
;; gore olan butun muhtemel hareketleri buluyoruz.
-listesi (hareket-listesi-hesapla *enust-renk* konumn))
(setq hareket
-deger benim-eniyi)
(setq enyuksek
(setq eniyim nil)
;; Artik hareket-listesi'ni taramaya haziriz. En iyi
;; hareketi bu listeden sececegiz. Enyuksek-deger ve eniyim
;; degerlerini nasil yukledigimize dikkat edin.
-listesi nil))
(do () ((equal hareket
;; Burasi ana ozyineli cagirimin yapildigi yer. Bu cagiri ile
;; siradaki hareketin arama alanini 'aciyoruz'. Iki yeni
;; bildirgeci gectigimize dikkat edin.
-hareket (tas-oynat (first hareket-listesi) konumn)
(setf dene (eniyi- derinlik 1)
(* onun-eniyi -1)
(* enyuksek-deger -1)))
(
;; eniyi-hareket iki deger geri getirir, unutmayin..
-deger (first dene))
(setq denenen
;; Simdi, elimizdeki hareketin otekilere daha iyi olup olmadigina
;; karar verelim. Elimizdeki hareketi 'su ana kadar en iyi' olarak
;; secip secmeyecegimiz buna bagli.
if (> denenen-deger enyuksek-deger)
(
(progn-deger denenen-deger)
(setq enyuksek-listesi))
(setq eniyim (first hareket
))
;; Iste 'kesit' islemi alfa-beta algoritmasi icin burada
;; yapilir. Eger iyi bir hareket bulamadiysak, arayisi burada
;; durduruyoruz. Return fonksiyonu, donguyu yarida kesiyor
;; ve bir onceki ozyine seviyesine donuyor.
if (> enyuksek-deger onun-eniyi)
(return-from eniyi-hareket (list enyuksek-deger eniyim)))
(
;; Listede taramaya devam ediyoruz, bakalim elimizdekinden daha
;; iyi bir hareket bulabilecekmiyiz
-listesi (cdr hareket-listesi))
(setq hareket
)
;; Butun hareket-liste'sini aradiktan sonra, en iyi
;; hareketi bulmus bulunuyoruz. Geriye cevap olarak
;; bu hareketi bildirecegiz.
return-from eniyi-hareket (list enyuksek-deger eniyim))
(
;; let sonu
)
;; defun sonu
)
;;
;; testler
-basla *beyaz*)
(oyuna"degerlendir testi" (tahta-degeri *tahta*) 12)
(test
-basla *beyaz*)
(oyuna"altust basit test" (altust-arama *tahta*) '(12 ((1 5) (0 4))))
(test
(setq *enust-renk* "b")
(setf hic-siyah-kalmadi
'(((nil ("b" nil) nil ("b" nil) nil ("b" nil) nil ("b" nil) )
(("b" nil) nil ("b" nil) nil ("b" nil) nil ("b" nil) nil)
"b" nil) nil ("b" nil) nil ("b" nil) nil ("b" nil) )
(nil (
(nil nil nil nil nil nil nil nil)(nil nil nil nil nil nil nil nil)
(nil nil nil nil nil nil nil nil)(nil nil nil nil nil nil nil nil )12 0)))
(nil nil nil nil nil nil nil nil)) ("basit degerlendir 1" (tahta-degeri hic-siyah-kalmadi) 12)
(test
*enust-renk* "s")
(setq -siyah-kalmadi
(setf hic'(((nil ("b" nil) nil ("b" nil) nil ("b" nil) nil ("b" nil) )
(("b" nil) nil ("b" nil) nil ("b" nil) nil ("b" nil) nil)
"b" nil) nil ("b" nil) nil ("b" nil) nil ("b" nil) )
(nil (
(nil nil nil nil nil nil nil nil)(nil nil nil nil nil nil nil nil)
(nil nil nil nil nil nil nil nil)(nil nil nil nil nil nil nil nil )12 0)))
(nil nil nil nil nil nil nil nil)) ("basit degerlendir 2" (tahta-degeri hic-siyah-kalmadi) 0)
(test
-basla *beyaz*)
(oyuna-kopyasi (copy-tree *tahta*))
(setq tahta-arama *tahta*)
(altust"tahta degismemesi gerekir testi" (equal tahta-kopyasi *tahta*) t)
(test
print "Tamam. Algoritma Birim Testleri Gecti") (
"dama-alg.lisp")
(load
;; Bu islev, atak oyun halinde mi, yoksa defans oyun halinde mi
;; oldugumuzu hesaplar. Eger defans agirlikli oynuyorsak, ki program
;; bunu oyunun basinda yapmak uzere yazildi, her tahtanin degeri
;; hesaplanirken agirliklar defansif olculere gore secilir. Atak
;; oyununda bu agirliklar degisiyor. Defans/Atak karari su ana kadar
;; kac hamle yapildigina gore veriliyor; Belli bir tetik degerinden
;; sonra, (7 hamle) bilgisayar atak oynamaya basliyor.
-oyun? ()
(defun atak> bilgisayar-hamle-sayisi 7) t)
(cond ((
(t nil)))
;; Alttaki degerlendirme islevini goruyoruz. Bu islev oyunun
;; akillica secim yapmasina yardim edecek.
-degeri(tahta)
(defun tahta
(let (-sayac 0) (x-sayac 0)
(y;; sayac degiskenler
-tas-sayim (caadr tahta))(rakibin-tas-sayisi (cadadr tahta))
(benim-kral-sayim 0)(rakibin-kral-sayisi 0)
(benim-hamlelerim 0)(rakibin-mevcut-hamleleri 0)
(mevcut;; agirliklar
-agirligi nil)(mevcut-hamle-agirligi nil)
(kralin-kalan-tas-agirligim nil)(rakibin-kalan-tas-agirligi nil)
(benim;; sonuc
-toplami 0)
(degerlendirme
)
;; Atak/defans halimize gore agirlik degerlerini
;; degistir
-oyun?) nil)
(cond ((equal (atak
(progn-agirligi 50)
(setq kralin-hamle-agirligi 60)
(setq mevcut-kalan-tas-agirligim 70)
(setq benim-kalan-tas-agirligi 30)
(setq rakibin
))
(t
(progn-agirligi 100)
(setq kralin-hamle-agirligi 60)
(setq mevcut-kalan-tas-agirligim 20)
(setq benim-kalan-tas-agirligi 70)
(setq rakibin
)
))
;; butun tahtayi tararken..
-sayac 8)
(dotimes (x-sayac 8)
(dotimes (y-degeri (tas-degeri-ver (list x-sayac y-sayac) tahta))
(setq konumif (not (equal konum-degeri nil))
(
(progn;; tas degeri ve kral gosterge degerine eris
-degeri))
(setq renk (car konum-mi (cadr konum-degeri))
(setq kral
;; saymaya basla
;; krallari say
if (and (equal *enust-renk* renk)
(-mi t))
(equal kral-kral-sayim (+ 1 benim-kral-sayim)))
(setq benim
if (and (equal *enalt-renk* renk)
(-mi t))
(equal kral-kral-sayisi (+ rakibin-kral-sayisi 1)))
(setq rakibin
;; mevcut hareketleri say (hareket sahamiz ne kadar genis?)
-hamlelerim
(setq mevcut-listesi-hesapla *enust-renk* tahta)))
(length (hareket-mevcut-hamleleri
(setq rakibin-listesi-hesapla *enalt-renk* tahta)))
(length (hareket
))
))
;; hepsini topla
-toplami
(setf degerlendirme+ degerlendirme-toplami
(* benim-tas-sayim benim-kalan-tas-agirligim)))
(-toplami
(setq degerlendirme+ degerlendirme-toplami
(* rakibin-tas-sayisi rakibin-kalan-tas-agirligi)))
(-toplami
(setq degerlendirme+ degerlendirme-toplami
(* benim-kral-sayim kralin-agirligi)))
(-toplami
(setq degerlendirme+ degerlendirme-toplami
(* mevcut-hamlelerim mevcut-hamle-agirligi)))
(
;; sonuc degeri geri bildir
-toplami)
degerlendirme
)
;;
;; testler
-hamle-sayisi 0)
(setq bilgisayar"atak mi defans mi? 1" (atak-oyun?) nil)
(test
-hamle-sayisi 10)
(setq bilgisayar"atak mi defans mi? 2" (atak-oyun?) t)
(test
-basla *beyaz*)
(oyuna"atak mi defans mi? 3" (atak-oyun?) nil)
(test
-basla *beyaz*)
(oyuna"tahta degerlendir" (tahta-degeri *tahta*) 1620)
(test
print "Tamam. Degerlendirme Birim Testleri Gecti") (
"dama-deger.lisp")
(load
-basla *beyaz*)
(oyuna
print "----------------------------------------------------")
(print "Hamleleri mesela siyah icin '((0 2)(1 3)) seklinde girmek gerekli")
(print "Bu, x=0 y=2'deki tasi x=1, y=3 pozisyonuna getirecektir")
(print "----------------------------------------------------")
(
(loop*tahta*)
(goster print "Hamlenizi giriniz")
(-hamlesi (eval (read)))
(setq insan-kurallara-uygunmu insan-hamlesi *tahta* "b") t)
(cond ((equal (hamle
(progn-oynat insan-hamlesi *tahta*)
(tasprint "su hareketi yaptiniz")
(print insan-hamlesi)
(*tahta*)
(goster -hamlesi (cadr (altust-arama *tahta*)))
(setq bilgisayarprint "bilgisayarin hareketi")
(print bilgisayar-hamlesi)
(-oynat bilgisayar-hamlesi *tahta*)
(tas-hamle-sayisi (+ bilgisayar-hamle-sayisi 1))
(setf bilgisayar
))print "HATALI HAREKET")))
(t ( )
;; Oyun tahtasi liste icinde liste olarak temsil edildi. Her tahta
;; konumu, eger uzerinde bir tas var ise, bir liste nesnesi
;; tasir. Eger bu tas normal bir tas ise, bu liste ("b" nil) gibi
;; olur. Eger bu tas kral tasi ise, ("b" T) olarak temsil
;; edilecektir. Yani, ikinci T ya da NIL degeri krallik
;; gostergesidir. Eger konum uzerinde hic tas yok ise, liste nesnesi
;; yerine NIL bulacaksiniz, dikkat edin (nil nil) degil. Listenin en
;; sonundaki iki rakam, tahta uzerinde o anda her renkten kac tas
;; kaldigini gosterir. Birinci rakam beyaz, ikincisi siyah icin. Bunu
;; yapmamizin sebebi algoritmayi hizlandirmak icin, boylece ikidebir
;; tahtayi bastan sona taramak gerekmiyor.
*beyaz* "b")
(setq *siyah* "s")
(setq *enust-renk* nil)
(setq *enalt-renk* nil)
(setq *tahta* nil)
(setq
-hamle-sayisi 0)
(setq bilgisayar
;;
;; test isleten islev
(defun test (isim deyim sonuc)
(cond
((equal deyim sonuc) t)print isim) (error "HATA! Birim test bir yanlis buldu! "))
(t (
))
;;
;; Tahta silbastan baslayinca, enust-renk bilgisayara aittir.
-basla (renk)
(defun oyuna-hamle-sayisi 0)
(setq bilgisayar*tahta* (copy-tree (tahtayi-hazirla)))
(setq
(cond*beyaz*)
((equal renk *enust-renk* "b")
(progn (setq *enalt-renk* "s")))
(setq *enust-renk* "s")
(t (progn (setq *enalt-renk* "b")
(setq
)
)
)
)
;;
;; tahtayi sifirla
-hazirla ()
(defun tahtayi'(((nil ("b" nil) nil ("b" nil) nil ("b" nil) nil ("b" nil) )
(("b" nil) nil ("b" nil) nil ("b" nil) nil ("b" nil) nil)
"b" nil) nil ("b" nil) nil ("b" nil) nil ("b" nil) )
(nil (
(nil nil nil nil nil nil nil nil)
(nil nil nil nil nil nil nil nil)"s" nil) nil ("s" nil) nil ("s" nil) nil ("s" nil) nil)
(("s" nil) nil ("s" nil) nil ("s" nil) nil ("s" nil) )
(nil ("s" nil) nil ("s" nil) nil ("s" nil) nil ("s" nil) nil)
((12 12))
) (
)
;;
;; tahtanin o anki durumunu ekrana metin olarak bas (hata bulmak
;; icin cok yararli oldu)
(defun goster (tahta)
(terpri)-line "+=0===1===2===3===4===5===6===7-+")
(write-sayici 8))
(let ((y-ozyine 8)
(dotimes (y- y-sayici 1))
(princ (-sayici 7))
(let ((x- 7 (- y-sayici 1)) (car tahta)))
(dolist (kon (nth (" ")
(princ
(cond" "))
((equal kon nil) (princ and (equal (car kon) "b") (null (cadr kon))) (princ "b"))
((and (equal (car kon) "b") (cadr kon)) (princ "B"))
((and (equal (car kon) "s") (null (cadr kon))) (princ "s"))
((and (equal (car kon) "s") (cadr kon)) (princ "S"))
((
)" ")
(princ if (null (equal x-sayici 0)) (princ "|"))
(-sayici (- x-sayici 1))
(setq x
)
)-line "|")
(writeif (null (equal y-sayici 1))
(-line "|===============================|"))
(write-sayici (- y-sayici 1))
(setq y
)
)-line "+=0===1===2===3===4===5===6===7=+")
(write
nil
)
;;
;; her hamle su sekilde temsil edilir, mesela '((0 2)(1 2))
;; Yani, hamle X=1, Y=2 konumundan X=1, Y=2 konumuna yapilacak.
-oynat (hamle tahta)
(defun tas
-tas1 (tas-degeri-ver (car hamle) tahta))
(setq gecici-tas2 (tas-degeri-ver (cadr hamle) tahta))
(setq gecici
;; hamle
(setq tahta -degeri-degis (cadr hamle)
(tas-cikart (car hamle) tahta) gecici-tas1))
(tas-konum
(setq atlanan-gidilen-konumlar (car hamle) (cadr hamle)))
(atlayarak
;; eger gerekiyorsa krala cevir
(condand (equal (car gecici-tas1) "s") (equal 7 (cadadr hamle)))
((-tas1) t))
(setf (cadr geciciand (equal (car gecici-tas1) "b") (equal 0 (cadadr hamle)))
((-tas1) t))
(setf (cadr gecici
)
(cond-konum ;; hareket atlama ise
(atlanan
(progn if (equal (car (tas-degeri-ver atlanan-konum tahta)) "b")
(- (caadr tahta) 1))
(setf (caadr tahta) (- (cadadr tahta) 1)))
(setf (cadadr tahta) (-cikart atlanan-konum tahta))
(setq tahta (tas
(cond;; birkac atlama var ise, ozyineli olarak cagir
((caddr hamle)
(progn-oynat (cdr hamle) tahta)
(tas
)
)
(t
tahta ))
)
);; atlama degil
(t
tahta
)
)
)
;;
;; tas degerini geri getir
-degeri-ver (kon tahta)
(defun tas- 7 (cadr kon)) (car tahta)))
(nth (car kon) (nth (
)
;;
;; tasin degerini tahtaya koy
-degeri-degis (kon tahta eleman)
(defun tas- 7 (cadr kon)) (car tahta))) eleman)
(setf (nth (car kon) (nth (
tahta
)
;;
;; tasi tahtadan al
-cikart (kon tahta)
(defun tas- 7 (cadr kon)) (car tahta))) nil)
(setf (nth (car kon) (nth (
tahta
)
;;
;;
-gidilen-konumlar (kon_a kon_b)
(defun atlayarak
(setq x (car kon_a))
(setq y (cadr kon_a))
(condlist (+ x 1) (+ y 1))) nil)
((equal kon_b (list (+ x 1) (- y 1))) nil)
((equal kon_b (list (- x 1) (+ y 1))) nil)
((equal kon_b (list (- x 1) (- y 1))) nil)
((equal kon_b (;; ya da ortada kalan taslarin kordinatlarini getir
(t
(cond< x (car kon_b)) (setq gecici_x (+ 1 x)))
((- x 1)))
(t (setq gecici_x (
)
(cond< y (cadr kon_b)) (setq gecici_y (+ 1 y)))
((- y 1)))
(t (setq gecici_y (
)list gecici_x gecici_y)
(
)
)
)
-kurallara-uygunmu (hareket tahta renk)
(defun hamle;; hareket menzilin disinda ise, bu kural disi bir hareket
(cond
((null (menzildemi (cadr hareket)))
nil
);; gitmeye ugrastigimiz yerde zaten bir tas var ise,
;; bu da kural disi bir harekettir
-degeri-ver (cadr hareket) tahta)
((tas
nil
)
(t
(let (-degeri-ver (car hareket) tahta))
(eleman (tas
(baslax (caar hareket))
(baslay (cadar hareket))
(bitisx (caadr hareket))
(bitisy (cadadr hareket)))
(cond ;; eger hareket ziplama hareketi ise
2 (abs (- baslax bitisx)))
((equal
(condlist "s" nil))
((equal eleman (if (and (equal 2 (- bitisy baslay))
(-degeri-ver
(equal (car (tas-gidilen-konumlar
(atlayarak
(car hareket)"b"))
(cadr hareket)) tahta))
t
)
)list "b" nil))
((equal eleman (if (and (equal -2 (- bitisy baslay))
(-degeri-ver
(equal (car (tas-gidilen-konumlar
(atlayarak
(car hareket)"s"))
(cadr hareket)) tahta))
t
)
)
((equal (cadr eleman) t)if (and (equal 2 (abs (- bitisy baslay)))
(-degeri-ver
(equal (car (tas-gidilen-konumlar
(atlayarak
(car hareket)
(cadr hareket)) tahta))-degistir renk)))
(renk
t
)
)
)
);; ziplama degil ise
1 (abs (- baslax bitisx)))
((equal
(condlist "s" nil))
((equal eleman (if (equal 1 (- bitisy baslay))
(
t
)
)list "b" nil))
((equal eleman (if (equal -1 (- bitisy baslay))
(
t
)
)
((equal (cadr eleman) t)if (equal 1 (abs (- baslay bitisy))) t)
(
)
)
)
)
)
)
)
)
(defun menzildemi (kon)
(let ((x (car kon)) (y (cadr kon)))
(cond and (< x 8) (< y 8) (> x -1) (> y -1)) t)
((
(t nil)
)
)
)
-degistir (color)
(defun renk
(cond"b" color) "r")
((equal "b")
(t
)
)
;;
;; girilen renk ve tahtaya gore, oyuncunun yapabilecegi
;; butun hareketleri geri getir
-listesi-hesapla (renk tahta)
(defun hareket-konumlari (tas-yerlerini-ver renk tahta))
(setq tas-hareketler nil) (mumkun-atlamalar nil))
(let ((muhtemel-konumlari)
(dolist (kon tas-atlamalar
(setq mumkun-atlamalar
(append mumkun-hareketleri-ver kon tahta renk)))
(mecburiif (null mumkun-atlamalar)
(
(prognif (hamle-kurallara-uygunmu
(list kon (list (- (car kon) 1)
(- (cadr kon) 1))) tahta renk)
(-hareketler
(setq muhtemel
(append -hareketler
muhtemellist (list kon (list (- (car kon) 1)
(- (cadr kon) 1)))))))
(if (hamle-kurallara-uygunmu
(list kon (list (- (car kon) 1)
(+ (cadr kon) 1))) tahta renk)
(-hareketler
(setq muhtemel
(append -hareketler
muhtemellist (list kon (list (- (car kon) 1)
(+ (cadr kon) 1)))))))
(if (hamle-kurallara-uygunmu
(list kon (list (+ (car kon) 1)
(- (cadr kon) 1))) tahta renk)
(-hareketler
(setq muhtemel
(append -hareketler
muhtemellist (list kon (list (+ (car kon) 1)
(- (cadr kon) 1)))))))
(if (hamle-kurallara-uygunmu
(list kon (list (+ (car kon) 1)
(+ (cadr kon) 1))) tahta renk)
(-hareketler
(setq muhtemel
(append -hareketler
muhtemellist (list kon (list (+ (car kon) 1)
(+ (cadr kon) 1)))))))
(;; progn sonu
) ;; if sonu
)
)if mumkun-atlamalar mumkun-atlamalar muhtemel-hareketler)
(
)
)
-yerlerini-ver (renk tahta)
(defun tas
(setq konumlar nil)
if (equal renk (car (tas-degeri-ver '(0 0) tahta)))
( (setq konumlar (append konumlar '((0 0)))))
(if (equal renk (car (tas-degeri-ver '(0 1) tahta)))
(setq konumlar (append konumlar '((0 1)))))
(if (equal renk (car (tas-degeri-ver '(0 2) tahta)))
(setq konumlar (append konumlar '((0 2)))))
(if (equal renk (car (tas-degeri-ver '(0 3) tahta)))
(setq konumlar (append konumlar '((0 3)))))
(if (equal renk (car (tas-degeri-ver '(0 4) tahta)))
(setq konumlar (append konumlar '((0 4)))))
(if (equal renk (car (tas-degeri-ver '(0 5) tahta)))
(setq konumlar (append konumlar '((0 5)))))
(if (equal renk (car (tas-degeri-ver '(0 6) tahta)))
(setq konumlar (append konumlar '((0 6)))))
(if (equal renk (car (tas-degeri-ver '(0 7) tahta)))
(setq konumlar (append konumlar '((0 7)))))
(if (equal renk (car (tas-degeri-ver '(1 0) tahta)))
(setq konumlar (append konumlar '((1 0)))))
(if (equal renk (car (tas-degeri-ver '(1 1) tahta)))
(setq konumlar (append konumlar '((1 1)))))
(if (equal renk (car (tas-degeri-ver '(1 2) tahta)))
(setq konumlar (append konumlar '((1 2)))))
(if (equal renk (car (tas-degeri-ver '(1 3) tahta)))
(setq konumlar (append konumlar '((1 3)))))
(if (equal renk (car (tas-degeri-ver '(1 4) tahta)))
(setq konumlar (append konumlar '((1 4)))))
(if (equal renk (car (tas-degeri-ver '(1 5) tahta)))
(setq konumlar (append konumlar '((1 5)))))
(if (equal renk (car (tas-degeri-ver '(1 6) tahta)))
(setq konumlar (append konumlar '((1 6)))))
(if (equal renk (car (tas-degeri-ver '(1 7) tahta)))
(setq konumlar (append konumlar '((1 7)))))
(if (equal renk (car (tas-degeri-ver '(2 0) tahta)))
(setq konumlar (append konumlar '((2 0)))))
(if (equal renk (car (tas-degeri-ver '(2 1) tahta)))
(setq konumlar (append konumlar '((2 1)))))
(if (equal renk (car (tas-degeri-ver '(2 2) tahta)))
(setq konumlar (append konumlar '((2 2)))))
(if (equal renk (car (tas-degeri-ver '(2 3) tahta)))
(setq konumlar (append konumlar '((2 3)))))
(if (equal renk (car (tas-degeri-ver '(2 4) tahta)))
(setq konumlar (append konumlar '((2 4)))))
(if (equal renk (car (tas-degeri-ver '(2 5) tahta)))
(setq konumlar (append konumlar '((2 5)))))
(if (equal renk (car (tas-degeri-ver '(2 6) tahta)))
(setq konumlar (append konumlar '((2 6)))))
(if (equal renk (car (tas-degeri-ver '(2 7) tahta)))
(setq konumlar (append konumlar '((2 7)))))
(if (equal renk (car (tas-degeri-ver '(3 0) tahta)))
(setq konumlar (append konumlar '((3 0)))))
(if (equal renk (car (tas-degeri-ver '(3 1) tahta)))
(setq konumlar (append konumlar '((3 1)))))
(if (equal renk (car (tas-degeri-ver '(3 2) tahta)))
(setq konumlar (append konumlar '((3 2)))))
(if (equal renk (car (tas-degeri-ver '(3 3) tahta)))
(setq konumlar (append konumlar '((3 3)))))
(if (equal renk (car (tas-degeri-ver '(3 4) tahta)))
(setq konumlar (append konumlar '((3 4)))))
(if (equal renk (car (tas-degeri-ver '(3 5) tahta)))
(setq konumlar (append konumlar '((3 5)))))
(if (equal renk (car (tas-degeri-ver '(3 6) tahta)))
(setq konumlar (append konumlar '((3 6)))))
(if (equal renk (car (tas-degeri-ver '(3 7) tahta)))
(setq konumlar (append konumlar '((3 7)))))
(if (equal renk (car (tas-degeri-ver '(4 0) tahta)))
(setq konumlar (append konumlar '((4 0)))))
(if (equal renk (car (tas-degeri-ver '(4 1) tahta)))
(setq konumlar (append konumlar '((4 1)))))
(if (equal renk (car (tas-degeri-ver '(4 2) tahta)))
(setq konumlar (append konumlar '((4 2)))))
(if (equal renk (car (tas-degeri-ver '(4 3) tahta)))
(setq konumlar (append konumlar '((4 3)))))
(if (equal renk (car (tas-degeri-ver '(4 4) tahta)))
(setq konumlar (append konumlar '((4 4)))))
(if (equal renk (car (tas-degeri-ver '(4 5) tahta)))
(setq konumlar (append konumlar '((4 5)))))
(if (equal renk (car (tas-degeri-ver '(4 6) tahta)))
(setq konumlar (append konumlar '((4 6)))))
(if (equal renk (car (tas-degeri-ver '(4 7) tahta)))
(setq konumlar (append konumlar '((4 7)))))
(if (equal renk (car (tas-degeri-ver '(5 0) tahta)))
(setq konumlar (append konumlar '((5 0)))))
(if (equal renk (car (tas-degeri-ver '(5 1) tahta)))
(setq konumlar (append konumlar '((5 1)))))
(if (equal renk (car (tas-degeri-ver '(5 2) tahta)))
(setq konumlar (append konumlar '((5 2)))))
(if (equal renk (car (tas-degeri-ver '(5 3) tahta)))
(setq konumlar (append konumlar '((5 3)))))
(if (equal renk (car (tas-degeri-ver '(5 4) tahta)))
(setq konumlar (append konumlar '((5 4)))))
(if (equal renk (car (tas-degeri-ver '(5 5) tahta)))
(setq konumlar (append konumlar '((5 5)))))
(if (equal renk (car (tas-degeri-ver '(5 6) tahta)))
(setq konumlar (append konumlar '((5 6)))))
(if (equal renk (car (tas-degeri-ver '(5 7) tahta)))
(setq konumlar (append konumlar '((5 7)))))
(if (equal renk (car (tas-degeri-ver '(6 0) tahta)))
(setq konumlar (append konumlar '((6 0)))))
(if (equal renk (car (tas-degeri-ver '(6 1) tahta)))
(setq konumlar (append konumlar '((6 1)))))
(if (equal renk (car (tas-degeri-ver '(6 2) tahta)))
(setq konumlar (append konumlar '((6 2)))))
(if (equal renk (car (tas-degeri-ver '(6 3) tahta)))
(setq konumlar (append konumlar '((6 3)))))
(if (equal renk (car (tas-degeri-ver '(6 4) tahta)))
(setq konumlar (append konumlar '((6 4)))))
(if (equal renk (car (tas-degeri-ver '(6 5) tahta)))
(setq konumlar (append konumlar '((6 5)))))
(if (equal renk (car (tas-degeri-ver '(6 6) tahta)))
(setq konumlar (append konumlar '((6 6)))))
(if (equal renk (car (tas-degeri-ver '(6 7) tahta)))
(setq konumlar (append konumlar '((6 7)))))
(if (equal renk (car (tas-degeri-ver '(7 0) tahta)))
(setq konumlar (append konumlar '((7 0)))))
(if (equal renk (car (tas-degeri-ver '(7 1) tahta)))
(setq konumlar (append konumlar '((7 1)))))
(if (equal renk (car (tas-degeri-ver '(7 2) tahta)))
(setq konumlar (append konumlar '((7 2)))))
(if (equal renk (car (tas-degeri-ver '(7 3) tahta)))
(setq konumlar (append konumlar '((7 3)))))
(if (equal renk (car (tas-degeri-ver '(7 4) tahta)))
(setq konumlar (append konumlar '((7 4)))))
(if (equal renk (car (tas-degeri-ver '(7 5) tahta)))
(setq konumlar (append konumlar '((7 5)))))
(if (equal renk (car (tas-degeri-ver '(7 6) tahta)))
(setq konumlar (append konumlar '((7 6)))))
(if (equal renk (car (tas-degeri-ver '(7 7) tahta)))
(setq konumlar (append konumlar '((7 7)))))
konumlar
)
-hareketleri-ver (kon tahta renk)
(defun mecburi-hareketler nil) (eleman (tas-degeri-ver kon tahta)))
(let ((muhtemelif (cadr eleman)
(;;
;; KRALLAR
;;
(progn-hareketler
(setq muhtemel-bul
(atlamalari-tree tahta) kon (+ (car kon) 2)
(copy+ (cadr kon) 2) renk muhtemel-hareketler))
(-hareketler
(setq muhtemel-bul
(atlamalari-tree tahta) kon (+ (car kon) 2)
(copy- (cadr kon) 2) renk muhtemel-hareketler))
(-hareketler
(setq muhtemel-bul
(atlamalari-tree tahta) kon (- (car kon) 2)
(copy+ (cadr kon) 2) renk muhtemel-hareketler))
(-hareketler
(setq muhtemel-bul
(atlamalari-tree tahta) kon (- (car kon) 2)
(copy- (cadr kon) 2) renk muhtemel-hareketler))
(
);;
;; NORMAL
;;
(prognif (equal renk "b")
(
(progn;;
;; BEYAZ :: Bu demektir ki normal parcalar icin + kullan
;;
-hareketler
(setq muhtemel-bul
(atlamalari-tree tahta) kon (+ (car kon) 2)
(copy- (cadr kon) 2) renk muhtemel-hareketler))
(-hareketler
(setq muhtemel-bul
(atlamalari-tree tahta) kon (- (car kon) 2)
(copy- (cadr kon) 2) renk muhtemel-hareketler))
(
)
(progn;;
;; SIYAH :: Buna gore normal parcalar icin '-' kullan
;;
-hareketler
(setq muhtemel-bul
(atlamalari-tree tahta) kon (+ (car kon) 2)
(copy+ (cadr kon) 2) renk muhtemel-hareketler))
(-hareketler
(setq muhtemel-bul
(atlamalari-tree tahta) kon (- (car kon) 2)
(copy+ (cadr kon) 2) renk muhtemel-hareketler))
(
)
)
)
)-hareketler
muhtemel
)
)
;;
;;
-bul (gecici_tahta kon yenix yeniy renk m-hareketler)
(defun atlamalari-hareketler nil))
(let ((muhtemelif (hamle-kurallara-uygunmu
(list kon (list yenix yeniy)) gecici_tahta renk)
(
(progn
(setq gecici_tahta -oynat (list kon (list yenix yeniy)) gecici_tahta))
(tas
(setq gecici -hareketleri-ver
(mecburilist yenix yeniy) gecici_tahta renk))
(if gecici
(
(dolist (b gecici)list kon (list yenix yeniy)))
(setq a (if muhtemel-hareketler
(-hareketler
(setq muhtemel
(append -hareketler
muhtemellist (append a (cdr b)))))
(-hareketler
(setq muhtemellist (append muhtemel-hareketler a (cdr b))))
(
)
)-hareketler (list (list kon (list yenix yeniy))))
(setq muhtemel
)
))if muhtemel-hareketler
(-hareketler muhtemel-hareketler) m-hareketler)
(append m
)
)
;; Oyunun bitip bitmedigine karar veren islev budur. Cagirmak icin
;; bir renk ve tahtanin durumu bildirilir, eger renk icin hic bir
;; hareket kalmadi ise, bu oyuncu icin oyun bitmis demektir.
;; Bu oyuncunun belki taslarinin onu kapanmistir, ya da hic
;; tasi kalmamistir. Her iki halde de hareket-listesi-hesapla
;; hic hareket listesi geri getirmez.
-bitti-mi?(renk tahta)
(defun oyun
(cond-listesi-hesapla renk tahta) nil) t)
((equal (hareket
(t nil))
)
;; -------------------------------------------------------------
;;
;; testler
-basla *beyaz*)
(oyuna-oynat '((0 2)(1 2)) *tahta*))
(setf sonuc (tas(setf beklenen-sonuc
'(((nil ("b" nil) nil ("b" nil) nil ("b" nil) nil ("b" nil))
"b" nil) nil ("b" nil) nil ("b" nil) nil ("b" nil) nil)
(("b" nil) nil ("b" nil) nil ("b" nil) nil ("b" nil))
(nil (
(nil nil nil nil nil nil nil nil) (nil nil nil nil nil nil nil nil)"s" nil) ("s" nil) nil ("s" nil) nil ("s" nil) nil)
(nil ("s" nil) nil ("s" nil) nil ("s" nil))
(nil nil nil ("s" nil) nil ("s" nil) nil ("s" nil) nil ("s" nil) nil))
((12 11)) )
("tek hareket yap" (equal beklenen-sonuc sonuc) t)
(test
-basla *beyaz*)
(oyuna"yanlis hareket yap"
(test -kurallara-uygunmu '((0 2)(1 2)) *tahta* *beyaz*) nil)
(hamle
(oyuna-basla *beyaz*)
(test "dogru hamle yap"
(hamle-kurallara-uygunmu '((0 2)(1 3)) *tahta* 'USER::BLACK) T)
-basla *beyaz*)
(oyuna-hareket-listesi
(setf beklenen'(((1 5) (0 4)) ((1 5) (2 4)) ((3 5) (2 4))
((3 5) (4 4)) ((5 5) (4 4)) ((5 5) (6 4)) ((7 5) (6 4))))
-listesi-hesapla "b" *tahta*))
(setf sonuc (hareket"oyuna uygun hareket" (equal sonuc beklenen-hareket-listesi ) t)
(test
-basla *beyaz*)
(oyuna-sonuc (tas-oynat '((0 2)(2 7)) *tahta*))
(setf gecici(setf beklenen-tahta
'(((nil ("b" nil) ("s" T) ("b" nil) nil ("b" nil) nil ("b" nil))
"b" nil) nil ("b" nil) nil ("b" nil) nil ("b" nil) nil)
(("b" nil) nil ("b" nil) nil ("b" nil) nil ("b" nil))
(nil (
(nil nil nil nil nil nil nil nil)
(nil nil nil nil nil nil nil nil)"s" nil) nil ("s" nil) nil ("s" nil) nil)
(nil nil ("s" nil) nil ("s" nil) nil ("s" nil) nil ("s" nil))
(nil ("s" nil) nil ("s" nil) nil ("s" nil) nil ("s" nil) nil))
((12 11)))
("kral yap" (equal gecici-sonuc beklenen-tahta) t)
(test
-siyah-tassiz-tahta
(setf hic'(((nil ("b" nil) nil ("b" nil) nil ("b" nil) nil ("b" nil) )
(("b" nil) nil ("b" nil) nil ("b" nil) nil ("b" nil) nil)
"b" nil) nil ("b" nil) nil ("b" nil) nil ("b" nil) )
(nil (
(nil nil nil nil nil nil nil nil)(nil nil nil nil nil nil nil nil)
(nil nil nil nil nil nil nil nil)(nil nil nil nil nil nil nil nil )12 0)))
(nil nil nil nil nil nil nil nil)) ("siyah icin oyun bitti"
(test -bitti-mi? *siyah* hic-siyah-tassiz-tahta) t)
(oyun
print "Tamam. Temel Birim Testler Gecti") (
"dama-deger.lisp")
(load
-basla *beyaz*)
(oyuna
*tahta*)
(goster -hamlesi '((0 2)(1 3)))
(setq insan(cond ((equal (hamle-kurallara-uygunmu insan-hamlesi *tahta* "b") t)
(progn
-oynat insan-hamlesi *tahta*)
(tasprint "su hareketi yaptiniz")
(print insan-hamlesi)
(*tahta*)
(goster -hamlesi (cadr (altust-arama *tahta*)))
(setq bilgisayarprint "bilgisayarin hareketi")
(print bilgisayar-hamlesi)
(-oynat bilgisayar-hamlesi *tahta*)
(tas-hamle-sayisi (+ bilgisayar-hamle-sayisi 1))
(setf bilgisayar*tahta*)
(goster
))print "HATALI HAREKET"))) (t (
Tek hamlelik bir oyun oynayalım, ve bilgisayarın karşılığını görelim,
!clisp dama-test.lisp
"Tamam. Temel Birim Testler Gecti"
"Tamam. Algoritma Birim Testleri Gecti"
WARNING: DEFUN/DEFMACRO: redefining function TAHTA-DEGERI in
/home/burak/Documents/classnotes/app-math-tr/probsolve/dama-deger.lisp,
was defined in
/home/burak/Documents/classnotes/app-math-tr/probsolve/dama-alg.lisp
"Tamam. Degerlendirme Birim Testleri Gecti"
+=0===1===2===3===4===5===6===7-+
7 | b | | b | | b | | b |
|===============================|
6 b | | b | | b | | b | |
|===============================|
5 | b | | b | | b | | b |
|===============================|
4 | | | | | | | |
|===============================|
3 | | | | | | | |
|===============================|
2 s | | s | | s | | s | |
|===============================|
1 | s | | s | | s | | s |
|===============================|
0 s | | s | | s | | s | |
+=0===1===2===3===4===5===6===7=+
"su hareketi yaptiniz"
((0 2) (1 3))
+=0===1===2===3===4===5===6===7-+
7 | b | | b | | b | | b |
|===============================|
6 b | | b | | b | | b | |
|===============================|
5 | b | | b | | b | | b |
|===============================|
4 | | | | | | | |
|===============================|
3 | s | | | | | | |
|===============================|
2 | | s | | s | | s | |
|===============================|
1 | s | | s | | s | | s |
|===============================|
0 s | | s | | s | | s | |
+=0===1===2===3===4===5===6===7=+
"bilgisayarin hareketi"
((1 5) (0 4))
+=0===1===2===3===4===5===6===7-+
7 | b | | b | | b | | b |
|===============================|
6 b | | b | | b | | b | |
|===============================|
5 | | | b | | b | | b |
|===============================|
4 b | | | | | | | |
|===============================|
3 | s | | | | | | |
|===============================|
2 | | s | | s | | s | |
|===============================|
1 | s | | s | | s | | s |
|===============================|
0 s | | s | | s | | s | |
+=0===1===2===3===4===5===6===7=+
Biz siyah (s) tarafıyız ve ilk hamleyi 0,2
kordinatından
1,3
kordinatına dogru yaptık. Bilgisayar buna karşılık
1,5
’ten 0,4
’e doğru bir hamle yapti. %