Tic Tac Toe Oyunu - Yapay Zeka - MiniMax Algo.

Yapay zeka konusuna ilk girişi klasik Minimax algoritmasıyla yapıyorum. Algoritma çok basit ve etkili bir yöntem kullanmaktadır. Oyuncu bir hamle yaptıktan sonra diğer tüm oyunları oynayarak bilgisayarın en az kaybettiği en çok kazandığı hamle tespit edilmiş olur. Uygulamayı Python dilinde gerçeklemeye çalıştım. Doğası itibariyle %100 nesne yönelimli programlandı. Görsel arayüz için OpenGL (pyOpenGL) ve GLUT kütüphanelerini kullandım. Algoritma için daha detaylı bilgiyi http://en.wikipedia.org/wiki/Minimax adresinden edinebilirsiniz. İsterseniz programa ve kodların açıklamasına şöyle bir göz atalım, ardından kaynak kodu vereyim.

# -*- coding: cp1254 -*-


"""
MiniMax algoritmasını kullanarak Tic Tac Toe oyununun gerçeklenmesi

Sakarya Üniversitesi Bilgisayar Mühendisliği Bölümü
Yapay Zeka Dersi Ödevi

Ramazan Bellek - Ekim 2010


"""


from OpenGL.GL import *
from OpenGL.GLUT import *
from OpenGL.GLU import *
import time
import math
import copy
from Tkinter import *


# MiniMax algoritmasını gerçekleyen sınıf
class MiniMax:
    mevcutDurum = [[]]
    def __init__(self, mevcutDurum): # yapılandırıcı metod
        self.mevcutDurum = copy.deepcopy(mevcutDurum)

    # bilgisayarın bir sonraki yapacağı en mantıklı hareketi belirler
    def sonrakiHamleyiHesapla(self):
        tahta = self.mevcutDurum
        max = [[0 for satir in range(3)] for sutun in range(3)]
        for x in range(3):
            for y in range(3):
                if tahta[x][y] == 0:
                    tahta[x][y] = 1 # boş alana hamle yap
                    max[x][y] = self.__tara(tahta, 1) # alt ağaçları tara
                    tahta[x][y] = 0 # tarama bitince yapılan hamle geri alınır
                else:
                    max[x][y] = -99
        sonuc = -99
        donusDegeri = [0,0]
        for x in range(3):
            for y in range(3):
                if max[x][y]>sonuc:
                    sonuc=max[x][y]
                    donusDegeri = [x, y]
        return donusDegeri

    # alt oyun ağaçlarını tarar
    def __tara(self, t, s):
        tahta = copy.deepcopy(t)
        sonEl = copy.deepcopy(s)
        toplam = [[0 for satir in range(3)] for sutun in range(3)]
        for x in range(3):
            for y in range(3):
                if tahta[x][y] == 0:
                    tahta[x][y] = sonEl*-1
                    kontrolSonucu = Hakem.kontrolEt(tahta)
                    if kontrolSonucu != 5: # -> tahta henüz dolu değil!
                        return kontrolSonucu
                    toplam[x][y] = self.__tara(tahta, sonEl*-1)
                    tahta[x][y] = 0
        if sonEl == 1:
            return self.Min(toplam)
        else:
            return self.Max(toplam)

    # Katardaki azami değeri tespit eder.
    def Max(self, t):
        tahta = copy.deepcopy(t)
        deger = -99
        for x in range(3):
            for y in range(3):
                if tahta[x][y]>deger:
                    deger = tahta[x][y]
        return deger

    # Katardaki asgari değeri tespit eder.
    def Min(self, t):
        tahta = copy.deepcopy(t)
        deger = 99
        for x in range(3):
            for y in range(3):
                if tahta[x][y]                    deger = tahta[x][y]
        return deger
    
class Hakem:
    @staticmethod
    def bosMu(t):
        tahta = copy.deepcopy(t)
        for x in range(3):
            for y in range(3):
                if tahta[x][y] == 0:
                    return True
        return False
    @staticmethod
    def kontrolEt(t):
        tahta = copy.deepcopy(t)

        # oyuncu hamleleri --------------

        # yatay kontrol --
        if tahta[0][0] == tahta[1][0] == tahta[2][0] == -1:
            return -1
        elif tahta[0][1] == tahta[1][1] == tahta[2][1] == -1:
            return -1
        elif tahta[0][2] == tahta[1][2] == tahta[2][2] == -1:
            return -1
        # ----------------

        # dikey kontrol --
        elif tahta[0][0] == tahta[0][1] == tahta[0][2] == -1:
            return -1
        elif tahta[1][0] == tahta[1][1] == tahta[1][2] == -1:
            return -1
        elif tahta[2][0] == tahta[2][1] == tahta[2][2] == -1:
            return -1
        # ----------------

        # çapraz kontrol --
        elif tahta[0][0] == tahta[1][1] == tahta[2][2] == -1:
            return -1
        elif tahta[2][0] == tahta[1][1] == tahta[0][2] == -1:
            return -1
        # -----------------

        # ------------------------------------

        # Bilgisayar hamleleri --------------

        # yatay kontrol --
        if tahta[0][0] == tahta[1][0] == tahta[2][0] == 1:
            return 1
        elif tahta[0][1] == tahta[1][1] == tahta[2][1] == 1:
            return 1
        elif tahta[0][2] == tahta[1][2] == tahta[2][2] == 1:
            return 1
        # ----------------

        # dikey kontrol --
        elif tahta[0][0] == tahta[0][1] == tahta[0][2] == 1:
            return 1
        elif tahta[1][0] == tahta[1][1] == tahta[1][2] == 1:
            return 1
        elif tahta[2][0] == tahta[2][1] == tahta[2][2] == 1:
            return 1
        # ----------------

        # çapraz kontrol --
        elif tahta[0][0] == tahta[1][1] == tahta[2][2] == 1:
            return 1
        elif tahta[2][0] == tahta[1][1] == tahta[0][2] == 1:
            return 1
        # -----------------

        # ------------------------------------

        # Eşitlik durumu
        if Hakem.bosMu(tahta) == False:
            return 0
        return 5 # -> tahta henüz dolu değil!

class Tahta:
    """Oyun tahtası sınıfı"""
    tahta = [ [0 for satir in range(3)] for sutun in range(3)]
    siraBilgisayarda = False
    oyunBitti = False
    
    def __init__(self):
        oyunBitti = False
        self.ilkDefa = True

    def ciz(self):
        if self.oyunBitti == True:
            glColor(0.9, 0.6, 0.1)
            drawText("Oyun bitti... :|", 10 ,5 ,250, 250)
        elif self.ilkDefa == True:
            glColor(0.9, 0.6, 0.1)
            drawText("Oynamaya hazirim, lütfen bir hamle yapiniz... :)", 10 ,5 ,250, 250)
        else:
            glColor(0.9, 0.6, 0.1)
            drawText("Sizin siraniz ?", 10 ,5 ,250, 250)
            
        if self.ilkDefa == True:
            self.ilkDefa = False
        Tahta.cerceveCiz()
        self.__oyunCiz()
        

    @staticmethod
    def cerceveCiz():
        glLineWidth(2.5)
        glColor(0.0, 0.0, 1.0)
        glBegin(GL_LINES)
        
        # dış çerçeve ------------
        glVertex(-0.9, 0.9, 0.0)
        glVertex(0.9, 0.9, 0.0)
        glVertex(-0.9, 0.9, 0.0)
        glVertex(-0.9, -0.9, 0.0)
        glVertex(-0.9, -0.9, 0.0)
        glVertex(0.9, -0.9, 0.0)
        glVertex(0.9, -0.9, 0.0)
        glVertex(0.9, 0.9, 0.0)
        # -------------------------

        # ızgaralar ---------------
        glVertex(-0.3, -0.9, 0.0)
        glVertex(-0.3, 0.9, 0.0)
        glVertex(0.3, -0.9, 0.0)
        glVertex(0.3, 0.9, 0.0)
        glVertex(-0.9, -0.3, 0.0)
        glVertex(0.9, -0.3, 0.0)
        glVertex(-0.9, 0.3, 0.0)
        glVertex(0.9, 0.3, 0.0)
        # -------------------------
        glEnd()       

    def __xCiz(self, x, y):
        x =0.6*x-0.6
        y =-1*(0.6*y-0.6)
        glLineWidth(8.5)
        glColor(0.0, 1.0, 0.0)
        glBegin(GL_LINES)
        glVertex(x-0.175, y-0.175)
        glVertex(x+0.175, y+0.175)
        glVertex(x-0.175, y+0.175)
        glVertex(x+0.175, y-0.175)
        glEnd()

    def __oCiz(self, x, y):
        x =0.6*x-0.6
        y =-1*(0.6*y-0.6)
        glLineWidth(1.5)
        glColor(1.0, 0.0, 0.0)
        glPushMatrix()
        glTranslate(x, y, 0.0)
        glBegin(GL_LINES)
        for i in range(0, 1080):
            glVertex(math.sin(i)*0.2,math.cos(i)*0.2)
        glEnd()
        glPopMatrix()

    def __oyunCiz(self):
        for x in range(3):
            for y in range(3):
                if self.tahta[x][y] == -1:
                    self.__xCiz(x, y)
                elif self.tahta[x][y] == 1:
                    self.__oCiz(x, y)

    ''' tüm hamleler bu metod üzerinden gerçekleştirilir.
        kullanıcı girişleri bu metoda yönlendirilerek kullanıcının hamle yapması
        sağlanırken, her hamleden sonra öz yinelemeli olarak bilgisayar kendi hamlesini yapar.
        Yapacağı hamleyi MiniMax algoritmasınını kullanarak tespit etmeye çalışır.
    '''
    def oyna(self, x, y):
        try:
            if self.oyunBitti == True:
##                Mesaj.msj("Oyun bittiği için hamle yapamazsınız.","Üzgünüm... :(")
                return
            if x not in range(40, 760):
                return
            if y not in range(30, 560):
                return
            x = (x-40)/240
            y = (y-30)/176
            if self.tahta[x][y] == 0:
                if self.siraBilgisayarda:
                    self.siraBilgisayarda = ~self.siraBilgisayarda
                    self.tahta[x][y] = 1
                    self.ciz()
                    glFlush ()
                    glutSwapBuffers()
                    self.__kontrolEt()
                else:
                    self.siraBilgisayarda = ~self.siraBilgisayarda
                    self.tahta[x][y] = -1
                    self.ciz()
                    glFlush ()
                    glutSwapBuffers()
                    self.__kontrolEt()
                    if self.oyunBitti == True:
                        return
                    mm = MiniMax(self.tahta)
                    time.sleep(0.5)
                    xy = mm.sonrakiHamleyiHesapla()
                    self.oyna(xy[0]*240+40, xy[1]*176+30)
                    glutPostRedisplay()
        except:
            print "Beklenmeyen bir hata meydana geldi. Lütfen tekrar deneyiniz."
            raise
        
    def __kontrolEt(self):
        durum = Hakem.kontrolEt(self.tahta)
        if durum == 0:
            self.oyunBitti = True
            Mesaj.msj("Berabere bitti!", "Eşitlik durumu")
            glEnable(GL_LIGHTING)
            glutPostRedisplay()
            return

        # Bilgisayarın hamleleri --------------
        mesaj = "Bilgisayar kazandı! :/\nBiraz daha dikkatli olmalısınız..."
        if durum == 1:
            self.oyunBitti = True
            Mesaj.msj(mesaj, "Oyun bitti...")
            glEnable(GL_LIGHTING)
            glutPostRedisplay()
            return
        # ------------------------------------

        # oyuncu hamleleri --------------
        mesaj = "Tebrikler, siz kazandınız... :)"
        if durum == -1:
            self.oyunBitti = True
            Mesaj.msj(mesaj, "Oyun bitti...")
            glEnable(GL_LIGHTING)
            glutPostRedisplay()
            return
        # ------------------------------------
        if durum == 5: # -> tahta henüz dolu değil
            return

# Mesaj sınıfı ----
class Mesaj:
    root = None
    def __init__(self, root):
        self.root = root
    @staticmethod
    def msj(yazi, baslik):
        root = Tk()
        root.title(unicode(baslik, encoding="cp1254"))
        root.withdraw()
        mesaj = Mesaj(root)
        mesaj.top = Toplevel(root)
        Label(mesaj.top, text=unicode(yazi, encoding="cp1254")).pack()
        Button(mesaj.top, text="OK", command=mesaj.tamam).pack(pady=5)
        root.wait_window(mesaj.top) # pencere Tamam komutu verene kadar bekler.
        root.destroy()
    def tamam(self):
        self.top.destroy()
# -----------------

# Yazı yazma fonksiyonu (pyOpenGL - örneğinden alınmıştır!)
def drawText( value, x,y,  windowHeight, windowWidth, step = 18 ):
    value = unicode(value, encoding="cp1254")
    glMatrixMode(GL_PROJECTION);
    matrix = glGetDouble(GL_PROJECTION_MATRIX)
    glLoadIdentity();
    glOrtho(0.0, windowHeight or 32, 0.0, windowWidth or 32, -1.0, 1.0)
    glMatrixMode(GL_MODELVIEW);
    glPushMatrix();
    glLoadIdentity();
    glRasterPos2i(x, y);
    lines = 0
    for character in value:
        if character == '\n':
            glRasterPos2i(x, y-(lines*18))
        else:
            glutBitmapCharacter(GLUT_BITMAP_9_BY_15, ord(character));
    glPopMatrix();
    glMatrixMode(GL_PROJECTION);
    glLoadMatrixd(matrix)
    glMatrixMode(GL_MODELVIEW);
# --------------------------------
            
# uygulama giriş fonsiyonları ---------------

resX,resY = (800,600 ) # ekran çözünürlüğü
oyunTahtasi = Tahta() # tahta sınıfı

def goster( ): # openGL render fonksiyonu
    glutSetWindow(window);
    glClearColor (1.0, 1.0, 1.0, 1.0)
    glClear (GL_COLOR_BUFFER_BIT)
    oyunTahtasi.ciz()
    glFlush ()
    glutSwapBuffers()

def ayarla():
    ''' yumuşak çizim '''
    glShadeModel(GL_SMOOTH)
    glDisable(GL_LIGHTING)



def fare(button, state, x, y):
    if button == 0 and state == 1:
        oyunTahtasi.oyna(x, y)


if __name__ == "__main__":
    glutInit([])
    glutInitDisplayMode(GLUT_RGBA | GLUT_DOUBLE | GLUT_DEPTH)

    glutInitWindowSize(resX, resY) # pencere genişliği
    glutInitWindowPosition(0, 0)
    window = glutCreateWindow("Tic Tac Toe Oyunu / MiniMax Yapay Zeka Uygulaması - Ramazan Bellek | Ekim 2010")
    glutMouseFunc(fare)
    ayarla()

    
    glutDisplayFunc(goster)
    glutMainLoop()