BAB 6 - BOARD GAME dan ALGORITMA MINIMAX


PENGERTIAN BOARD GAME

Board game adalah permainan yang dimainkan oleh dua orang atau lebih, berupa papan permainan yang telah di desain sedemikian rupa sesuai jenis permainan, board game bisa menggunakan koin, dadu, pion, kartu atau semacamnya yang digunakan dengan cara tertentu, sesuai dengan peraturan tiap-tiap jenis board game. Contohnya adalah game canddyland, chess, monopoly, scrabble, dan lain sebgainya.


ALGORITMA MINIMAX               

Algoritma minimax merupakan basis dari semua permainan berbasis AI seperti permainan catur misalnya. AI permainan catur tentunya sudah sangat terkenal dimana AI tersebut bahkan dapat mengalahkan juara dunia sekalipun. Pada algoritma minimax, pengecekan akan seluruh kemungkinan yang ada sampai akhir permainan dilakukan. Pengecekan tersebut akan menghasilkan pohon permainan yang berisi semua kemungkinan tersebut. Tentunya dibutuhkan resource yang berskala besar untuk menangani komputasi pencarian pohon solusi tersebut berhubung kombinasi kemungkinan untuk sebuah permainan catur pada setiap geraknya sangat banyak sekali.

Keuntungan yang didapat dengan menggunakan algoritma minimax yaitu algoritma minimax mampu menganalisis segala kemungkinan posisi permainan untuk menghasilkan keputusan yang terbaik karena algoritma minimax ini bekerja secara rekursif dengan mencari langkah yang akan membuat lawan mengalami kerugian minimum. Semua strategi lawan akan dihitung dengan algoritma yang sama dan seterusnya. Ini berarti, pada langkah pertama komputer akan menganalisis seluruh pohon permainan. Dan untuk setiap langkahnya, komputer akan memilih langkah yang paling membuat lawan mendapatkan keuntungan minimum, dan yang paling membuat komputer itu sendiri mendapatkan keuntungan maksimum. Dalam penentuan keputusan tersebut dibutuhkan suatu nilai yang merepresentasikan kerugian atau keuntungan yang akan diperoleh jika langkah tersebut dipilih. Untuk itulah disini digunakan sebuah fungsi heurisitic untuk mengevaluasi nilai sebagai nilai yang merepresentasikan hasil permainan yang akan terjadi jika langkah tersebut dipilih. Biasanya pada permainan tic tac toe ini digunakan nilai 1,0,-1 untuk mewakilkan hasil akhir permainan berupa menang, seri, dan kalah. Dari nilai-nilai heuristic inilah komputer akan menentukan simpul mana dari pohon permainan yang akan dipilih, tentunya simpul yang akan dipilih tersebut adalah simpul dengan nilai heuristic yang akan menuntun permainan ke hasil akhir yang menguntungkan bagi komputer.            

Algoritma minimax merupakan algoritma yang diterapkan dalam game yang melibatkan dua pemain yang saling bergantian, seperti tic-tac-toe, chess, go, othello dan game yang menggunakan strategi atau logika lainnya (Wijaya, 2010). Persamaan antara semua game tersebut yaitu semua merupakan game logika dan game dengan informasi yang lengkap. Ini berarti bahwa game merupakan sekumpulan aturan main dan dasar pemikiran yang logis. Adanya aturan main dan dasar pemikiran yang logis tersebut, maka nantinya setiap pemain dapat mengetahui semua langkah yang mungkin dari pemain lawannya, sehingga pemain bisa tetap “memantau” kondisi permainan sewaktu game sedang berlangsung (Akbar, 2011).

Algoritma minimax merupakan salah satu algoritma yang sering digunakan untuk game kecerdasan buatan yang menggunakan teknik depth first search (DFS) dalam pencariannya pada pohon dengan kedalaman terbatas (Kusumadewi, 2003). Algoritma minimax digunakan untuk memilih langkah terbaik, dimana kedua pemain akan saling berusaha untuk  memenangkan permainan. Selain itu, algoritma minimax ini bekerja secara rekursif dengan mencari langkah yang akan membuat lawan mengalami kerugian minimum. Algoritma minimax mendeskripsikan kondisi apabila terdapat pemain yang mengalami keuntungan, pemain lain akan mengalami kerugian senilai dengan keuntungan yang diperoleh lawan dan sebaliknya.            

Algoritma minimax akan melakukan pengecekan pada seluruh kemungkinan yang ada, sehingga akan menghasilkan pohon permainan yang berisi semua kemungkinan permainan tersebut (Jannah, 2010). Dengan pohon permainan ini setiap pemain mengetahui langkah-langkah yang mungkin diberikan pada situasi permainan saat ini. Sehingga untuk setiap langkah dan semua langkah selanjutnya dapat diketahui. Dalam repersentasi pohon pada algoritma minimax, terdapat dua jenis simpul, yaitu simpul min dan simpul max. Max akan memilih langkah dengan nilai tertinggi dan min akan memilih langkah dengan nilai terendah (Kusumadewi, 2003). Dalam penentuan keputusan max/min tersebut dibutuhkan suatu nilai yang merepresentasikan kerugian atau keuntungan yang akan diperoleh jika langkah tersebut dipilih. Untuk itulah disini digunakan sebuah fungsi heuristik.

Table Transposition and Memory
Algoritma dapat menggunakan tabel transposisi untuk menghindari melakukan pekerjaan ekstra dalam mencari posisi board yang sama beberapa kali.
  •  Memori kerja posisi board sudah dikenal
  • Menggunakan fungsi hash khusus desiderata: sebarkan posisi-posisi yang mirip seluas mungkin melalui kisaran nilai hash nilai hash yang banyak berubah saat berpindah dari papan bergerak mengalami perubahan yang sangat sedikit.
  • Kunci zobrist adalah sekumpulan bit acak dari fixed-length pola yang tersimpan untuk setiap kemungkinan keadaan dari setiap lokasi yang mungkin ada pada board. Contoh: Catur memiliki 64 kotak, dan masing-masing persegi bisa kosong atau ada 1 dari 6 potongan berbeda di atasnya, masing-masing dua warna mungkin.Zobrist kunci harus seperti berikut : 64 2 (6 + 1) = 832 bit-string yang berbeda.
  • Kunci Zobrist perlu diinisialisasi dengan bit-string acak dengan ukuran yang sesuai.
  • Untuk setiap kotak yang tidak kosong, tombol Zobrist adalah mendongak dan XORed dengan jumlah hash yang berjalan.
  • Zobrist Key dapat diperbarui secara bertahan
  • Tabel hash menyimpan nilai yang terkait dengan posisi board • Gerakan terbaik dari posisi masing-masing board.
  • Kedalaman digunakan untuk menghitung nilai
  • Nilai yang akurat, atau kita dapat juga menyimpan nilai "fail-soft" yang dihasilkan darisebuah cabang yang dipangkas
  • Nilai akurat atau nilai gagal-rendah (alpha pruned), atau nilai gagal-tinggi (beta pruned)


Source:
voice-teacher.blogspot.com › Pengayaan
http://abdulagisni.blogspot.com/2017/11/

[TULISAN] BAB 5 - TAKTIK dalam PERMAINAN AI


TAKTIK dan STRATEGI dalam AI

Taktik Real-time (disingkat RTT sebagai fixed unit real-time strategy) adalah subgenre dari wargames taktis bermain di real-time simulasi pertimbangan dan keadaan perang operasional dan taktik militer.
Taktik turn-based ( TBT ), atau taktis turn-based ( TTB ), adalah genre strategi video game yang melalui stop-tindakan mensimulasikan pertimbangan dan keadaan perang operasional dan taktik militer di umumnya konfrontasi skala kecil dibandingkan dengan pertimbangan yang lebih strategis dari strategi turn-based (TBS) permainan.

Strategi real-time "(RTS) menunjukkan bahwa tindakan dalam permainan kontinu, dan pemain akan harus membuat keputusan dan tindakan mereka dalam latar belakang negara permainan yang terus berubah, dan komputer real-time strategy gameplay ditandai dengan memperoleh sumber daya, membangun pangkalan, meneliti teknologi dan memproduksi unit.

Taktik Real-time (disingkat RTT dan kurang umum disebut sebagai fixed unit real-time strategy) adalah subgenre dari wargames taktis bermain di real-time simulasi pertimbangan dan keadaan perang operasional dan taktik militer.

Turn-Based Game Strategi (TBS) biasanya diperuntukkan bagi strategi permainan komputer tertentu, untuk membedakan mereka dari real-time strategi permainan komputer. Seorang pemain dari permainan turn-based diperbolehkan periode analisis sebelum melakukan aksi game. Contoh genre ini adalah Civilization , Heroes of Might and Magic , Making History , Muka Wars , Master of Orion , dan Worms seri.

Taktik Turn-Based ( TBT ), atau taktis turn-based ( TTB ), adalah genre strategi video game yang melalui stop-tindakan mensimulasikan pertimbangan dan keadaan perang operasional dan taktik militer di umumnya konfrontasi skala kecil dibandingkan dengan pertimbangan yang lebih strategis dari strategi turn-based (TBS) permainan.

PERMAINAN MENGGUNAKAN TAKTIK REAL TIME
Soldiers: Heroes of World War II adalah yang pertama dalam serangkaian taktik video game real-time yang diatur dalam Perang Dunia II, yang dikembangkan oleh atau di bawah pengawasan Ukrainian company Best Way. Pemain dapat mengendalikan pasukan Amerika, Inggris, Soviet, atau Jerman untuk memainkan pertempuran yang diatur dalam Perang Dunia II. Permainan ini terutama permainan strategi, tetapi pemain dapat mengendalikan pasukannya dan mengarahkannya dengan keyboard dan mouse untuk kedalaman kontrol tambahan.

Source:
http://jokomurdiyanto.blogspot.com/2014/04/pengantar-teori-game-tactikal-strategy.html
https://en.wikipedia.org/wiki/Soldiers:_Heroes_of_World_War_II

[TUGAS] BAB 5 - TAKTIK DALAM PERMAINAN


WAYPOINT
Waypoint adalah titik acuan / kumpulan koordinat yang digunakan untuk keperluan navigasi untuk mengidentifikasi sebuah titik di peta. Koordinat-koordinat itu biasanya menyertakan longitude, latitude, dan kadang altitude untuk keperluan navigasi di udara.
Waypoint digunakan di berbagai navigasi yang tidak memiliki jalur yang tampak seperti navigasi di udara dan navigasi di laut, juga navigasi di darat yang tidak memiliki jalur yang jelas. Khusus navigasi di darat yang tidak menggunakan manusia sebagai penentu arah melainkan robot, waypoint digunakan meski terdapat jalur yang jelas. Hal ini penting agar robot tetap memiliki rute.
Waypoint dibagi menjadi dua jenis, yaitu waypoint fly by dan waypoint fly over. Waypoint fly by tidak melewati lokasi di atas way point namun tetap menuju ke arah tujuan, sedangkan waypoint fly over melewati lokasi di atas way point. Setelah satu waypoint terlewati, maka pilot harus menetapkan waypoint berikutnya yang disebut dengan waypoint aktif. Waypoint merupakan kumpulan dari beberapa titik kordinat yang kemudian dijadikan sebagai navigasi pergerakan.
Dalam sebuah game, pergerakan NPC (non playable character) umumnya menggunakan titik arah antara titik kordinat yang satu dengan yang lain ditentukan oleh pencipta game. Waypoint dapat digunakan pada non playable character untuk melakukan patroli di dalam game dengan melintasi titik-titik kordinat yang ditentukan.

ANALISIS TAKTIK
Taktik adalah suatu siasat atau akal yang dirancang dan akan dilaksanakan dalam permainan oleh perorangan, kelompok, maupun tim untuk memenangkan suatu pertandingan secara sportif. Taktik biasanya merujuk bagaimana perorangan atau kelompok yang digunakan dalam permainan tertentu.

PATH FINDING
Path Finding atau pencarian jalur adalah proses pencarian rute atau jalur tedekat dari suatu start menuju tujuan dengan jalur yang memiliki pengahalang – penghalang dari arena tersebut. pathfinding ini pada umumnya adalah untuk mencari jalur paling efisien dengan sebisa mungkin menghindari penghalang yang ada.
Pathfinding dapat diterapkan misalnya dalam membuat AI dari suatu game, misalnya agar AI tersebut dapat mengejar musuh secara efisien dan tanpa menabrak tembok atau menghindari penghalang lain. Terdapat beberapa metode yang dapat diterapkan dalam pathfinding ini, salah satu metode yang sering digunakan adalah A*.


Source:
http://jokomurdiyanto.blogspot.com/2014/04/pengantar-teori-game-tactikal-strategy.html
https://gurusakti.wordpress.com/2013/06/28/mengenal-algoritma-a-untuk-pencarian-jalur-rute-terdekat/

[PROGJAR] ANALISA PROGRAM


Kali ini saya akan menganalisa beberapa program yaitu getIP.java, getName.java, IptoName.java, NsLookup.java, dan program client-server sederhana. Berikut adalah analisanya

1.            getName.java
import java.net.*;
public class getName {
     public static void main(String args[]) throws Exception {
           InetAddress host = null;
           host = InetAddress.getLocalHost();
           System.out.println("Nama komputer Anda: " +

           host.getHostName());}}

 ANALISA
Program diatas adalah program untuk mengetahui nama komputer yang sedang dipakai. Program ini berguna supaya kita bisa jalankan program lain (program simpleClient.java dan program NsLookup.java) yang berkolerasi dengan program ini. Program ini menggunakan library .net yang digunakan java untuk program yang terhubung dengan jaringan. Inti dari program ini terdapat pada kodingan host.getHostName() yang berfungsi untuk mendapatkan hostname komputer yang sedang dipakai.

OUTPUT PROGRAM


2.            getIP.java

import java.net.*;
public class getIP {
public static void main(String args[]) throws Exception {
     InetAddress host = null;
     host = InetAddress.getLocalHost();
     byte ip[] = host.getAddress();
    
     for (int i=0; i < ip.length; i++) {
           if (i > 0) {
                System.out.print(".");}
           System.out.print(ip[i] & 0xff);}

     System.out.println();}}

 ANALISA

Program diatas adalah program untuk mengetahui alamat IP komputer yang sedang dipakai. Program ini berguna supaya kita bisa jalankan program lain (program IPtoName.java) yang berkolerasi dengan program ini. Program ini menggunakan library .net yang digunakan java untuk program yang terhubung dengan jaringan. Inti dari program ini terdapat pada kodingan byte ip[] = host.getAddress() yang berfungsi untuk mendapatkan alamat IP komputer yang sedang dipakai. Tipe data byte dipakai karena memiliki rentang nilai 0 s/d 255 yang memang dipakai untuk memberikan alamat IP komputer. Setelah itu terdapat blok for Untuk mengeluarkan output dari hasil perintah host.getAddress .

OUTPUT PROGRAM
3.            IptoName.java

import java.net.*;
public class IPtoName {
     public static void main(String args[]) {
           if (args.length == 0) {
       System.out.println("Pemakaian: java IPtoName ");
                System.exit(0);}

           String host = args[0];
           InetAddress address = null;
          
           try {
                address = InetAddress.getByName(host);}
           catch (UnknownHostException e) {
                System.out.println("invalid IP - malformed IP");
                System.exit(0);}


           System.out.println(address.getHostName());}}

 ANALISA
Program diatas adalah program untuk mengetahui nama komputer yang sedang dipakai menggunakan alamat IP komputer yang diinput. Program ini menggunakan library .net yang digunakan java untuk program yang terhubung dengan jaringan. Inti program diatas adalah System.out.println(address.getHostName()) untuk mengeluarkan input hostname yang diperoleh dari proses kodingan  address = InetAddress.getByName(host) yaitu kodingan proses pengambilan nama computer dengan alamat IP yang kita masukkan sebelumnya dan disimpan di variable host. Jika alamat yang diinput salah, maka akan menampilkan output error dengan tulisan “Invalid IP – Malformed IP” dan program akan berhenti dan keluar.

OUTPUT PROGRAM

4.            NsLookup.java

import java.net.*;
public class NsLookup {
     public static void main(String args[]) {
           if (args.length == 0) {
                System.out.println("Pemakaian: java NsLookup ");
                System.exit(0);}

           String host = args[0];
           InetAddress address = null;
          
           try {
                address = InetAddress.getByName(host);}
           catch(UnknownHostException e) {
                System.out.println("Unknown host");
                System.exit(0);}

           byte[] ip = address.getAddress();
           for (int i=0; i < ip.length; i++) {
                if (i > 0) System.out.print(".");
                System.out.print((ip[i]) & 0xff);}

           System.out.println();}}

 ANALISA
Program diatas adalah kebalikan dari program IptoName.java. Program ini untuk mengetahui alamat IP komputer yang sedang dipakai menggunakan hostname komputer yang diinput. Sama seperti sebelumnya, program ini juga menggunakan library .net yang digunakan java untuk program yang terhubung dengan jaringan. Pada kodingan address = InetAddress.getByName(host) adalah kodingan proses pengambilan alamat IP komputer dengan hostname yang kita masukkan sebelumnya dan disimpan di variable host. Jika alamat yang diinput salah, maka akan menampilkan output error dengan tulisan “Unknown Host” dan program akan berhenti dan keluar. Lalu pada baris byte[] ip = address.getAddress() adalah untuk mengambil alamat IP komputer yang diperoleh dari proses sebelumnya. Untuk mengeluarkan output alamat IP tersebut digunakan blok for sama seperti program getIP.java

OUTPUT PROGRAM

5.            Program Client-Server sederhana
a.     simpleServer.java
import java.io.*;
import java.net.*;
public class simpleServer {
   public final static int TESTPORT = 5000;
   public static void main(String args[]) {
        ServerSocket checkServer = null;
        String line;
        BufferedReader is = null;
        DataOutputStream os = null;
        Socket clientSocket = null;
       
        try {
             checkServer = new ServerSocket(TESTPORT);
             System.out.println("Aplikasi Server hidup ...");}
        catch (IOException e) {
             System.out.println(e);}
       
        try {
             clientSocket = checkServer.accept();
             is = new BufferedReader(new InputStreamReader(clientSocket.getInputStream()));
             os = new DataOutputStream(clientSocket.getOutputStream());}
        catch (Exception ei) {
             ei.printStackTrace();}
            
        try {
             line = is.readLine();
             System.out.println("Terima : " + line);
             if (line.compareTo("salam") == 0) {
                   os.writeBytes("salam juga");}
             else {
                   os.writeBytes("Maaf, saya tidak mengerti");}}
        catch (IOException e) {
             System.out.println(e);}

        try {
             os.close();
             is.close();
             clientSocket.close();}
        catch (IOException ic) {

             ic.printStackTrace();}}}

ANALISA
Program diatas adalah program server untuk menyediakan layanan kepada client. Apabila program ini berhasil dijalankan akan mengeluarkan output "Aplikasi Server hidup ..." dan menunggu permintaan dari client. Dengan menggunakan perintah accept, berarti program ini menerima permintaan dari client. Apabila client telah mengirimkan pesan berupa tulisan “salam” maka otomatis server akan mengirimkan pesan “salam juga” ke client yang hanya ditampilkan pada tampilan client. Apabila bukan tulisan “salam” maka server akan mengirimkan pesan “maaf, saya tidak mengerti”. Program ini hanya dapat melakukan satu kali permintaan yang diterima setalah itu program akan berhenti dan keluar.

OUTPUT PROGRAM

b.     simpleClient.java

import java.io.*;
import java.net.*;
public class simpleClient {
  public final static int REMOTE_PORT = 5000;
 public static void main(String args[]) throws Exception {
    Socket cl = null;
    BufferedReader is = null;
    DataOutputStream os = null;
    BufferedReader stdin = new BufferedReader(new
    InputStreamReader(System.in));
    String userInput = null;
    String output = null;

// Membuka koneksi ke server pada port REMOTE_PORT
    try {
          cl = new Socket(args[0], REMOTE_PORT);
          is = new BufferedReader(new
          InputStreamReader(cl.getInputStream()));      os = new DataOutputStream(cl.getOutputStream());}
    catch(UnknownHostException e1) {
          System.out.println("Unknown Host: " + e1);}
    catch (IOException e2) {
          System.out.println("Erorr io: " + e2);}

    // Menulis ke server
    try {
          System.out.print("Masukkan kata kunci: ");
          userInput = stdin.readLine();
          os.writeBytes(userInput + "\n");}
    catch (IOException ex) {
      System.out.println("Error writing to server..." + ex);}

// Menerima tanggapan dari server
    try {
       output = is.readLine();
       System.out.println("Dari server: " + output);}
    catch (IOException e) {
          e.printStackTrace();}

// close input stream, output stream dan koneksi
    try {
          is.close();
          os.close();
          cl.close();}
    catch (IOException x) {

      System.out.println("Error writing...." + x);}}}


ANALISA
Program diatas adalah program client untuk meminta layanan kepada server. Saat dijalankan, program ini harus menyertakan hostname server agar terhubung dengan server yang sesuai dengan begitu client dapat mengirimkan permintaannya. Apabila program ini berhasil dijalankan akan mengeluarkan input "Masukkan kata kunci: "dan apabila kita input sesuai dengan kata kunci yang ada di program server maka server akan mengirimkan output “salam juga”.  Apabila bukan tulisan “salam” maka server akan mengirimkan pesan “maaf, saya tidak mengerti” di tampilan output client. Program ini hanya dapat melakukan satu kali permintaan yang diterima setalah itu program akan berhenti dan keluar.
             
           OUTPUT PROGRAM    




NAMA      : PUTRI NURHASANAH D
KELAS     : 4IA23
NPM         : 58414617
Langganan: Postingan (Atom)