Memberikan penempatan bom cerdas AI Bomberman

13

Saya mencoba menerapkan algoritma AI untuk Bomberman. Saat ini saya memiliki implementasi rudimenter yang berfungsi tetapi tidak terlalu pintar (AI saat ini terlalu bersemangat dalam menempatkan bom).

Ini adalah AI pertama yang pernah saya coba terapkan dan saya agak macet. Algoritma yang lebih canggih yang ada dalam pikiran saya (yang saya harapkan dapat membuat keputusan yang lebih baik) terlalu berbelit-belit untuk menjadi solusi yang baik.

Apa tip umum yang Anda miliki untuk menerapkan Bomberman AI? Apakah ada pendekatan yang sangat berbeda untuk membuat bot lebih defensif atau ofensif?


Sunting: Algoritma saat ini

Algoritme saya saat ini berjalan seperti ini (pseudo-code):

1) Cobalah untuk menempatkan bom dan kemudian temukan sel yang aman dari semua bom, termasuk yang baru saja Anda tempatkan. Untuk menemukan sel itu, lakukan iterate pada empat arah; jika Anda dapat menemukan sel divergen aman dan mencapainya tepat waktu (mis. jika arahnya naik atau turun, cari sel yang ditemukan di kiri atau kanan jalan ini), maka aman untuk menempatkan bom dan bergerak ke arah itu.

2) Jika Anda tidak dapat menemukan dan mengamankan sel-sel yang berbeda, cobalah JANGAN menempatkan bom dan melihat lagi. Kali ini Anda hanya perlu mencari sel aman hanya dalam satu arah (Anda tidak harus menyimpang darinya).

3) Jika Anda masih tidak dapat menemukan sel yang aman, jangan lakukan apa pun.

for $(direction) in (up, down, left, right):
    place bomb at current location
    if (can find and reach divergent safe cell in current $(direction)):
        bomb = true
        move = $(direction)
        return

for $(direction) in (up, down, left, right):
    do not place bomb at current location
    if (any safe cell in the current $(direction)):
        bomb = false
        move = $(direction)
        return

else:
    bomb = false
    move = stay_put

Algoritma ini membuat bot sangat memicu-senang (ini akan menempatkan bom sangat sering). Itu tidak membunuh dirinya sendiri, tetapi memiliki kebiasaan membuat dirinya rentan dengan masuk ke jalan buntu di mana ia dapat diblokir dan dibunuh oleh pemain lain.

Apakah Anda punya saran tentang bagaimana saya dapat meningkatkan algoritma ini? Atau mungkin saya harus mencoba sesuatu yang sama sekali berbeda?

Salah satu masalah dengan algoritma ini adalah bahwa ia cenderung meninggalkan bot dengan sangat sedikit (seringkali hanya satu) sel aman yang dapat bertahan. Ini karena bot meninggalkan jejak bom di belakangnya, selama itu tidak bunuh diri.

Namun, meninggalkan jejak bom di belakang menyisakan beberapa tempat di mana Anda dapat bersembunyi. Jika salah satu pemain atau bot lain memutuskan untuk meletakkan bom di suatu tempat di dekat Anda, sering terjadi bahwa Anda tidak memiliki tempat untuk bersembunyi dan Anda mati.

Saya perlu cara yang lebih baik untuk memutuskan kapan akan menempatkan bom.

Paul Manta
sumber
Sulit untuk memikirkan sesuatu yang bekerja 100% tiba-tiba. Tetapi mungkin jika Anda menambahkan algoritme yang Anda miliki saat ini, kami semua dapat membantu meningkatkannya secara bertahap. Anda juga mungkin bukan penghobi pertama yang mencoba menerapkan AI Bomberman, dan saya telah menemukan beberapa kompetisi AI Bomberman dengan pencarian Google acak yang dapat membuktikan sumber informasi yang sangat berharga bagi Anda.
Roy T.
Saya pikir Anda dapat menggeneralisasi pembom AI dalam dua hal: 1) mencoba melindungi diri Anda dari peledakan bom pemain lain 2) menempatkan bom di papan permainan untuk mencoba membuat orang lain mati (sambil tetap mengingat aturan 1): untuk menghindari peledakan / terperangkap oleh bommu sendiri).
tigrou
Mungkin akan lebih baik jika Anda memposting setidaknya gambaran umum tingkat tinggi dari implementasi Anda saat ini (dengan asumsi banyak kode) dan kami mungkin dapat membantu Anda memecahkan masalah Anda karena mereka terlalu bersemangat dalam menempatkan bom.
Tetrad
@Tetrad Saya sedang dalam proses mengimplementasikan algoritma baru. Saya akan melihat bagaimana yang berjalan dan memposting algoritma di sini jika perlu.
Paul Manta
Meskipun ini bukan tip nyata tetapi Anda dapat melihat kode clanbomber . itu adalah permainan dalam banyak hal mirip dengan pelaku bom.
Ali1S232

Jawaban:

4

Masalah yang Anda hadapi adalah bahwa AI Anda tidak pernah berhenti untuk membuat keputusan yang cerdas tentang di mana ia harus meletakkan bom berikutnya, yang membuatnya hanya menjatuhkan bom kapan pun ia bisa dan kemudian bekerja "sial, sial, apa yang saya lakukan sekarang! ? "

Berhenti sejenak untuk berpikir

Saat ini, AI Anda hanya mengembara entah ke mana. Namun, kadang-kadang, itu sebenarnya harus bergerak ke target. Sebagai contoh, jika ia melihat powerup dan berpikir ia dapat mencapainya sebelum pemain, mungkin ia harus menemukan jalan yang aman ke ubin itu dan pindah ke sana, mengawasi bom dan menghindari mereka di sepanjang jalan.

Perilaku pindah-ke-target yang sama dapat digunakan ketika memikirkan tentang di mana menempatkan bom berikutnya .

Ketika AI Anda dapat menempatkan bom, alih-alih langsung melakukannya, AI harus menggunakan algoritma pencarian untuk memilih dari tempat penempatan bom yang tersedia berdasarkan kriteria seperti:

  • Apakah di dekatnya? (sehingga tidak berjalan ke sudut berlawanan diagonal peta setiap kali ia ingin menempatkan bom)
  • Apakah ada tempat yang bisa saya sembunyikan dari ledakan - dan dapatkah saya sampai di sana sebelum bom meledak?
  • Apakah ledakan akan meledakkan ubin dan memberi saya powerups?
  • Apakah itu berpotensi menyerang pemain? (AI yang lebih mudah mungkin menghindari ini di game awal, AI agresif akan mengejar ini - sementara tidak melupakan powerups)

Ketika keputusan ini telah dibuat, AI telah memilih tempat penempatan bom, dan tempat untuk bersembunyi dari ledakannya. Sekarang ia bisa berjalan ke tempat itu, meletakkan bomnya, lalu berjalan ke tempat persembunyiannya. Setelah mencapai tempat persembunyiannya, ia mungkin ingin terus berjalan dan menemukan lokasi bom (jika memiliki banyak bom), asalkan tetap ingat untuk menghindari jalan bom yang ia jalani di sini untuk menghindari.

Berjalan, dan menemukan jalan yang aman

Anda dapat mengembangkan untuk AI metode berjalan tunggal ke titik Anda dan gunakan ini setiap kali Anda menginginkannya berjalan di suatu tempat. Metode ini dapat menggunakan algoritma pencarian A * untuk menemukan jalurnya.

Untuk menjaga agar AI tetap aman, Anda mungkin ingin memeriksanya kembali setiap kali bom baru dipasang. Untuk menghindari ledakan, bom dapat memeriksa waktu sampai bom meledak, dan mempertimbangkan ubin ledakan potensial yang aman untuk dilewati jika bom tidak akan meledak saat sedang berjalan melalui ubin itu - dan jika tidak aman, perlakukan sebagai ubin yang tidak bisa dilewati. .

Untuk memberikan kesalahan AI Anda (sehingga kadang-kadang bisa meledak) itu harus membuat kesalahan perhitungan: lupa tentang bom tanpa sadar, meremehkan ukuran ledakan atau waktu sampai bom meledak, dll.

Catatan: Anda juga dapat membuat jalan acaknya tampak lebih terarah dengan memilih secara acak tempat-tempat untuk berjalan, atau selalu memiliki tempat penempatan bom baru dalam pikiran untuk berjalan, daripada hanya memilih secara acak ubin yang berdekatan untuk berkeliaran. Dengan begitu ia tidak akan bolak-balik di tempat yang sama seolah-olah ia tidak bisa mengambil keputusan.

doppelgreener
sumber
Saya lupa memberikan beberapa detail yang relevan tentang game. Ini adalah versi sederhana dari Bomberman: tidak ada power-up, pemain selalu dapat menempatkan bom tanpa batas, dan bom selalu memiliki jangkauan maksimum (dari satu ujung peta ke yang lain). Sistem poinnya juga berbeda ... [cont'd]
Paul Manta
[lanjutan] Anda mendapatkan 1 poin untuk menempatkan bom, tetapi 0 poin karena menghancurkan dinding. Anda juga mendapatkan 30 poin untuk membunuh, 15 untuk bantuan dan -20 untuk bunuh diri. [lanjutan]
Paul Manta
[lanjutan] Dengan mengingat hal itu, AI harus mencoba menempatkan bom sesering mungkin (karena menempatkan bom memberi bom), tetapi tidak perlu sangat berhati-hati mengenai di mana bom ditempatkan. Memang harus berhati-hati tentang selalu memiliki tempat yang aman untuk pergi. [cont'd]
Paul Manta
[lanjutan] Apakah Anda berpikir bahwa ketika memilih arah, cukup bagi saya untuk memilih yang mengarah ke area yang aman . Alih-alih mencari sel aman, saya akan mencari area aman terbesar, jadi saya bisa bersembunyi dari bom yang ditempatkan oleh pemain lain juga, bukan hanya milik saya. Juga, apakah itu ide yang baik untuk mendukung arahan yang membuat saya lebih dekat dengan salah satu pemain lain?
Paul Manta
3
Kalau begitu kita tidak berbicara tentang Bomberman dan AI-nya sama sekali! Kami hanya tentang Beberapa Permainan Dengan Bom Yang Dangkal Menyerupai Bomberman Tapi Di Bawah Tudung Sangat Berbeda Dan Mendorong Anda Menjadi Pemicu Bahagia yang Bahagia , dan saya memiliki pengalaman yang jauh lebih sedikit dalam berurusan dengan permainan itu.
doppelgreener