Minimax untuk Bomberman

11

Saya mengembangkan klon game Bomberman dan saya bereksperimen dengan berbagai jenis AI. Pertama saya menggunakan pencarian melalui ruang negara dengan A * dan sekarang saya ingin mencoba pendekatan yang berbeda dengan algoritma Minimax. Masalah saya adalah bahwa setiap artikel minimum yang saya temukan diasumsikan pemain bergantian. Namun di Bomberman, setiap pemain melakukan beberapa aksi pada saat yang bersamaan. Saya pikir saya bisa menghasilkan semua status yang mungkin untuk satu tick game, tetapi dengan empat pemain dan 5 aksi dasar (4 gerakan dan tempat bom) memberikan 5 ^ 4 status di level pertama dari tree game. Nilai itu akan meningkat secara eksponensial dengan setiap level berikutnya. Apakah saya melewatkan sesuatu? Apakah ada cara untuk mengimplementasikannya atau haruskah saya menggunakan algoritma yang sama sekali berbeda? Terima kasih atas sarannya

Billda
sumber
1
Meskipun ini adalah topik yang agak tidak umum, satu hal yang saya suka lakukan dengan AI adalah menggunakan tujuan atau kepribadian untuk AI. Ini bisa berupa hal-hal seperti menimbun power up, non-agresif, mencari balas dendam, terburu-buru, dll. Dengan tujuan seperti itu Anda dapat secara kasar menentukan arah mana Anda harus bergerak dan hanya menjatuhkan bom jika itu memajukan kemajuan Anda ke tujuan (jika itu cukup dekat dengan pemain yang kamu buru atau blok yang ingin kamu hancurkan).
Benjamin Danger Johnson
2
Ya, Anda melewatkan beberapa hal, tetapi Anda tidak akan berterima kasih kepada saya karena menunjukkannya karena memperburuknya. Tidak ada 5 tindakan dasar. Beberapa kotak memiliki 5 "bergerak" (4 arah dan tetap diam); yang lain memiliki 3 (karena mereka diblokir dalam dua arah); rata-rata adalah 4. Tapi Anda bisa menjatuhkan bom saat berlari , jadi rata-rata faktor percabangan adalah 8. Dan seseorang dengan powerup berkecepatan tinggi dapat memuat lebih banyak gerakan, secara efektif mendorong faktor percabangannya.
Peter Taylor
Saya memberi Anda jawaban dalam pertanyaan Anda menggunakan pencarian pohon monte carlo.
SDwarfs
Minimax sama sekali tidak berguna dalam situasi dengan banyak pilihan seperti Bomberman. Anda akan kehabisan kemampuan untuk mencari sebelum melangkah cukup jauh untuk melihat apakah suatu langkah masuk akal atau tidak.
Loren Pechtel

Jawaban:

8

Game Strategi Real-Time seperti bomber man mengalami masa sulit dengan AI. Anda ingin menjadi cerdas, tetapi pada saat yang sama itu tidak bisa sempurna.

Jika AI sempurna, pemain Anda akan frustrasi. Entah karena mereka selalu kehilangan atau Anda mendapatkan 0,3 frame per detik.

Jika tidak cukup cerdas, pemain Anda akan bosan.

Rekomendasi saya adalah memiliki dua fungsi AI, yang menentukan kemana AI pergi, yang lain menentukan kapan yang terbaik untuk menjatuhkan bom. Anda dapat menggunakan hal-hal seperti prediksi pergerakan untuk menentukan apakah musuh bergerak menuju tempat yang akan berbahaya jika bom dijatuhkan di lokasi saat ini.

Tergantung pada kesulitan Anda dapat memodifikasi fungsi-fungsi ini untuk meningkatkan atau mengurangi kesulitan.

Garis BawahZero
sumber
2
Waktu, frustrasi, dan kebosanan bukanlah masalah. Saya menulis tesis sarjana tentang pendekatan AI yang berbeda di Bomberman dan membandingkannya. Jadi jika sempurna lebih baik. Saya terjebak dengan minimax itu sekarang
Billda
1
Masalah yang akan Anda temui dalam algoritma minimax adalah waktu pemrosesan. Anda harus melacak semua tindakan musuh dan menentukan gaya permainan mereka dan gaya bermain lawan Anda. Sepertinya Anda sudah mengetahui hal ini, tetapi ini bisa menjadi tugas yang menakutkan untuk gim real time tanpa memperlambat gim. Alih-alih membangun pohon bermain, Anda perlu menentukan tindakan Anda secara langsung, mungkin membangun algoritma pembelajaran mesin yang menjadi lebih baik semakin banyak bermain?
UnderscoreZero
4

Seperti yang Anda perhatikan, Bomberman terlalu rumit untuk disimulasikan sebagai gim berbasis giliran. Mengekstrapolasi setiap keputusan yang mungkin ada ditambah setiap kemungkinan keputusan dari setiap pemain lain tidak berhasil.

Alih-alih itu, Anda sebaiknya menggunakan pendekatan yang lebih strategis.

Anda harus bertanya pada diri sendiri: Bagaimana seorang pemain manusia membuat keputusan saat bermain bomberman? Biasanya, pemain harus mengikuti empat prioritas dasar:

  1. menghindari area ledakan bom
  2. letakkan bom sehingga orang lain tidak dapat menghindari daerah ledakan mereka
  3. kumpulkan powerups
  4. Tempatkan bom untuk meledakkan batu

Prioritas pertama dapat dipenuhi dengan membuat "peta bahaya". Ketika sebuah bom ditempatkan, semua ubin yang ditutupi olehnya harus ditandai sebagai "berbahaya". Semakin cepat bom meledak (ingat reaksi berantai!), Semakin tinggi tingkat bahaya. Kapan saja AI mengetahui bahwa ia berada di lapangan dengan bahaya tinggi, ia harus menjauh. Ketika merencanakan bidang (dengan alasan apa pun), bidang dengan tingkat bahaya tinggi harus dihindari (dapat diimplementasikan dengan menambahkan biaya jalur yang lebih tinggi secara artifisial kepada mereka).

Perhitungan peta bahaya dapat lebih ditingkatkan untuk melindungi AI dari keputusan bodoh (seperti memasuki area yang sulit untuk melarikan diri dari saat pemain lain berada di dekat).

Ini seharusnya sudah membuat AI defensif yang masuk akal. Jadi bagaimana dengan pelanggaran?

Ketika AI menyadari bahwa itu cukup aman saat ini, ia harus merencanakan manuver ofensif: Ia harus mempertimbangkan bagaimana hal itu dapat meningkatkan peta bahaya di sekitar pemain lain dengan menempatkan bom itu sendiri. Ketika memilih lokasi untuk menanam bom, ia harus memilih lokasi yang dekat sehingga tidak harus bergerak sejauh ini. Seharusnya juga mengabaikan lokasi bom ketika peta bahaya yang dihasilkan tidak memungkinkan untuk rute pelarian yang masuk akal.

Philipp
sumber
Pengalaman saya yang terbatas dengan bermain itu adalah bahwa Anda biasanya harus menempatkan beberapa bom untuk membunuh lawan yang kompeten - strategi perlu mempertimbangkan hal ini. Saya telah bermain melawan AI dengan kira-kira strategi Anda, mereka cukup tidak efektif membunuh Anda kecuali Anda bisa dipojokkan.
Loren Pechtel
4

Saya pikir saya bisa menghasilkan semua status yang mungkin untuk satu tick game, tetapi dengan empat pemain dan 5 aksi dasar (4 gerakan dan tempat bom) memberikan 5 ^ 4 status di level pertama dari tree game.

Benar! Anda perlu mencari semua tindakan 5 ^ 4 (atau bahkan 6 ^ 4, karena Anda bisa berjalan ke 4 arah, berhenti dan "pasang bom"?) Untuk setiap centang game. TETAPI, ketika seorang pemain sudah memutuskan untuk pindah, dibutuhkan beberapa waktu hingga langkah tersebut dijalankan (mis. 10 tick game). Selama periode ini jumlah kemungkinan berkurang.

Nilai itu akan meningkat secara eksponensial dengan setiap level berikutnya. Apakah saya melewatkan sesuatu? Apakah ada cara untuk mengimplementasikannya atau haruskah saya menggunakan algoritma yang sama sekali berbeda?

Anda dapat menggunakan Hash-Table untuk hanya menghitung status permainan "subtree" yang sama satu kali. Bayangkan pemain A berjalan naik dan turun, sementara semua pemain lain "menunggu", Anda berakhir dalam keadaan permainan yang sama. Sama seperti untuk "kiri-kanan" atau "kanan-kiri". Juga memindahkan "atas-kemudian-kiri" dan "kiri-kemudian-atas" menghasilkan kondisi yang sama. Menggunakan Tabel-Hash Anda dapat "menggunakan kembali" skor yang dihitung untuk kondisi permainan yang telah dievaluasi. Ini mengurangi kecepatan pertumbuhan yang cukup banyak. Secara matematis, ini mengurangi basis fungsi pertumbuhan eksponensial Anda. Untuk mendapatkan gambaran tentang seberapa banyak hal itu mengurangi kompleksitas, mari kita lihat pergerakan yang mungkin dilakukan hanya untuk satu pemain dibandingkan dengan posisi yang dapat dijangkau di peta (= status permainan yang berbeda) jika pemain hanya dapat bergerak ke atas / bawah / kiri / kanan / berhenti .

kedalaman 1: 5 bergerak, 5 status berbeda, 5 status tambahan untuk rekursi ini

kedalaman 2: 25 bergerak, 13 status berbeda, 8 status tambahan untuk rekursi ini

kedalaman 3: 6125 bergerak, 25 status berbeda, 12 status tambahan untuk rekursi ini

Untuk memvisualisasikannya, jawab diri Anda sendiri: bidang mana di peta yang dapat dijangkau dengan satu gerakan, dua gerakan, tiga gerakan. Jawabannya adalah: Semua bidang dengan jarak maksimum = 1, 2 atau 3 dari posisi awal.

Saat menggunakan HashTable, Anda hanya perlu mengevaluasi setiap kondisi permainan yang dapat dijangkau (dalam contoh kami 25 pada kedalaman 3) satu kali. Sedangkan tanpa HashTable Anda perlu mengevaluasinya beberapa kali, yang berarti 6125 evaluasi, bukannya 25 pada level kedalaman 3. Yang terbaik: Setelah Anda menghitung entri HashTable, Anda dapat menggunakannya kembali dalam langkah waktu berikutnya ...

Anda juga dapat menggunakan subtingkat "cut" deepening deepening dan pemangkasan alpha-beta yang tidak layak dicari secara lebih mendalam. Untuk catur, ini mengurangi jumlah node yang dicari menjadi sekitar 1%. Pengantar singkat tentang pemangkasan alpha-beta dapat ditemukan sebagai video di sini: http://www.teachingtree.co/cs/watch?concept_name=Alpha-beta+Pruning

Awal yang baik untuk studi lebih lanjut adalah http://chessprogramming.wikispaces.com/Search . Halaman ini terkait dengan catur, tetapi algoritma pencarian dan optimisasi cukup sama.

Algoritma AI lain (tetapi kompleks) - yang akan lebih cocok untuk permainan - adalah "Temporal Difference Learning".

Salam

Stefan

PS: Jika Anda mengurangi jumlah status gim yang mungkin (mis. Ukuran peta yang sangat kecil, hanya satu bom per pemain, tidak ada yang lain), ada peluang untuk menghitung sebelum evaluasi untuk semua kondisi gim.

--edit--

Anda juga bisa menggunakan hasil perhitungan minimax yang dihitung secara offline untuk melatih jaringan saraf. Atau Anda dapat menggunakannya untuk mengevaluasi / membandingkan strategi yang diimplementasikan dengan tangan. Misalnya Anda dapat menerapkan beberapa "kepribadian" yang disarankan dan beberapa heuristik yang mendeteksi, di mana situasi strategi mana yang baik. Karenanya Anda harus "mengklasifikasikan" situasi (misalnya status permainan). Ini juga dapat ditangani oleh jaringan neuron: Latih jaringan neuron untuk memprediksi strategi kode tangan mana yang memainkan yang terbaik dalam situasi saat ini dan jalankan. Ini harus menghasilkan keputusan real-time yang sangat bagus untuk game nyata. Jauh lebih baik daripada pencarian batas bawah yang dapat dicapai jika tidak, karena tidak masalah berapa lama perhitungan offline dilakukan (sebelum sebelum permainan).

- edit # 2 -

Jika Anda hanya menghitung ulang gerakan terbaik Anda setiap 1 detik, Anda juga bisa mencoba melakukan perencanaan level yang lebih tinggi. Apa yang saya maksud dengan itu? Anda tahu berapa banyak gerakan yang dapat Anda lakukan dalam 1 detik. Jadi, Anda dapat membuat daftar posisi yang dapat dijangkau (mis. Jika ini adalah 3 gerakan dalam 1 detik, Anda akan memiliki 25 posisi yang dapat dijangkau). Maka Anda dapat merencanakan seperti: pergi ke "posisi x dan tempatkan bom". Seperti yang disarankan beberapa orang lainnya, Anda dapat membuat peta "bahaya", yang digunakan untuk algoritme perutean (cara menuju ke posisi x? Jalur mana yang harus dipilih [ada beberapa variasi yang mungkin dalam kebanyakan kasus]). Ini kurang memakan memori dibandingkan dengan HashTable yang sangat besar, tetapi menghasilkan hasil yang kurang optimal. Tetapi karena menggunakan lebih sedikit memori, itu bisa lebih cepat karena efek caching (lebih baik menggunakan cache memori L1 / L2 Anda).

TAMBAHAN: Anda bisa melakukan pra-pencarian yang hanya berisi gerakan untuk masing-masing pemain untuk memilah variasi yang mengakibatkan kehilangan. Karenanya, keluarkan semua pemain lain dari permainan ... Simpan kombinasi mana yang dapat dipilih setiap pemain tanpa kehilangan. Jika hanya ada gerakan yang kehilangan, cari kombinasi gerakan tempat pemain tetap hidup dalam waktu lama. Untuk menyimpan / memproses struktur pohon semacam ini, Anda harus menggunakan array dengan indeks-pointer seperti ini:

class Gamestate {
  int value;
  int bestmove;
  int moves[5];
};

#define MAX 1000000
Gamestate[MAX] tree;

int rootindex = 0;
int nextfree = 1;

Setiap negara bagian memiliki "nilai" evaluasi dan tautan ke Gamestates berikutnya ketika memindahkan (0 = berhenti, 1 = naik, 2 = kanan, 3 = turun, 4 = kiri) dengan menyimpan indeks array dalam "pohon" dalam gerakan [0 ] untuk bergerak [4]. Untuk membangun pohon Anda secara rekursif ini bisa terlihat seperti ini:

const int dx[5] = { 0,  0, 1, 0, -1 };
const int dy[5] = { 0, -1, 0, 1,  0 };

int search(int x, int y, int current_state, int depth_left) {
  // TODO: simulate bombs here...
  if (died) return RESULT_DEAD;

  if (depth_left == 0) {
    return estimate_result();
  }

  int bestresult = RESULT_DEAD;

  for(int m=0; m<5; ++m) {
    int nx = x + dx[m];
    int ny = y + dy[m];
    if (m == 0 || is_map_free(nx,ny)) {
      int newstateindex = nextfree;
      tree[current_state].move[m] = newstateindex ;
      ++nextfree;

      if (newstateindex >= MAX) { 
        // ERROR-MESSAGE!!!
      }

      do_move(m, &undodata);
      int result = search(nx, ny, newstateindex, depth_left-1);
      undo_move(undodata);

      if (result == RESULT_DEAD) {
        tree[current_state].move[m] = -1; // cut subtree...
      }

      if (result > bestresult) {
        bestresult = result;
        tree[current_state].bestmove = m;
      }
    }
  }

  return bestresult;
}

Jenis struktur pohon ini jauh lebih cepat, karena mengalokasikan memori secara dinamis sangat lambat! Tapi, menyimpan pohon pencarian juga cukup lambat ... Jadi ini lebih merupakan inspirasi.

SDwarfs
sumber
0

Apakah akan membantu membayangkan bahwa setiap orang bergiliran?

Secara teknis, dalam sistem yang mendasarinya, mereka benar-benar melakukannya, tetapi karena hal-hal yang saling terkait dan tumpang tindih, mereka tampaknya berjalan secara bersamaan.

Ingat juga bahwa Anda tidak harus menjalankan AI setelah setiap frame animasi. Banyak game kasual yang sukses hanya menjalankan algoritme AI setiap detik atau lebih, memberikan karakter yang dikontrol AI dengan informasi tentang ke mana mereka akan pergi atau apa yang seharusnya mereka lakukan, kemudian informasi tersebut digunakan untuk mengontrol karakter AI di bingkai lainnya.

Rasimaztion
sumber
Saya tidak menghitung AI setiap frame animasi tetapi setiap detik. Setiap detik lingkungan saya mengumpulkan tindakan semua pemain dan mengirimkan mereka status baru yang diperbarui.
Billda