POHON TREE GAME TIC-TAC

POHON TREE GAME TIC-TAC

 

Tic tac toe adalah salah satu game klasik yang hanya bisa dimainkan oleh dua orang pemain. Kedua orang pemain itu bergiliran mengisikan tanda yang berbeda (biasanya silang dan lingkaran)di dalam kotak sebesar 3 x 3. Pemain yang berhasil memposisikan tandanya secara horisontal, vertikal, atau diagonal sebagai baris yang penuh akan memenangkan pertandingan.

Contoh ilustrasinya sebagai berikut

 

 

Ilustrasi game diatas dimenangkan oleh pemainyang menggunakan tanda X.

 

 

 

 

 

Permainan di atas berakhir seri. Jika seorang pemain sadar bahwa dirinya tidak bisa menang maka hasil seri lah yang paling baik baginya. Karena itu strategi salah satu pemain di atas adalah berusaha bertahan (defense) dengan cara menghalangi pemain lainnya untuk membentuk sebuah garis lurus.

Mengapa tic tac toe

Kesederhanaan game ini membuatnya menjadi contoh yang ideal dan mudah dipahami untuk pembelajaran konsep Combinatorial game dan Artificial Intelligence (kecerdasan buatan) dengan permodelan pohon. Dengan bantuan kalkulasi program komputer secara langsung yang terimplementasi dalam program untuk permainan tic tac toe di dapat statistik sebagai berikut :

 

• Analisa terhadap 765 bentuk yang essensial
  
• 362.880 posisi akhir jika belum diperhitungkan menang atau kalahnya
  
• 26.380 posisi akhir jika diperhitungkan menang atau kalahnya (memperhitungkan bentuk simetri)
  
• 255,168 posisi jika tidak memperhitungkan bentuk simetri, dengan rincian (jika X jalan terlebih dahulu)
  
  • 131,184 game dimenangkan oleh X
    
  • 77,904 game dimenangkan oleh O
    
  • 46,080 game berakhir seri
    
  • 31.896 mungkinan jalannya suatu game.
    

    
     

 

Komputer Artificial Intelligence pertama untuk game ini adalah OXO atau Noughts and Crosses (dibuat tahun 1952) yang dibuat pada platform EDSAC dan berhasil menciptakan salah satu Artificial Intelligence yang mampu melawan manusia. Salah satu contoh Komputer permainan Tic Tac Toe adalah TinkerToy computer, yang dikembangkan oleh salah satu mahasiswa MIT. Komputer ini hanya memainkan Tic Tac Toe dan belum pernah kalah sekalipun. Saat ini mesin ini dipajang di Museum of Science, Boston.

 

Representasi pohon bagi Artificial Intelligence game ini

 

Kita dapat dapat merepresentasikan seluruh kemungkinan permainan

dengan graf berarah yang biasa di sebut game tree (berbentuk pohon n-ary).

Node dari pohon (tree) tersebut merepresentasikan keadaan game.

 

 

 

Strategi yang harus dirancang oleh algoritma game

 

Untuk menang atau mencegah kekalahan dalam game ini. Computer harus secara konsisten melakukan langkah-langkah sesuai prioritas dibawah ini dengan mendahulukan langkah dengan priooritas tertinggi.

 

1. menempurnakan 3 buah baris diagonal,vertikal, atau horizontal.

2. menahan lawan agar tidak membentuk tiga baris yang sempurna (horisontal,vertikal maupun diagonal)

3. menciptakan strategi dengan melakukan langkah yang membuat kita mempunyai

dua kemungkinan penyempurnaan baris. Beberapa pola tersebut antara lain:

 

 

 

 

 

 

 

4. Mencegah posisi lawan mempunyai pola yang bisa membuatnya menang (contoh:pola sebagaimana no.3 )

5. memperbesar kemungkinan kemenangan dengan membuat dua tanda yang berdampingan.

6. mencegah lawan membuat dua tanda yang berdampingan.

 

Agar berhasil computer harus melengkapi langkahnya tanpa mengorbankan prioritas yang lebih tinggi secara konsisten