Pohon Permainan (Game Tree)

2.1     Pohon Permainan

Pohon permainan merepresentasikan kepada penulis kondisi-kondisi yang mungkin penulis hadapi pada permainan dimulai dari kondisi yang sedang penulis hadapi sekarang hingga beberapa kondisi ke depan. Sebuah pohon permainan merupakan representasi grafis dari contoh permainan. Pohon permainan menyediakan informasi akan pemain, hasil, strategi, dan pilihan langkah. Pohon permainan dapat direpresentasikan dengan baik pada permainan yang berbasis giliran (turn-based game). Pohon permainan memiliki root yang merupakan representasi dari kondisi dimana langkah belum diambil, nodes pada pohon yang merepresentasikan keadaan-keadaan yang mungkin diambil pada permainan, dan arcs yang merepresentasikan langkah.

Penggunaan pohon permainan pada permainan yang dimainkan oleh dua pemain direpresentasikan dengan cara bergantian. Untuk edges dari tingkat pertama ke tingkat kedua merepresentasikan langkah-langkah yang dapat diambil oleh pemain pertama, sedangkan untuk edges dari tingkat kedua ke tingkat ketiga merepresentasikan langkah-langkah yang dapat diambil oleh pemain kedua, dan begitu seterusnya. Leaf nodes pada pohon permainan merepresentasikan keadaan akhir pada permainan, dimana permainan tersebut dimenangkan, dikalahkan ataupun seri. Pada permainan yang sederhana, untuk mencapai leaf nodes mungkin dapat direpresentasikan, tetapi untuk permainan yang rumit seperti Checker, pencapaian leaf nodes sangat tidak dimungkinkan karena percabangan pada pohon permainan yang sangat besar. 

Gambar. Contoh pohon permainan game tic-tac-toe

(Ben Coppin, 2004)

Berikut adalah penjelasan pohon permainan game tic-tac-toe pada Gambar:

1.       Terdapat root yang merupakan keadaan awal dimana permainan belum dimulai dan langkah belum diambil.

2.       Edges yang menghubungkan tingkat pertama (root) dengan tingkat kedua merupakan langkah pemain pertama dan begitu seterusnya. Sehingga pohon permainan tersebut merepresentasikan langkah kedua pemain secara bergantian.

3.       Untuk nodes pada pohon tersebut merepresentasikan keadaan-keadaan yang dapat diambil oleh pemain yang akan melangkah.

4.       Percabangan pertama yang dihasilkan adalah 9, kemudian untuk percabangan berikutnya adalah 8, tingkat percabangan berikutnya adalah 7, dan begitu seterusnya hingga mencapai keadaan akhir (leaf nodes).