Dalam konteks teori permainan kombinatorial, game tree atau pohon permainan merupakan sebuah grafik yang merepresentasikan seluruh kemungkinan status permainan dalam permainan sekuensial yang memiliki informasi sempurna. Permainan semacam ini mencakup catur, dam, Go, hingga permainan tic-tac-toe.
Related Stories
Suka dengan Artikel Ini?
Dapatkan lebih banyak cerita menarik dengan berlangganan newsletter kami. Gratis!
Subscribe →Struktur ini berfungsi untuk mengukur tingkat kompleksitas suatu permainan dengan cara memetakan berbagai skenario arah jalannya pertandingan. Untuk permainan kompleks seperti catur, algoritma komputer umumnya menggunakan sebagian kecil dari pohon permainan atau partial game trees agar proses komputasi dapat berjalan efisien.
Dalam penerapannya di bidang kecerdasan buatan, game tree memegang peranan krusial untuk menentukan langkah terbaik melalui berbagai algoritma pencarian pohon. Kombinasi aturan minimax serta teknik pemangkasan memungkinkan sistem komputer menganalisis langkah secara optimal dalam keterbatasan waktu.
Penyelesaian suatu permainan secara utuh menggunakan game tree dapat dilakukan apabila seluruh cabang permainan berhasil dipetakan menggunakan algoritma deterministik seperti backward induction. Meski demikian, dalam banyak kasus, penggunaan sebagian kecil dari pohon tersebut sudah cukup untuk menentukan strategi terbaik.