Arama ve Karar

Şimdiye kadar model: kod + sayı dosyasıydı. “Yapay zeka” kelimesi daha eski bir şeyi de kapsar ve o şey hâlâ bildiğin programdır. Satranç motoru ağırlık dosyası yüklemez. Yasal hamleleri üretir, bir ağaçta dolaşır, skor fonksiyonuyla dal keser. Derleyici yine javac / g++’dir. Bu yazı o programın ne yaptığını anlatır; sohbet modelinin içi değildir. İkisini karıştırmak, JVM ile GPU sürücüsünü karıştırmak gibidir.

Labirentte çıkışı her koridoru deneyerek bulabilirsiniz. Satrançta her yasal hamleyi sonuna kadar genişletmek imkânsızdır. Klasik araç, bu uzayda nereye bakılacağını seçmekti.

Durum, eylem, uzay

Durum s, problemin o andaki tam tanımıdır: labirentte (x, y), satrançta tahta + sıra. Eylem a, s’yi s' yapar. Geçiş T(s, a) = s' deterministikse arama bir graftır; rastgeleyse beklenti aranır.

Durum uzayı, ulaşılabilir durumların grafıdır. Düğüm durum, kenar eylemdir. Hedef, belirli bir s* (veya küme) veya bir ödülün birikimidir.

Graf yazısındaki BFS ve DFS doğrudan işe yarar. BFS en az adımlı yolu bulur; her katmanı tarar, bellek dallanma kadar büyür. DFS belleği az kullanır, en kısayı vaat etmez. Yönsüz labirentte BFS yeter. Satrançta “en az hamle” değil, kazanan değer aranır.

Dallanma faktörü b, bir durumdaki ortalama yasal eylem sayısıdır. Derinlik d ise ağaç kabaca b^d yaprak üretir. Satrançta b ≈ 35, d = 10 için 35^10 mertebesi, tam genişlemeyi bitirir. Arama, bu üssel patlamayı budamak zorundadır.

Minimax

İki oyunculu, sıfır toplamlı, mükemmel bilgili oyunda (satranç, dama) bir taraf değeri ençoklar, diğeri enazlar. Yaprakta bir değerlendirme u(s) vardır: +1 galibiyet, −1 mağlubiyet, 0 beraberlik; veya malzeme skoru.

İki katlı bir örnek. Sıra bende, üç hamle: A, B, C. Rakip A altında 3 ve 8; B altında 2 ve 4; C altında 5 döndürsün (benim açımdan skor).

• A’yı seçersem rakip min(3, 8) = 3 bırakır.
• B’de min(2, 4) = 2.
• C’de 5.

Ben max(3, 2, 5) = 5 ile C’yi seçerim. “C daha derin kazandırır” bilgisi yoksa, sınırın ötesindeki dünya değerlendirmenin tahminidir.

Alpha-beta, kesin seçilmeyecek dalı keser. α benim garanti alt sınırım, β rakibin garanti üst sınırıdır. Bir dal β’yı geçemezse gerisi taranmaz. Sıralama iyiyse (önce iyi hamle) kesim artar; asıl karmaşıklık aynı kalabilir, pratik derinlik artar.

Sezgisel ve A*

Sezgisel h(s), s’den hedefe kalan maliyetin ucuz tahminidir. ızgarada Manhattan |Δx| + |Δy| duvar yokmuş gibi kalan adımdır. Gerçek maliyetin altında kalan (h(s) ≤ h*(s)) sezgisel admissibledır. A* o zaman en kısa yolu kaçırmaz.

A* düğümü f(s) = g(s) + h(s) ile sıraya koyar. g başlangıçtan gelen gerçek maliyettir. h = 0 ise A*, Dijkstra’ya (ağırlıklı BFS) düşer. h gerçek maliyetin üstündeyse yol kısa olmayabilir; arama yine bir yol bulabilir.

Örnek: ızgarada start (0,0), hedef (2,0), duvar yok, adım maliyeti 1. Manhattan h(0,0) = 2. Komşu (1,0) için g = 1, h = 1, f = 2. (0,1) için g = 1, h = 3, f = 4. A* önce (1,0)’ı açar. Duvar varken h hâlâ alt sınırdır; g gerçek yolu şişirir, f doğru sırayı korur.

Değerlendirme fonksiyonu da bir sezgiseldir: malzeme, kral güvenliği. Gerçeği söylemez; hangi dalın derinleşeceğini söyler.

Arama ≠ dil modeli

Modern bir sohbet modeli hamle ağacını gezmez; token olasılığı üretir. Satranç oynuyorsa bile çoğu zaman arama değil, ezberlenmiş desen ve varsa ayrı bir arama motorudur. İkisini karıştırmak, hatayı yanlış katmanda aratır.

Alıştırma

8 komşulu ızgarada A* için Manhattan yerine Öklid √(Δx² + Δy²) admissible midir? (Evet: düz çizgi, ızgara yolunun altındadır.) Sonra h = 2 * Manhattan kullanın. Neden admissible bozulur ve hangi tür “kısa” yol kaçabilir?