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()
