Pengantar Algoritma Minimax dengan Implementasi Java

1. Ikhtisar

Pada artikel ini, kita akan membahas algoritma Minimax dan aplikasinya di AI. Karena ini adalah algoritme teori permainan, kami akan menerapkan permainan sederhana menggunakannya.

Kami juga akan membahas keuntungan menggunakan algoritme dan melihat bagaimana hal itu dapat ditingkatkan.

2. Pendahuluan

Minimax adalah algoritma pengambilan keputusan, biasanya digunakan dalam permainan dua pemain berbasis giliran . Tujuan dari algoritma ini adalah untuk menemukan langkah selanjutnya yang optimal.

Dalam algoritme, satu pemain disebut maximizer, dan pemain lainnya disebut minimizer. Jika kita memberikan skor evaluasi ke papan permainan, satu pemain mencoba memilih keadaan permainan dengan skor maksimum, sementara yang lain memilih negara dengan skor minimum.

Dengan kata lain, para maximizer bekerja untuk mendapatkan skor tertinggi, sementara mencoba minimizer nilai terendah dengan mencoba bergerak kontra .

Ini didasarkan pada konsep permainan zero-sum. Dalam permainan zero-sum, total skor utilitas dibagi di antara para pemain. Peningkatan skor satu pemain menyebabkan penurunan skor pemain lain. Jadi, skor total selalu nol. Agar satu pemain menang, yang lain harus kalah. Contoh dari permainan tersebut adalah catur, poker, checker, tic-tac-toe.

Fakta menarik - pada tahun 1997, komputer bermain catur IBM Deep Blue (dibangun dengan Minimax) mengalahkan Garry Kasparov (juara dunia dalam catur).

3. Algoritma Minimax

Tujuan kami adalah menemukan langkah terbaik untuk pemain. Untuk melakukannya, kita tinggal memilih node dengan skor evaluasi terbaik. Untuk membuat prosesnya lebih cerdas, kami juga dapat melihat ke depan dan mengevaluasi gerakan lawan potensial.

Untuk setiap gerakan, kami dapat melihat ke depan sebanyak mungkin gerakan yang dimungkinkan oleh daya komputasi kami. Algoritme mengasumsikan bahwa lawan bermain dengan optimal.

Secara teknis, kita mulai dengan simpul akar dan memilih simpul terbaik. Kami mengevaluasi node berdasarkan skor evaluasinya. Dalam kasus kami, fungsi evaluasi dapat memberikan skor hanya ke node hasil (daun). Oleh karena itu, kami secara rekursif menjangkau daun dengan skor dan kembali menyebarkan skor.

Pertimbangkan pohon permainan di bawah ini:

Maximizer dimulai dengan simpul akar dan memilih langkah dengan skor maksimum. Sayangnya, hanya daun yang memiliki skor evaluasi, dan karenanya algoritme harus mencapai simpul daun secara rekursif. Pada pohon permainan yang diberikan, saat ini giliran minimizer untuk memilih perpindahan dari simpul daun , sehingga simpul dengan skor minimum (disini, simpul 3 dan 4) akan dipilih. Itu terus memilih node terbaik dengan cara yang sama, sampai mencapai node root.

Sekarang, mari kita tentukan secara formal langkah-langkah algoritma:

  1. Bangun pohon permainan lengkap
  2. Evaluasi skor untuk cuti menggunakan fungsi evaluasi
  3. Skor cadangan dari daun ke akar, dengan mempertimbangkan jenis pemain:
    • Untuk pemain maksimal, pilih anak dengan skor maksimal
    • Untuk pemain min, pilih anak dengan skor minimum
  4. Pada node root, pilih node dengan nilai maksimal dan lakukan langkah yang sesuai

4. Implementasi

Sekarang, mari kita terapkan game.

Dalam permainan, kami memiliki tumpukan dengan n jumlah tulang . Kedua pemain harus mengambil 1,2 atau 3 tulang pada gilirannya. Seorang pemain yang tidak bisa mengambil tulang kalah dalam permainan. Setiap pemain bermain dengan maksimal. Diberikan nilai n , mari kita tulis AI.

Untuk menentukan aturan permainan, kami akan mengimplementasikan kelas GameOfBones :

class GameOfBones { static List getPossibleStates(int noOfBonesInHeap) { return IntStream.rangeClosed(1, 3).boxed() .map(i -> noOfBonesInHeap - i) .filter(newHeapCount -> newHeapCount >= 0) .collect(Collectors.toList()); } }

Selain itu, kami juga membutuhkan implementasi untuk kelas Node dan Tree juga:

public class Node { int noOfBones; boolean isMaxPlayer; int score; List children; // setters and getters } public class Tree { Node root; // setters and getters }

Sekarang kami akan menerapkan algoritme. Dibutuhkan pohon permainan untuk melihat ke depan dan menemukan langkah terbaik. Mari terapkan itu:

public class MiniMax { Tree tree; public void constructTree(int noOfBones) { tree = new Tree(); Node root = new Node(noOfBones, true); tree.setRoot(root); constructTree(root); } private void constructTree(Node parentNode) { List listofPossibleHeaps = GameOfBones.getPossibleStates(parentNode.getNoOfBones()); boolean isChildMaxPlayer = !parentNode.isMaxPlayer(); listofPossibleHeaps.forEach(n -> { Node newNode = new Node(n, isChildMaxPlayer); parentNode.addChild(newNode); if (newNode.getNoOfBones() > 0) { constructTree(newNode); } }); } }

Sekarang, kami akan menerapkan metode checkWin yang akan mensimulasikan permainan, dengan memilih gerakan optimal untuk kedua pemain. Ini menetapkan skor menjadi:

  • +1, jika pemaksimal menang
  • -1, jika minimizer menang

The checkWin akan mengembalikan true jika pemain pertama (dalam kasus kami - maximizer) menang:

public boolean checkWin() { Node root = tree.getRoot(); checkWin(root); return root.getScore() == 1; } private void checkWin(Node node) { List children = node.getChildren(); boolean isMaxPlayer = node.isMaxPlayer(); children.forEach(child -> { if (child.getNoOfBones() == 0) { child.setScore(isMaxPlayer ? 1 : -1); } else { checkWin(child); } }); Node bestChild = findBestChild(isMaxPlayer, children); node.setScore(bestChild.getScore()); }

Di sini, metode findBestChild menemukan node dengan skor maksimum jika seorang pemain adalah pemaksimal. Jika tidak, ia mengembalikan anak dengan skor minimum:

private Node findBestChild(boolean isMaxPlayer, List children) { Comparator byScoreComparator = Comparator.comparing(Node::getScore); return children.stream() .max(isMaxPlayer ? byScoreComparator : byScoreComparator.reversed()) .orElseThrow(NoSuchElementException::new); }

Terakhir, mari kita implementasikan kasus uji dengan beberapa nilai n (jumlah tulang dalam tumpukan):

@Test public void givenMiniMax_whenCheckWin_thenComputeOptimal() { miniMax.constructTree(6); boolean result = miniMax.checkWin(); assertTrue(result); miniMax.constructTree(8); result = miniMax.checkWin(); assertFalse(result); }

5. Perbaikan

Untuk sebagian besar masalah, tidak mungkin membangun pohon permainan secara keseluruhan. Dalam praktiknya, kita dapat mengembangkan pohon parsial (membangun pohon hingga jumlah level yang telah ditentukan saja) .

Kemudian, kita harus menerapkan fungsi evaluasi, yang harus dapat memutuskan seberapa baik keadaan saat ini, untuk pemain.

Bahkan jika kita tidak membangun pohon permainan yang lengkap, akan memakan waktu untuk menghitung gerakan untuk permainan dengan faktor percabangan yang tinggi.

Untungnya, ada opsi untuk menemukan gerakan optimal, tanpa menjelajahi setiap node pohon permainan. Kita bisa melewati beberapa cabang dengan mengikuti beberapa aturan, dan itu tidak akan mempengaruhi hasil akhir. Proses ini disebut pemangkasan . Pemangkasan alfa-beta adalah varian umum dari algoritma minimax.

6. Kesimpulan

Algoritma minimax adalah salah satu algoritma paling populer untuk permainan papan komputer. Ini banyak diterapkan dalam game berbasis giliran. Ini bisa menjadi pilihan yang baik ketika pemain memiliki informasi lengkap tentang game tersebut.

Ini mungkin bukan pilihan terbaik untuk game dengan faktor percabangan yang sangat tinggi (misalnya game GO). Meskipun demikian, dengan penerapan yang tepat, ini bisa menjadi AI yang cukup cerdas.

Seperti biasa, kode lengkap untuk algoritme dapat ditemukan di GitHub.