John Krutch
c/o Howard W. Sams & Co.
4300 West 62nd St.
Indianapolis, IN 46268

"Bir insan için bir problemi çözmek ne kadar zorsa, örneğin matematiğin karmaşık bir teoremini kanıtlamak gibi, benzer bir şeyi yapacak bir program yazmak da o kadar zordur."

Bu makale, John Krutch tarafından yazılan Experiments in Artificial Intelligence for Microcomputers adlı kitabın, İkinci Baskı, 1986, içindekiler sayfaları ve 3. Bölümü olan Problem-Solving Programs temel alınarak hazırlanmıştır.

Kitap, Howard W. Sams & Co. tarafından yayımlanmıştır, 4300 West 62nd St., Indianapolis, IN 46268, 164 sayfa, 14,95 $; bu alıntı izin alınarak yeniden basılmıştır ve bu izin için teşekkür edilmektedir.

Bu, BASIC dilinde yazılmış programlar içeren, iyi deneyler sunan, mükemmel ve ilgi çekici bir kitaptır; programlar burada alıntılanmamıştır çünkü biz denklemleri ya da ayrıntılı programlamayı basmıyor, bunun yerine teknik olmayan okurun anlayabileceği materyali sunmaya çalışıyoruz.

İçindekiler

Giriş
Yapay Zekâ ve BASIC
Yapay Zekânın Kapsamı — Yapay Zekâda Yararlı BASIC Komutları — Yapay Zekâda Problem Alanları
Programlama — Kingmove
Oyun Oynayan Programlar
Oyun Programlarının İç Yapısı — Dama
Problem Çözme Programları

Akıl Yürüten Programlar

Geometrik Analoji Programı
Genel Problem Çözücü -- TF
SIR -- Varsayımsal Kıyas
Infer
Argümanların Bilgisayar Analizi
Argümanlar ve Geçerlilik -- Bir Argüman Analiz Programı

Bilgisayar Şiiri

Yaratıcı Süreç
Haiku

Bilgisayar Tarafından Üretilen Metin

Bir Cümlenin Yapı Taşları -- Autowriter

Doğal Dil İşleme

Eliza ve Doctor -- Yapay Paranoyak
Doğal Dili Anlama -- Doctor

Uzman Sistemler

Bazı Uzman Sistemler -- Uzman Sistemlerin İç Yapısı -- Uzman Sistemler Gösterimi

Mavi Gökyüzü Projeleri

Program Üretimi
Müzik Besteleme
Ressam

Bir Program Tarafından BASIC Anahtar Sözcükleri

Otomatik

Checksum Üretici ve Checksum Tabloları

Dizin

Problem Çözme Programları

Bilgisayarlar, ilk üretilenlerden birinin montaj hattından çıkmasından bu yana, iş dünyasında, bilimde ve sanayide problemlerin çözümünde kullanılmaktadır. Ancak bugüne kadarki bilgisayarların problem çözme yeteneği, etkileyici olmakla birlikte, olabileceği kadar geniş kapsamlı değildir. Matematiksel analiz, istatistik, navigasyon ve gök mekaniği gibi alanlarda karmaşık problemleri çözmek üzere programlar yazılabilir; ancak herhangi bir programın çalışabileceği alan, programcı tarafından dar bir biçimde tanımlanmak zorundadır. Ayrıca, bekleneceği gibi, bir insan için bir problemi çözmek ne kadar zorsa, örneğin matematiğin karmaşık bir teoremini kanıtlamak gibi, benzer bir şeyi yapacak bir program yazmak da o kadar zordur.

Bu nedenle birçok araştırmacı, bilgisayarların daha geniş bir yelpazede ve daha zorlayıcı problemleri çözmesini sağlamaya ilgi duymaktadır. Onların geliştirdiği iki programı inceleyeceğiz: Thomas G. Evans'ın geometrik analoji programı ve Newell, Shaw ve Simon'ın Genel Problem Çözücüsü (GPS). Ardından BASIC dilinde yazılmış bir problem çözme programına bakacağız. Programın adı TF'dir ve çözmeye çalıştığı problem ilginçtir: insan davranışının öngörülmesi.

Geometrik Analoji Programı

Çoğu IQ testi üç bölüme ayrılır. Bir bölüm matematiksel yetenekleri, bir bölüm sözel yetenekleri, kalan bölüm ise geometrik şekiller arasındaki analojileri görselleştirme ve bulma yeteneğini test eder.

1963 yılında Thomas G. Evans tarafından yazılan bir geometrik analoji programı, IQ testlerinde yaygın olarak bulunan türdeki geometrik analoji problemlerini çözer ve bunu oldukça iyi bir şekilde yapar. Program basit ve doğrudan bir biçimde çalışır; geometrik analoji problemlerini çözme görevini mekanik bir sürece indirger. Bu türden bir problem şekil 3-1'de gösterilmektedir. Evans programının bunu nasıl çözmeye çalışacağını görelim.

Şekil 3-1'de yedi şekil vardır; bunlar 1, 2, 3, a, b, c ve d olarak etiketlenmiştir. Problem şu şekilde ifade edilebilir: 1, 2'ye nasıl ise, 3 de a, b, c ya da d'den hangisine öyledir?

Şekil 3-1
Geometrik analoji problemi

Dönüşümlerin Karşılaştırılması

Biraz durup düşünürsek, bu problemin çözümünün dönüşümlerin karşılaştırılması etrafında döndüğünü göreceğiz. Bununla ne kastedildiğini anlamak için, beş çift şeklin söz konusu olduğuna dikkat edin. Bu çiftler şunlardır:

Her bir şekil çifti bir dönüşümü temsil eder. Örneğin 1:2 çifti, 1 numaralı bir şeklin 2 numaralı şekle dönüştürüldüğünü ifade eder. Program, 1 ile 2 arasındaki dönüşümün ne olduğunu belirlemeli ve 3:a, 3:b, 3:c ya da 3:d çiftlerinden hangisinin aynı dönüşümü (ya da ona en yakın olanı) temsil ettiğine karar vermelidir.

Programın yapması gereken ilk şey, geometrik şekillerin her birinin önemli konumsal özelliklerinin bir temsilini oluşturmaktır. p bir daireyi, q eşkenar bir üçgeni ve r bir kareyi temsil etsin; şekil 3-1'deki her bir şekil için oluşturulan temsil aşağıdakine benzer olacaktır:

1: p'nin içinde q
2: q
3: q'nun içinde r
a: q
b: q
c: r
d: p

Bu listedeki tek konumsal ilişki içindedir. Gelişebilecek diğer ilişkiler (şekle bağlı olarak), örneğin üstünde ve solunda olabilir.

Program temsilleri ürettikten sonra, her bir şekil çiftini inceleyerek dönüşümün sağ tarafındaki şeklin, sol taraftaki şekle göre nasıl değiştirildiğini kontrol eder. Sonuç şudur:

1:2
p silindi
q ölçek değişimi × 2
q 60 derece döndürüldü
3:a
r silindi
3:b
q ölçek değişimi × ½
q 60 derece döndürüldü
r silindi
3:c
q silindi
r ölçek değişimi × 2
r 45 derece döndürüldü
3:d
q silindi
r silindi

Son adım, 3:a, 3:b, 3:c ve 3:d çiftleri için elde edilen dönüşümleri, 1:2 çifti için elde edilen dönüşümlerle karşılaştırmaktır. 1:2 dönüşümüne en çok uyan dönüşüm cevaptır. Bu örnekte program c'yi seçecektir.

İnsan Düşünce Süreçlerinin Taklit Edilmesi

Bu problemi çözmeye çalışsaydınız, program tarafından kullanılan yöntemlerin birçoğunu kullanabilirdiniz. Muhtemelen 1:2 çiftine bakar, 1'in 2'yi elde etmek için nasıl dönüştürüldüğünü belirlersiniz ve ardından 3:a, 3:b, 3:c ve 3:d çiftleri arasından aynı dönüşümü içeren bir çift bulmaya çalışırdınız. Evans'ın programının yaptığı tam olarak budur.

Bu, Evans'ın programı yazarken kendi düşünce süreçlerini bir model olarak kullandığını ima eder. Bu teknik burada son derece başarılı olsa da, insan düşünce süreçlerini taklit etmek her zaman bazı "akıllı" işlemleri gerçekleştirmek için en iyi yol değildir ve hatta parmaklarınızla saymak yerine hesap makinesi kullanmak gibi, son derece verimsiz bir yöntem olabilir. Hatta, insan düşünce süreçlerine dayanmayan bir algoritma kullanılsaydı Evans programının iyileştirilmesi bile mümkün olabilirdi. Ancak, tamamen yeni bir görev gerçekleştirme yolunu bulup bunu bir programa dahil etmek, beynimize yerleşmiş gibi görünen bir algoritmadan yararlanmaktan daha zor olurdu.

Genel Problem Çözücü

Geometrik analoji programı problem çözme stratejisinin bir parçası olarak insan düşünce süreçlerinden örtük biçimde yararlanıyorsa, Genel Problem Çözücü (GPS) bunu oldukça açık bir biçimde yapar. Hatta insan problem çözmesine ilişkin psikolojik kuramları bünyesinde barındırır. Geometrik analoji programı yalnızca tek bir problem sınıfı üzerinde çalışabilir. Adından da anlaşılacağı üzere Genel Problem Çözücü, çok daha geniş bir problem yelpazesini çözebilir; ancak bu yelpaze sınırsız değildir.

GPS, durumlar ve operatörler olarak adlandırılan iki hayati veri kategorisini kullanır. Durumlar ve operatörler ile ne kastedildiğini anlamak için bir örneğe bakalım.

Diyelim ki arabanıza bindiniz ve marşı çevirdiniz. Araba çalışmıyor. Çalıştırmak için birkaç deneme yapıyorsunuz, ancak yine de çalışmayı reddediyor. Bir probleminiz var.

Başlangıç Durumunun ve Hedef Durumun Tanımlanması

Problem, durumlar cinsinden tanımlanabilir. Durum terimi, burada kullandığımız şekliyle, işlerin durumu ifadesinin bir kısaltması olarak düşünülebilir. Problemin bir başlangıç durumu ve bir hedef durumu vardır. Başlangıç durumu, problemin başlangıçtaki durumudur: araba çalışmaz. Hedef durum ise ulaşmak istediğiniz durumdur: arabanın motorunun düzgün şekilde dönmesi. Bu durum, şekil 3-2’de grafiksel olarak gösterilmiştir.

Şekil 3-2 incelendiğinde, hedef durumun başlangıç durumunda bulunmayan bir şeyi içerdiği görülebilir; bu şeye iki durum arasındaki fark denir. Araba çalışmıyor başlangıç durumu ile araba çalışıyor hedef durumu arasındaki fark, basitçe motorun dönmesi olarak ifade edilebilir. Başlangıç durumundan hedef duruma geçebilmek için, iki durum arasındaki farkın sıfıra indirilmesi gerekir.

Şekil 3-2
Durumlar cinsinden ifade edilmiş bir problem

Şimdi tekrar arabaya dönelim. Arabadan inersiniz, kaputu açarsınız ve motora bakarsınız. Keskin bir benzin kokusu algılarsınız ve motorun boğulmuş olduğunu fark edersiniz. Arabayı çalıştırmak için marşa basarken gaz pedalına sonuna kadar basmanız ve orada tutmanız gerekir. (Bu işlem, jikle ve gaz kelebeği valflerinin tamamen açılmasına neden olarak karbüratördeki fazla benzini dışarı atar.)

Bir Operatör ve Bir Ara Durum Geliştirme

Az önce bir operatör geliştirdiniz. Bir operatör, durum X’e uygulandığında durum X’i durum Y’ye dönüştüren bir kuraldır. Bir operatör, şekil 3-3’te gösterildiği gibi, grafiksel olarak bir ok ile temsil edilir.

PRESS-ACCELERATOR-TO-FLOOR

Şekil 3-3
Bir operatör

Amacınız, başlangıç durumu ile hedef durum arasındaki farkı sıfıra indirmektir. Başlangıç durumu araba çalışmıyor, hedef durum araba çalışıyor ve iki durum arasındaki fark motorun dönmesidir. Öyleyse, görünüşe göre, iki durum arasındaki farkı sıfıra indirmek (böylece başlangıç durumunu hedef duruma dönüştürmek) için yapmanız gereken tek şey, press-accelerator-to-floor operatörünü başlangıç durumuna uygulamaktır.

Ancak press-accelerator-to-floor operatörü başlangıç durumuna uygulanamaz. Neden? Çünkü arabanın dışındasınız. Bu nedenle, başlangıç durumundan get-into-car operatörü aracılığıyla ulaşılabilen ve sürücü arabada adını vereceğimiz bir ara durum belirlersiniz.

Artık yapbozun tüm parçaları bir araya gelmiştir ve arabanızı çalıştırma problemi çözüme hazırdır:

Başlangıç durumu ile ara durum arasındaki farkı bulun. Fark arabada oturuyordur.
Başlangıç durumuna uygun operatörü, yani get-into-car operatörünü uygulayarak, başlangıç durumu ile ara durum arasındaki farkı sıfıra indirin. Bu noktada ara duruma ulaşmış olursunuz.
Ara durum ile hedef durum arasındaki farkı bulun. Bu fark motorun dönmesidir.
Uygun operatörü, yani press-accelerator-to-floor operatörünü uygulayarak, ara durum ile hedef durum arasındaki farkı sıfıra indirin.

Hedef duruma ulaşmış olursunuz; problem çözülmüştür. Tüm süreç şekil 3-4’te özetlenmiştir.

Şekil 3-4
Arabayı çalıştırma probleminin çözümü

Yukarıdaki açıklama, elbette, bir kişinin boğulmuş bir motoru çalıştırma ya da başka herhangi bir problemi çözmeye çalışırken tüm bu adımların farkında olduğu anlamına gelmez. Ancak, insan problem çözme üzerine en az bir kurama göre, kişi bu süreçlerin farkında olmasa bile, bir problemi çözmekle meşgulken gerçekleşebilecek içsel süreçlerin makul bir temsilidir; bu süreçlerin farkına varmak ise ancak yoğun bir düşünme ile mümkündür.

Çözümleri Bizimkine Çok Benzer Şekilde Bulmak

Genel Problem Çözücü (General Problem Solver), problemlere çözümleri, arabayı çalıştırma problemine bulduğumuz çözüme çok benzer bir şekilde bulur. Çözmesi gereken bir görevle karşılaştığında, önce başlangıç durumu ile hedef durum arasındaki farkı bulur. Ardından, iki durum arasındaki farkı sıfıra indirecek bir operatörü uygulamaya çalışır. Bunu yapacak bir operatörü kendi repertuvarında bulamazsa, GPS gerekli olduğu kadar ara durum belirler, bir ara durum ile bir sonraki arasındaki farkı bulur ve uygun operatörü—varsa—kullanarak, hedef duruma ulaşılana kadar durumlar arasındaki farkı azaltır.

GPS’in kendi kendine, yoktan operatörler geliştiremeyeceğini belirtmek önemlidir. Operatörler (problemin özlü bir ifadesi dâhil olmak üzere, pek çok başka unsurla birlikte) bir programcı tarafından GPS’e dikkatle kodlanmalıdır. Ancak, insanların da aynı sınırlamaya sahip olduğunu belirtmek adildir; bir şekilde, problem çözme sürecinde kullandığımız operatörlerin çoğu ya da tamamı bize verilmiş olmalıdır. Boğulmuş bir motoru çalıştırmaya çalışıyor olsaydınız, bu bilginin bir tamirciden ya da başka bir kaynaktan edinilmemiş olması durumunda, press-accelerator-to-floor’un geçerli bir operatör olduğunu bilemezdiniz. Bu operatör, otomobil motorları hakkında genel bir bilgiden türetilebilir; ancak bu türetme de, nihayetinde dışarıdan gelmiş olması gereken verilere dayanır.

GPS çok çeşitli görevleri çözebilir. Tek ve bütünleşik bir programdır—özelleşmiş görevleri yerine getiren daha küçük programların bir koleksiyonu değildir. Yine de basit kalkülüs problemlerini çözebilir, mantık teoremlerini kanıtlayabilir ve İngilizce cümleleri ayrıştırabilir (sözdizimsel yapısını analiz edebilir). Bir örüntü sergileyen herhangi bir harf dizisi verildiğinde, bu dizideki bir sonraki harfleri bulabilir. GPS ayrıca şunları da çözebilir

Barkod: Yeni Bir Veri Dili

Şekil 3-5’te gösterilen Hanoi Kuleleri problemi. Bu problemde, 1 numaralı çubuktaki "kule" 3 numaralı çubuğa aktarılmalıdır. Aynı anda yalnızca bir halka aktarılabilir ve daha büyük bir halka, daha küçük bir halkanın üzerine konulamaz.

Şekil 3-5
Hanoi Kuleleri problemi

GPS, iyi bilinen Misyonerler ve Yamyamlar probleminin de çözümünü bulabilir. Bir nehrin kıyısında üç misyoner ve üç yamyam vardır. Misyonerlerin bir ya da iki kişiyi taşıyabilen bir tekneleri vardır. Eğer herhangi bir anda iki kıyıdan birinde misyonerler sayıca yamyamlardan az kalırsa, o misyonerler yenir. Misyonerler herkesin sağlam biçimde nehrin karşı kıyısına geçmesini nasıl sağlayabilir?

GPS bu problemi çözmek için on altı dakika harcadı; siz de çözmeyi deneyip sürenizi GPS’inkiyle karşılaştırmak isteyebilirsiniz.

TF: Öngörücü Problem Çözme Programı

Şimdi BASIC dilinde yazılmış TF adlı bir problem çözme programını ele alacağız. TF bir öngörü oyunudur. Geçmiş davranışlarınıza ilişkin gözlemlerine dayanarak bir sonraki eyleminizi tahmin etmeye çalışır. Rastgele T ya da F harfini yazarsınız; programın görevi, bir sonraki hangi harfi yazacağınızı belirlemektir.

Elbette normalde, önceki öğeleri inceleyerek rastgele bir dizinin bir öğesinin ne olacağını söylemenin bir yolu yoktur; bu nedenle buna rastgele dizi denir. Ancak TF yazılırken şu varsayım yapıldı: bir insanın davranışı hiçbir zaman gerçekten rastgele olamaz; yanıtlarınızı ne kadar rastgeleleştirmeye çalışsanız da, farkında olmadığınız davranış kalıpları bulunabilir.

Bu nedenle program, T ya da F olsun her yanıtı saklar ve davranışınızdaki kalıpları arar. Bir kalıp bulursa ve bu kalıp yeniden ortaya çıkarsa, program bir tahmin yapabilir. Şekil 3-6, TF programını çalıştıran bir bilgisayarın ekran çıktısıdır.

SİZ YAZDINIZ:
BİLGİSAYARIN TAHMİNİ:
TOPLAM GİRİŞ SAYISI: 115
BİLGİSAYARIN DOĞRU TAHMİN SAYISI: 62
BİLGİSAYARIN DOĞRU TAHMİN YÜZDESİ: %53,9

Şekil 3-6
TF ekran çıktısı

Ana Program

Aşağıda TF ana programı verilmiştir:

T
T

(Teknik ayrıntılar için lütfen kitaba bakınız.)

Experiments in Artificial Intelligence and Problem Solving Programs