Arama algoritmaları | Minimax Ve Binary Search Algoritmaları

Nonantiy

Moderatör
28 Haz 2020
1,066
236
Kayseri
Merhabalar, iyi günler Türk Hack Team ailesi.
Bu gün sizlerle Arama algoritmalarına bakıcağız.


algoritma-ne-demek.jpg


Bilgisayar bilimlerinde, çeşitli data structures Türkçesi veri yapıları üzerinde bir bilginin arandığı zaman kullanılan algoritma. Örnek olarak bir dizide bir verinin aranması. Veya bir text dosyasında bir kelimenin bulunması bunlara örnek gösterilebillnir. Yapılarına göre bu algoritmaları gruplandırmamız gerekirse iki grupta hemen hemen hepsini toparlıyabilliriz.
Uninformed Search
İnformed Search
Uninformed Search:Verilen probleme algoritmanın özgü kolaylıkların barındırmaması denir.
İnformed Search:Verilen probleme algoritmanın özgü kolaylıkların barındırması denir.

Uninformed'e örnek vermemiz gerekirse diziler üzerinde çalışan arama algoritmalarından olan ikili arama algoritmasını gösterebillirim.


Binary Search Algorithm

Bir veri yapısı üzerinde problemi her adımda iki parçaya bölerek yapılan arama algoritmasının ismidir. Bu algoritma söyle çalışır her bir aşamada aranan değerin dizin orta değerine eşit olup olmadığı kontrol edilir. Eşit ise işlem olumlu bir şekilde doğrulanır. Eğer eşit değilse aranan değer orta değerin orta değer'inde ikiye ayrılarak hangi kısımda olduğu kontrol edilir. Aranan değerin bulunduğu değer bu işlemden sonra ki işlemde aranacak dizi olur bu şekilde gereksiz eleman sayısından kurtulur. Yapılacak işlemi hemen hemen yarıya indirmiş olur. Bunu C# koduna dökücek olursak.
Screenshot_2021-08-20_02-04-02.png

Yukarıdaki kod buna örnek olabillir. Birde manuel olarak bir dizide ortak değeri bulalım.

1, 4, 8, 22, 10, 30, 43, 50, 81
simdi aranan 43 olsun bunu nasıl buluruz hemen bakalım. Bu dizinin ortancı elemanı 10'dur.

1, 4, 8, 22, 10, 30, 43, 50, 81

Burada sormamız gereken soru 10 43'e eşit mi? Bunun cevabı hayır. Ozaman 10 43'ten büyük mü? Bu sorunun cevabıda hayır. Son olarak 43 10'dan büyük müdür olucak. Bunun cevabı evet. Olduğundan dolayı sol tarafı eliyoruz. İkili arama algoritmasının mantığı parçala ve buldur. O yüzden bu diziyi ikiye parçaladık.

30, 43, 50, 81

Yukarıdaki dizin ortakcı elemanı 43'tür.
30, 43, 50, 81

43 aranan sayıya eşitmidir bunun cevabı evet. İşlem tamamlandı.

algotithm-768x416.jpg


Simdi ise İnformed Search grup'undan Minimax algoritmasına bakalım.

Minimax Algorithm


Minimax algoritması yapay zekanın karşısındaki oyuncunun mantıklı ve kazanmaya oynadığını varsayarak en iyi şekilde oynadığı olasılığı alır. Yapay zekanın oyunu kazanmasının en olası olduğu durumu seçer. Santraç ve Tic Tac Toe gibi birçok oyunda kullanılabillinir. Bu tip oyunlara mükemmel bilgi oyunlarıda denir çünkü bütün olasılıklar belliridr. Tabikide bu algoritma 2 oyuncu tarafından karşılıklı oynanan ve hangi hamleyi yapacağı belli olmayan oyunlarda kullanılamaz. Diğer oyuncuya maksimum zarara sahip olan hamleyi seçip kendisinin kaybını en aza indirmeye çalışır minimax.

Bir oyunca MIN ve MAX adında iki tane oyuncu var diyelim. MAX oyuncusu olabilecek en yükse puanı almaya çalışır. MIN ise olabileceği en düşük puan'ı almaya çalışır. Minimax'ın genel mantığı ortalama bu şekildedir diyebillirim. Tabiki'de burada bilmemiz gereken bazı terminolojiler bulunmakta. Bunlara bakalım.

Oyun Ağacı:Oyunun bulunduğu durumdan sonraki adıma geçmenize yarıyan tüm olasılıklara sahip bir ağaç şekilidir.

İlk durum: Oyunun pozisyonun ve haraket hakkının kimde olduğunu gösterir.

Halef işlevi: Bir oyuncunun yapabileceği kural içi haraketlerinin tamamı.

Terminal durumu: Oyun bittiğinde oyunun durumu.

alphabeta.jpg

Örnek olarak yukarıdaki sekile baktığımızda kazanma olaşılığımızın ilk duruma göre en yüksek olduğu olasılık en soldaki 3 üncü kutucuğa hamle yapmamız. Ardından 2 tane olasılık kalıyor ya kazanıcağız yada kaybediceğiz. Ayrıca -1 kaybetmek 0 berabere kalmak +1 kazanmak olarak gösterilir. Terminal durumlarına baktığımızda yüksek ihtimalle yenilmeyeceğimizi görmekteyiz. Uzun lafın kısası yukarıdaki gibi bir durum ile karşılasırsak yapay zekanın yapacağı hamlede yukarıdaki algoritmaya göre değisir. Eğer yapak zeka oyunu kazanmak istiyorsa +1 durumdaki hamleleri oynar.
 
Üst

Turkhackteam.org internet sitesi 5651 sayılı kanun’un 2. maddesinin 1. fıkrasının m) bendi ile aynı kanunun 5. maddesi kapsamında "Yer Sağlayıcı" konumundadır. İçerikler ön onay olmaksızın tamamen kullanıcılar tarafından oluşturulmaktadır. Turkhackteam.org; Yer sağlayıcı olarak, kullanıcılar tarafından oluşturulan içeriği ya da hukuka aykırı paylaşımı kontrol etmekle ya da araştırmakla yükümlü değildir. Türkhackteam saldırı timleri Türk sitelerine hiçbir zararlı faaliyette bulunmaz. Türkhackteam üyelerinin yaptığı bireysel hack faaliyetlerinden Türkhackteam sorumlu değildir. Sitelerinize Türkhackteam ismi kullanılarak hack faaliyetinde bulunulursa, site-sunucu erişim loglarından bu faaliyeti gerçekleştiren ip adresini tespit edip diğer kanıtlarla birlikte savcılığa suç duyurusunda bulununuz.