Amiral Battı: Bilgisayar Gemilerinizi Nasıl Buluyor?

Amiral Battı, çocukken babamla oynadığım oyundu; kendi sürümümü tasarlamak istememin nedeni de bu. Lise bitirme projelerimden biri olarak C# ile masaüstünde çalışan bir sürüm yazdım; özgün kodu GitHub’da duruyor. O sürüm sade bir oyundu. Bu yazıda anlatacağım av ve hedef algoritması sonradan geldi; bugün sitedeki oyunda Normal seviye bu algoritmayla oynuyor.

Amiral Battı ilk bakışta bir şans oyunu gibi görünür. İki oyuncu gemilerini birbirinden saklar ve sırayla birer hücre söyler; ortada su sıçramalarından ve isabetlerden başka görünen bir şey yoktur. Oysa rakibi hakkında hiçbir şey bilmeyen bir bilgisayar bile, bütün filoyu gözü kapalı ateş eden birinin harcayacağı atışların yarısından azıyla batırabilir. İşin sırrı: biraz sayma, biraz olasılık ve birkaç basit kural.

Bu yazıda sitedeki oyunun bilgisayar rakibini, üç zorluk seviyesine sırayla bakarak tanıyacağız: Kolay seviye rastgele ateş ediyor, Normal seviye av ve hedef ile oynuyor, Zor seviye ise gemilerin hâlâ saklanabileceği her yeri sayıyor. Matematik bilmeniz gerekmiyor; her formülü ve her sembolü, ilk göründüğü yerde sade bir dille açıklayacağım. Yazıdaki bütün tahtalar, grafikler ve simülasyon sonuçları da site hazırlanırken oyunun kendi koduyla hesaplanıyor: Bir şekil bilgisayarın E5’e ateş ettiğini gösteriyorsa, oyun gerçekten E5’i seçmiştir.

Oyunun kuralları

Tahta 10 × 10’luk bir ızgara, yani 100 hücre. Sütunlar soldan sağa A’dan J’ye harflerle, satırlar yukarıdan aşağıya 1’den 10’a sayılarla adlandırılır; E5, E sütunuyla 5. satırın kesiştiği hücredir. Her oyuncunun beş gemisi var: beş hücrelik bir uçak gemisi, dört hücrelik bir zırhlı, üçer hücrelik bir kruvazörle bir denizaltı ve iki hücrelik bir muhrip. Hepsi birlikte 17 hücre eder.

Gemiler tahtanın içinde yatay ya da dikey durur. Bu sitede birbirine değebilirler ama üst üste binemezler. Sırası gelen oyuncu bir hücre söyler, karşı taraf “ıska” ya da “isabet” diye yanıt verir. Bir geminin son hücresi de vurulunca o gemi batar ve oyun batan geminin yerini gösterir; artık tam olarak hangi hücrelerde durduğu bellidir.

Bilgisayarın nasıl oynadığına geçmeden önce küçük bir sayma alıştırması yapalım. Bu sayılar ileride işimize yarayacak.

Bir gemi kaç farklı yere saklanabilir?

Bir geminin tahtada durabileceği her yere bir konum diyelim. Tek bir geminin kaç konumu var? Hadi birlikte sayalım. Hesabı her tahta ve her gemi için bir kerede yapalım; bunun için iki harf yeter: Tahtanın bir kenarındaki hücre sayısına $n$, geminin boyuna $L$ diyelim. Bizim tahtamızda $n = 10$, kruvazör için de $L = 3$. Harfleri gördüğünüz yerde bu sayıları düşünebilirsiniz.

Birinci adım: tek bir satır. Bir satırın hücrelerini soldan sağa 1, 2, …, $n$ diye numaralayalım. $L$ boyundaki bir gemi bu satırda yan yana $L$ hücre kaplar. Geminin yerini, başladığı hücre, yani en soldaki hücresi belirler; bu hücrenin numarasına $k$ diyelim. Gemi $k$ numaralı hücreden başlar ve $L$ hücre boyunca uzanır:

Örneğin 4. hücreden başlayan bir kruvazör 4, 5 ve 6 numaralı hücreleri kaplar; son hücresi $4 + 3 - 1 = 6$. Geminin tahtadan taşmaması için son hücresinin numarası en fazla $n$ olmalı ($\le$ işareti “küçük ya da eşit” demek):

(Sağdakini bulmak için soldakinin iki tarafından da $L - 1$ çıkardık.) $k$ en az 1 olduğuna göre, geminin başlayabileceği hücreler 1, 2, …, $n - L + 1$ olur. Demek ki bir satırda tam $n - L + 1$ konum var. Kruvazör için $10 - 3 + 1 = 8$.

İkinci adım: bütün satırlar. Tahtada $n$ satır var ve her birinde $n - L + 1$ konum. Aynı sayıyı $n$ kez toplamak, onu $n$ ile çarpmak demek; saymanın çarpma kuralı da budur. Yatay konumların sayısı:

(İki şeyi aralarına işaret koymadan yan yana yazmak, matematikte onları çarpmak demek. İki sayının arasına konan $\cdot$ noktası da çarpma işareti.) Kruvazör için $10 \cdot 8 = 80$.

Üçüncü adım: sütunlar. Tahta kare olduğu için aynı hesap sütunlarda da işler. Tahtayı 90 derece çevirdiğinizi düşünün: Satırlar sütun, yatay gemiler dikey gemi olur. Demek ki dikey konumların sayısı da $n\,(n - L + 1)$; kruvazör için yine 80.

Dördüncü adım: hepsi birden. Bir gemi ya yatay durur ya dikey; ikisi birden olamaz. Birbirine karışmayan iki grubun eleman sayılarını toplamak yeter (bu da toplama kuralı):

Kruvazör için $2 \cdot 10 \cdot (10 - 3 + 1) = 2 \cdot 10 \cdot 8 = 160$.

(Bu hesap en az iki hücrelik gemiler için geçerli: Tek hücrelik bir geminin “yatay” ve “dikey” hâli aynı konum olurdu ve formül her konumu iki kez sayardı. Neyse ki filoda tek hücrelik gemi yok.)

Filodaki gemilerin boyları 5, 4, 3, 3 ve 2. Formül bunlar için sırasıyla 120, 140, 160, 160 ve 180 konum verir; hepsi birlikte 760.

Gemi	Hücre	Konum
Uçak gemisi	5	2 · 10 · 6 = 120
Zırhlı	4	2 · 10 · 7 = 140
Kruvazör	3	2 · 10 · 8 = 160
Denizaltı	3	2 · 10 · 8 = 160
Muhrip	2	2 · 10 · 9 = 180
Filo	17	760

Bütün filo kaç türlü dizilir?

Tek bir gemi en fazla 180 konumda durabiliyor. Peki beş gemi birlikte kaç farklı biçimde dizilebilir?

Gemiler üst üste binebilseydi yanıt kolay olurdu. Her gemi yerini ötekilerden bağımsız olarak seçerdi ve yine çarpma kuralı yeterdi: Uçak gemisinin 120 konumunun her biri için zırhlının 140 konumu, bunların her biri için kruvazörün 160 konumu; böyle devam eder. Sonuç 120 · 140 · 160 · 160 · 180 = 77.414.400.000 olurdu.

Ama gemiler üst üste binemez ve bu her şeyi değiştirir. Bir geminin nereye sığacağı, ötekilerin nerede durduğuna bağlıdır: Uçak gemisi tahtanın ortasına yerleştiyse zırhlıya daha az yer kalır. Bu yüzden sonucu tek satırda veren basit bir formül yok. Ben de bilgisayara saydırdım. Önce en büyük üç gemiyi, yani uçak gemisini, zırhlıyı ve kruvazörü, üst üste binmeden durabilecekleri her biçimde tek tek dizdim. Her dizilimde denizaltıyla muhribin boşta kalan konumlarını sayıp bu iki sayıyı çarptım (yine çarpma kuralı); sonra denizaltıyla muhribin üst üste bindiği çiftleri çıkardım. Sonuç: 30.093.975.536 farklı filo. Yani üst üste binmeyi yasaklayınca, az önceki hesaptaki dizilimlerin yalnızca %39 kadarı geriye kalıyor.

Bir ayrıntı: Kruvazörle denizaltı ikisi de üç hücrelik olsa da farklı gemiler; ikisinin yerlerini değiş tokuş etmek yeni bir dizilim sayılıyor.

Bu kadar çok filoyu tek tek gözden geçiren bir oyuncu yok; ne insan ne program. Üstelik her atış bu listeden bazı filoları eler ve hangilerini elediğini söylemek hiç kolay değil. Bu yüzden aşağıdaki stratejilerin hepsi filoyu bir bütün olarak değil, her gemiyi ayrı ayrı düşünüyor.

Kıyas noktası: rastgele atış

Önce en saf rakiple başlayalım. Kolay seviye, daha önce ateş etmediği hücrelerden birini rastgele seçer; gözü kapalı nişan almak gibi. Bu seviyeyi, öbür seviyelerin ne kadar akıllı olduğunu ölçeceğimiz bir cetvel olarak kullanacağız. Soru şu: Rastgele ateş eden biri bütün filoyu ortalama kaç atışta batırır?

Bir oyunun kaç atış sürdüğüne $T$ diyelim. $T$ her oyunda başka çıkar: Bazen şans yüzünüze güler, bazen son gemi hücresi en sona kalır. Bu yüzden tek bir oyunu değil, çok sayıda oyunun ortalamasını soruyoruz. Sayısız oyun oynayıp $T$ değerlerinin ortalamasını alsaydık, bu ortalama belli bir sayıya otururdu. Bu sayıya $T$’nin beklenen değeri denir ve $\mathbb{E}[T]$ diye yazılır (E harfi, İngilizcede “beklenen” anlamına gelen expected kelimesinden geliyor).

Bu sayıyı neden hesaplıyoruz? İki sebebi var. Birincisi, akıllı seviyeleri bu sayıyla kıyaslayacağız. İkincisi, yazının sonundaki simülasyonu bu sayıyla denetleyeceğiz: Bilgisayarda oynattığımız Kolay oyunların ortalaması, formülün verdiği sayıya çok yakın çıkmalı. Çıkıyor da: simülasyonda 95,4 atış, formülde 95,4 atış.

Şimdi hesaplayalım. Şöyle düşünün: Elinizde 100 kartlık bir deste var; kartların 17 tanesi kırmızı (gemi hücreleri), geri kalan 83 tanesi siyah (boş su). Rastgele ateş etmek, desteyi iyice karıştırıp kartları sırayla açmak gibi. Oyun, son kırmızı kart açıldığı anda biter.

Kırmızı kartlar siyahları yığınlara ayırır: ilk kırmızıdan önceki yığın, art arda gelen iki kırmızı arasındaki yığınlar ve son kırmızıdan sonraki yığın. 17 kırmızı kart olduğu için 18 yığın var; bazıları boş da olabilir. İyi karıştırılmış bir deste hiçbir yığını kayırmaz, bu yüzden ortalama olarak her yığında eşit sayıda kart olur: 83 siyah kart 18 yığına dağılır, yığın başına ortalama $83/18$ (83 bölü 18), yani yaklaşık 4,6 kart.

Oyun son kırmızı kartta bittiğine göre, açılmadan kalan tek yığın en sondaki yığın. Demek ki ortalama bir oyunda 100 karttan yalnızca son yığın kadarı açılmadan kalır:

($\approx$ işareti “yaklaşık eşit” demek.) Dikkat: 95,4 bir yüzde değil, bir atış sayısı. Yüzdeye benzemesinin tek sebebi tahtanın tam 100 hücre olması. Söylediği şey şu: Rastgele ateş eden biri, filoyu batırana kadar ortalama olarak tahtanın neredeyse tamamını tarar; hiç dokunulmadan kalan hücre ortalama yalnızca 4,6 tane.

Ortalamanın ötesine de geçebiliriz. Oyunun 85 atış içinde bitme olasılığı nedir? Bu, 17 kırmızı kartın hepsinin ilk 85 kartın arasına düşmesi demek. Karıştırılmış destede kırmızıların düştüğü yerler, 100 sıradan rastgele seçilmiş 17 sıradır. $\binom{100}{17}$ sembolü, 100 şeyin arasından 17 tanesini kaç farklı biçimde seçebileceğimizi gösterir (hangisinin önce seçildiği önemsiz). Bu seçimlerin hepsi eşit olasılıklı ve bunlardan $\binom{85}{17}$ tanesinde bütün kırmızılar ilk 85 sıraya düşüyor. Olasılık da bu ikisinin oranı:

Bu olasılık yalnızca %4,8. Aynı hesabı 85 yerine her atış sayısı için yapabiliriz; yazının sonundaki grafikte noktalı eğri bunu gösteriyor. Oyunları kısadan uzuna dizseniz tam ortadaki oyun 97 atış sürer (buna medyan denir). Rastgele atış filoyu eninde sonunda batırır, ama genellikle neredeyse bütün suyu taradıktan sonra.

Av ve hedef

Hiç teori bilmeyen biri bile rastgele ateş eden birinden çok daha iyi oynar. Bir gemiyi vurduğunuzda ne yaparsınız? Gemi batana kadar çevresine ateş edersiniz. Peşine düşeceğiniz bir isabet yokken de atışlarınızı tahtaya yayarsınız. Normal seviye tam olarak bunu yapıyor. Birincisine hedef, ikincisine av diyoruz; ikisine ayrı ayrı bakalım.

Hedef modu: bir gemiyi bitirmek

Bir isabet, o hücrede bir gemi olduğunu söyler. Gemiler düz durduğu için geminin geri kalanı aynı satırda ya da aynı sütunda olmalı. Bilgisayar bu yüzden isabetin dört komşusunu, yani üstünü, altını, solunu ve sağını dener. İkinci bir isabet birincinin yanına düşünce geminin yönü belli olur. Bilgisayar artık isabet dizisini iki ucundan uzatır; uçlardan biri bir ıskaya ya da tahtanın kenarına dayanınca öbür uçtan devam eder.

Atış	Hücre	Sonuç	Sonra
1	E5	isabet	Hedef
2	E4	ıska	Hedef
3	E6	ıska	Hedef
4	F5	isabet	Çizgi
5	G5	ıska	Çizgi
6	D5	isabet, battı	Av

• Iska, sıra numarasıyla
• İsabet, sıra numarasıyla
• Batmış gemi

İki ince nokta daha var. Birincisi, bilgisayar bir gemiyi kovalarken başka bir gemiyi de vurabilir; örneğin iki gemi yan yana durduğunda. Bu yüzden “kovaladığım gemi” diye bir şey aklında tutmaz. Henüz batmamış gemilere ait bütün isabetlere bakar; bunlara açık isabet diyelim. İkincisi, bir gemi batınca oyun onun hangi hücrelerde durduğunu gösterir. O hücrelerdeki isabetler kapanır. Geride açık isabet kaldıysa başka bir gemiye aittir ve bilgisayar bu kez onun peşine düşer. Ava ancak hiç açık isabet kalmayınca döner.

Av modu: parite

Peki peşine düşecek bir isabet yokken nereye ateş etmeli? Bir ıskanın hemen yanına ateş etmek biraz israftır: Iska, iki hücreyi birlikte kaplayabilecek bütün gemi konumlarını zaten eledi; bu yüzden yandaki hücrede gemi bulma şansı daha düşük.

Şöyle düşünün: Tahtayı dama tahtası gibi siyah ve beyaz boyayalım. Yan yana iki hücre her zaman farklı renktedir. En kısa gemi bile iki hücre uzunluğunda olduğu için her gemi en az bir siyah hücrenin üzerinden geçer. Öyleyse yalnızca siyah hücrelere ateş eden biri hiçbir gemiyi kaçırmaz; üstelik taranacak hücre sayısı 100 yerine 50 olur. Siyah hücreleri, satır ve sütun numaralarının toplamı çift olanlar diye seçebiliriz; birazdan bunu matematikçe de yazacağız.

Daha az hücre yetmez mi? Yetmez. Tahtayı yan yana iki hücrelik 50 domino taşıyla boşluksuz döşeyebilirsiniz ve muhrip bu taşlardan herhangi birinin altında saklanıyor olabilir. Muhribi nerede olursa olsun yakalamak isteyen biri, her taşın en az bir hücresine ateş etmek zorundadır. Yani en az 50 hücre gerekir.

Muhrip battıktan sonra en kısa gemi üç hücrelik olur ve dama tahtasından da seyrek bir desen yeter. Genel kuralı görmek için satırları ve sütunları bu kez 0’dan başlayarak numaralayalım (A sütunu 0, B sütunu 1, …; 1. satır 0, 2. satır 1, …); oyunun kodu da böyle sayıyor. Satır numarasına $r$, sütun numarasına $c$ diyelim, bir de 2 ya da 3 gibi bir $m$ sayısı seçelim.

Burada çok işimize yarayacak bir gösterim var: mod. Bir sayının yalnızca $m$’ye bölümünden kalanına bakmak demek, tıpkı saat gibi. Saat 12’den sonra başa döndüğü için 15.00 ile 3.00 aynı yeri gösterir. Matematikçiler bunu $15 \equiv 3 \pmod{12}$ diye yazar ve “15, mod 12’de 3’e denktir” diye okur. Yani iki sayı $m$’ye bölündüğünde aynı kalanı veriyorsa, bu iki sayı mod $m$’de denktir. Kalanı 0 olan sayılar da $m$’nin katlarıdır: 0, $m$, $2m$, …

Artık tarama desenini tek satırda yazabiliriz. Satır ve sütun numaralarının toplamı $m$’nin katı olan hücreleri seçiyoruz:

($\Lambda$, “lambda” diye okunan Yunan harfi; burada yalnızca desenin adı.) $m = 2$ için bunlar $r + c$ toplamının çift olduğu hücreler, yani baştaki dama tahtasının ta kendisi. Fikrin adı da buradan geliyor: parite, bir sayının 2’ye bölümünden kalan, yani tek mi çift mi olduğu.

Peki her gemi neden bu desene yakalanıyor? Yatay bir gemide satır numarası sabit kalır, sütun numarası birer birer artar; dikey bir gemide de tam tersi. Yani bir geminin ilk hücresinde toplam $s$ ise, $L$ boyundaki bu geminin hücrelerinde toplam sırayla şöyle gider:

Art arda gelen sayıların mod $m$’deki kalanları da saatin akrebi gibi sırayla döner: …, $m - 2$, $m - 1$, 0, 1, … Bu yüzden art arda gelen herhangi $m$ sayının kalanları $0, 1, \dots, m - 1$ değerlerinin her birini tam bir kez alır; aralarından biri mutlaka 0’dır. Hatta hangisi olduğunu da söyleyebiliriz: $s$’nin kalanı $a$ ise, $k = (m - a) \bmod m$ adım sonraki hücrede $s + k \equiv 0 \pmod{m}$ olur ve $k$ en fazla $m - 1$’dir. Demek ki boyu en az $m$ olan ($L \ge m$) her gemi, $\Lambda_m$ deseninin en az bir hücresinin üzerinden geçer.

Gemi $m$’den kısaysa bu garanti ortadan kalkar. $m = 3$ iken ilk toplamı $s \equiv 1 \pmod{3}$ olan bir muhribin iki hücresinin kalanları 1 ve 2 olur; hiçbiri 0 değildir ve muhrip desenin arasından sıyrılır. Aşağıdaki şekilde tam böyle bir muhrip var: G2–H2’de, $s = 1 + 6 = 7 \equiv 1 \pmod{3}$.

Normal seviye $m$ olarak su üstündeki en kısa geminin boyunu alır. Muhrip su üstünde kaldıkça $m = 2$ olur: dama tahtası. Muhrip batınca $m = 3$ olur ve desen, her üç çaprazdan birinin üzerindeki 34 hücreye seyrelir.

m = 2 · 50 hücre

m = 3 · 34 hücre

• Desen hücresi
• Geminin kapladığı desen hücresi
• Aradan sıyrılan muhrip

Bunu gerçek bir oyunda izlemek, anlatmaktan daha kolay. Aşağıda Normal seviye, yazının sonundaki simülasyonun 743 numaralı oyunundaki filoyu baştan sona batırıyor. Bu oyunu şanslı olduğu için seçmedim; sayıları, birazdan göreceğimiz ortalamalara çok yakın. Atışları iki türe ayıracağız: Açık isabet yokken yapılan atış bir av atışı, geri kalan her atış bir hedef atışı.

Av biçimi

Desen açıkDesen kapalı

Atış

21 / 49

Son atış

E7 · isabet

Atış türü

Av atışı

Tarama deseni

m = 2 · 50 hücre

Av atışları

17

Hedef atışları

4

Batan gemiler

1 / 5

• Iska, sıra numarasıyla
• İsabet, sıra numarasıyla
• Son atış
• Batmamış gemi
• Batmış gemi
• Desen hücresi

Bu oyundaki atışlar

Desen açık

3613

49

Desen kapalı

4316

59

• Av atışları
• Hedef atışları

Bu oyunda desen 10 atış kazandırdı (59 yerine 49) ve farkın çoğu av atışlarından geliyor: av atışları 43 yerine 36, hedef atışları 16 yerine 13.

Tek bir oyun şansa bağlı olabilir, ama 1.000 oyunun ortalaması da aynı şeyi söylüyor. Yazının sonundaki simülasyonda desen, oyun başına ortalama 9,8 atış kazandırıyor: Av ve hedef desensiz ortalama 60,3 atış, desenle 50,5 atış sürüyor. Desen taranacak hücreleri yarıya indiriyor ama oyunu yarıya indirmekten çok uzak: Desenden yalnızca av atışları yararlanıyor, onlar da yarıya inmiyor; gemileri bitiren atışlar ise iki durumda da aşağı yukarı aynı. Desen en kötü durumu da iyileştiriyor: 1.000 oyunun en uzunu desenle 74, desensiz 100 atış sürdü.

Durum makinesi

Parçaları birleştirince Normal seviye küçük bir durum makinesine dönüşür. Adı karmaşık ama fikir basit: Bilgisayar her an birkaç durumdan birindedir, tıpkı bir trafik lambasının yeşil, sarı ya da kırmızı yanması gibi; her atışın sonucu onu bir sonraki duruma geçirir.

Kodda “şu an hangi durumdayım” diye bir kayıt yok. Bilgisayar hangi durumda olduğunu her atıştan önce tahtaya bakarak yeniden buluyor: Açık isabet yoksa avlanıyordur. Yan yana iki açık isabet varsa ve dizinin bir ucunda henüz ateş edilmemiş bir hücre duruyorsa çizgiyi izliyordur. Bunların dışında hedefliyordur. Durum her seferinde tahtadan okunduğu için tahtayla asla çelişemez.

Battı adımı, bilgisayarın ıska ya da isabetten fazlasını öğrendiği tek an.

Olasılık yoğunluğu

Av ve hedef, filo hakkında tek bir bilgi kullanır: en kısa geminin boyu. Zor seviye ise su üstündeki her geminin boyunu kullanır. Her atıştan önce her hücre için şunu sorar: Şimdiye kadar gördüklerimle çelişmeden, kalan gemiler bu hücreyi kaç farklı biçimde kaplayabilir? Sonra sayısı en büyük olan hücreye ateş eder; birkaç hücre berabere kalırsa aralarından rastgele birini seçer.

Konumları saymak

Şimdiye kadar görülenlerle çelişmeyen bir konuma tutarlı diyelim: Tahtanın içinde duruyor; ne bir ıskanın ne de batmış bir geminin hücrelerinin üzerinden geçiyor. (Yalnızca isabetlerden oluşan bir konum da sayılmaz, çünkü bütün hücreleri vurulmuş bir gemi çoktan batmış olurdu.) Henüz ateş edilmemiş bir hücrenin yoğunluğuna kısaca $d$ diyeceğiz. Ortada isabet yokken tanımı çok basit: $d$, su üstündeki bütün gemilerin o hücreden geçen tutarlı konumlarının sayısı. İsabetler işin içine girince konumlara puan vereceğiz; ona birazdan geleceğiz.

• DüşükYüksek
• En yüksek yoğunluk

Bu iki sayıyı kendimiz de bulabiliriz. Bir köşe hücresinden her geminin tek bir yatay ve tek bir dikey konumu geçer: bir ucu o köşede duranlar. Beş gemi için $5 \cdot 2 = 10$. Ortadaki dört hücrenin her birinden ise $L$ boyundaki bir gemi $L$ yatay ve $L$ dikey konumla geçebilir, çünkü o hücre geminin birinci, ikinci, … ya da sonuncu hücresi olabilir. Beş gemi için bu $2 \cdot (5 + 4 + 3 + 3 + 2) = 2 \cdot 17 = 34$ eder. Hiçbir hücre bundan fazlasını toplayamaz; kruvazörde gördüğümüz gibi, kenara yaklaştıkça sayı düşer.

Yöntemin adı da buradan geliyor: Bir hücrenin sayısını toplam konum sayısına (760) bölerseniz, bütün konumlar arasından rastgele seçilen birinin o hücreden geçme olasılığını bulursunuz.

Iskalar konumları eler ve yoğunluk onların çevresinde düşer:

• Iska, sıra numarasıyla
• DüşükYüksek
• En yüksek yoğunluk

Bir ıska, üzerinden geçen bütün konumları siler; en çok da komşularının sayısını düşürür. Bir sonraki tepe bu yüzden genellikle biraz ötede çıkar. Yoğunluk, dama tahtası fikrini kimse söylemeden kendi kendine buluyor. Hatta daha fazlasını biliyor: kenarlarda avlanmanın pek verimli olmadığını ve bir yönde dar kalan bir boşluğa gemilerin ancak öbür yönde sığabileceğini.

İsabetlere ağırlık vermek

Şimdi bilgisayarın E5’i vurduğunu düşünelim. Her konum 1 sayılsaydı hiçbir şey değişmezdi: E5’ten geçen konumlar hâlâ mümkün, tıpkı önceden olduğu gibi; bütün hücreler eski sayılarını korurdu. Oysa isabet, bilgisayarın elindeki en değerli bilgi ve düz bir sayım onu göremiyor. Ağırlık tam bunun için var.

Kural şu: Hiçbir açık isabete değmeyen bir konum 1 puan, tek bir açık isabetin üzerinden geçen bir konum 35 puan sayılır. İki açık isabetin üzerinden birden geçen bir konum 35 · 35 puan sayılır; böyle devam eder. Bir hücrenin yoğunluğu, o hücreden geçen tutarlı konumların puanlarının toplamı. Bu 35 sayısına $w$ diyelim. $w$, su üstündeki gemilerin boylarından hesaplanıyor: boyların toplamının iki katının bir fazlası. Tam filoda 1 + 2 · 17 = 35.

Neden bu sayı? Az önce saydığımız gibi, tam filoda hiçbir hücrenin üzerinden 34 konumdan fazlası geçmez; $w$ ise bundan tam bir fazla. Yani 1 puanlık sıradan konumlar bir hücrede ne kadar birikirse biriksin, tek bir isabet konumunun puanına yetişemez. Gemiler battıkça hem bu üst sınır hem $w$ küçülür, ama $w$ hep sınırın bir fazlası kalır.

Bu, okulda öğrendiğimiz basamaklara çok benzer. Onluk sistemde bir basamağa en fazla 9 yazılır, bu yüzden birler basamağı hiçbir zaman tek bir onluğa yetişemez. 472 ile 469’u karşılaştırırken de önce yüzlere, sonra onlara bakarız; birlere sıra ancak onlar da eşitse gelir. Yoğunlukta da aynısı oluyor; yalnız taban 10 değil, $w$:

Burada $w^2$, $w \cdot w$ demek. $N_0$, hücreden geçen ve hiçbir açık isabete değmeyen konumların sayısı; $N_1$ yalnızca bir açık isabetin üzerinden geçenlerin, $N_2$ iki açık isabetin üzerinden birden geçenlerin sayısı; sondaki üç nokta da “böyle devam eder” demek. Bir hücreden toplamda en fazla $w - 1$ konum geçtiği için bu sayıların her biri 0 ile $w - 1$ arasında kalır; yani bunlar $d$ sayısının $w$ tabanındaki basamakları, tıpkı $472 = 2 + 7 \cdot 10 + 4 \cdot 10^2$ gibi. İki hücreyi karşılaştırmak da iki sayıyı karşılaştırmak gibi en yüksek basamaktan başlar. Bilgisayar önce şuna bakar: Bu hücreden geçen bir konum en fazla kaç açık isabete değebiliyor? Konumların sayısı ancak bu soruda berabere kalan hücreler arasında karar verir.

Tek isabet

F5 ve E6: 12 · 35 + 22 = 442

Aynı hizada iki isabet

D5 ve G5: 7 · 35² + 5 · 35 + 21 = 8.771

• İsabet
• DüşükYüksek
• En yüksek yoğunluk

E5’teki tek isabetten sonra tepe F5 ve E6 hücrelerinde: 12 · 35 + 22 = 442. Bunu şöyle okuyun: Bu hücrelerin her birinden geçen konumların 12 tanesi E5’in de üzerinden geçiyor ve her biri 35 puan getiriyor; 22 tanesi geçmiyor ve her biri 1 puan getiriyor. E5’in öbür komşuları E4 ve D5 biraz geride, 441 puanda: E5 tam ortada durmuyor; üstünde ve solunda biraz daha az yer var. İkinci isabetten sonra, iki isabetin üzerinden birden geçen konumlar yalnızca çizgiyi sürdüren hücrelerden geçebiliyor; bu yüzden o hücrelerin en yüksek basamağı $w^2$ basamağına çıkıyor. Tepe artık çizginin iki ucunda, D5 ve G5 hücrelerinde: 7 · 35² + 5 · 35 + 21 = 8.771.

Zor seviyeye çizgiyi uzatma kuralını kimse yazmadı; kural aritmetiğin içinden kendiliğinden çıkıyor. Yukarıdaki durum makinesinin büyük kısmı da öyle: En büyük yoğunluğun en yüksek basamağı, durumun yerini tutuyor. Bu basamak birler basamağıysa bilgisayar avlanıyor, $w$ basamağıysa hedefliyor, $w^2$ ya da daha yukarısıysa bir isabet dizisi boyunca ilerliyor. İki isabetin arasında kalan, henüz ateş edilmemiş tek bir hücreye, örneğin E5 ile G5 arasındaki F5’e, doğrudan yöneliyor bile; Normal seviye içinse o hücre komşulardan yalnızca biri. Bir gemi batınca o geminin isabetleri kapanır, $w$ küçülür ve basamaklar kendiliğinden yeniden düzenlenir.

Kendiniz deneyin

Aşağıdaki laboratuvar, oyunun yoğunluk hesabını tarayıcınızda çalıştırıyor. Iskaları ve isabetleri işaretleyin, tepenin nasıl yer değiştirdiğini izleyin. Kafanızdaki oyunda bir gemi batınca hücrelerini “Battı” olarak işaretleyin ve gemiyi listeden kaldırın: $w$ küçülür, yoğunluk da kalan gemilere göre yeniden dağılır.

İşaretleme aracı

IskaİsabetBattıSil

ABCDEFGHIJ

12345678910

İşaretlemek için bir hücreye tıklayın ya da dokunun; klavyede ok tuşlarıyla gezinip Enter ya da Boşluk tuşuna basın. Bir hücreyi aynı araçla yeniden işaretlerseniz işaret kalkar. Bir gemi batınca hücrelerini “Battı” olarak işaretleyin ve gemiyi listeden kaldırın.

Su üstündeki gemiler

• Uçak gemisi5, 5 hücre
• Zırhlı4, 4 hücre
• Kruvazör3, 3 hücre
• Denizaltı3, 3 hücre
• Muhrip2, 2 hücre

Zor seviyenin hedefi

E5, F5, E6 ve F6 · d = 34

Hücre

A1 · d = 10

Bir isabetin ağırlığı

w = 35

Tahtayı sıfırla

Denemeye değer iki şey var. İki isabeti yan yana koyun ve tepenin çizginin iki ucuna sıçramasını izleyin; sonra uçlardan birine bir ıska ekleyin. Ya da tahtayı boş bırakıp uçak gemisi dışındaki bütün gemileri listeden kaldırın: Yalnızca uzun bir gemi kalınca yoğunluğun kenarlardan ne kadar kaçtığına bakın.

Sayımın atladıkları

Yoğunluk her gemiyi tek başına düşünür; bu yüzden hiçbir filoda bir arada olamayacak konumları da sayar, örneğin aynı hücrelerde duran bir uçak gemisiyle bir zırhlıyı. Kesin yanıt için, şimdiye kadarki atışlarla çelişmeyen her filoyu tek tek tartmak gerekirdi; ilk atıştan önce bunlar 30.093.975.536 tane. Üstelik bu bile ancak rakip gemilerini tamamen rastgele yerleştiriyorsa doğru olurdu. Bundan sonraki doğal adım, tutarlı filolar arasından rastgele örnekler seçmek olurdu. Gemi başına sayım ise ucuz, anlaşılır ve bir sonraki bölümün gösterdiği gibi şimdiden işe yarıyor. (Bilgisayarın nasıl düşündüğünü bilen biri, gemilerini yoğunluğun en son taradığı kenarlara saklayabilir.)

Kaç atış?

Stratejileri karşılaştırmak için her birine aynı 1.000 filoyu batırttım; filoları oyunun kendisi rastgele yerleştirdi. Oyunlar numaralı ve her biri birebir yeniden oynatılabiliyor, çünkü hem filonun yerleşimi hem de bilgisayarın rastgele seçimleri oyunun numarasına bağlı. Yukarıda adım adım izlediğiniz 743 numaralı oyun da bunlardan biri. Aşağıdaki tabloda üç seviyenin yanında dördüncü bir strateji daha var: desensiz av ve hedef. Bu, tarama deseni kapatılmış Normal seviye: Rastgele avlanıyor, Normal seviye gibi hedefliyor.

Tüm filoyu batırmak için gereken atış sayısı; strateji başına 1.000 oyun

Strateji	Ortalama	Medyan	Ortadaki %80	En iyi	En kötü
Rastgele (Kolay)	95,4	97	89–100	63	100
Desensiz av ve hedef	60,3	60	42–80	22	100
Av ve hedef (Normal)	50,5	51	38–62	24	74
Olasılık yoğunluğu (Zor)	44,4	43	33–57	22	71

Tablodaki “Ortadaki %80” sütunu, en hızlı %10 ve en yavaş %10 oyun dışarıda bırakılınca geriye kalan aralığı gösteriyor.

• Olasılık yoğunluğu (Zor)
• Av ve hedef (Normal)
• Desensiz av ve hedef
• Rastgele (Kolay)
• Rastgele atış, kesin hesap

En büyük sıçrama hedeflemeden geliyor: Kolay seviyenin ortalama 95,4 atışından (tıpkı formülün söylediği gibi) desensiz av ve hedefin 60,3 atışına. Tarama deseni 9,8 atış daha kazandırıyor, yoğunluk da 6,1 atış. Zor seviye oyunlarının %76 kadarını 50 atış içinde bitiriyor, Normal seviye %47 kadarını; Zor seviyenin hiçbir oyunu 71 atıştan uzun sürmedi. Bu ortalamalar da biraz şansa bağlı: Her biri, sayısız oyun oynasaydık bulacağımız ortalamadan büyük olasılıkla en fazla 0,9 atış uzakta. Stratejiler arasındaki farklar bundan çok daha büyük, yani sıralama şans eseri değil.

Üç fikir

Ayrıntıları bir kenara bırakınca geriye, her biri bir öncekinden daha genel üç fikir kalıyor. Bir isabet komşuları hakkında bilgi taşır, öyleyse peşine düşün: Hedef modu budur. Aynı gemiye denk gelebilecek yan yana iki atış israftır, öyleyse atışlarınızı hiçbir geminin kaçamayacağı bir desene yayın: Parite budur. Bu kuralları tek tek yazmak yerine hâlâ mümkün olan her şeyi sayın ve kararı ağırlıklara bırakın: Olasılık yoğunluğu da budur; önceki iki kural onun içinden kendiliğinden çıkar.

Üç seviyeyi de Amiral Battı oyununda deneyebilirsiniz. Zor seviyede savaş sürerken ısı haritasını açın ve bilgisayar yaklaştıkça $d$ değerinin kendi filonuzun üzerinde nasıl yayıldığını izleyin. Bir dahaki Amiral Battı oyununuzda belki siz de dama tahtasını hatırlarsınız.

Okuma önerileri

• DataGenetics, “Battleship” (2011, İngilizce): rastgele atışı, av ve hedefi, pariteyi ve olasılık yoğunluğunu karşılaştıran klasik bir yazı; çok daha fazla grafik içeriyor.