Bagian pertama (analisis kode) ada di sini: https://habr.com/post/420725/ .

Algoritma

Deskripsi

Algoritme secara terus menerus melakukan langkah-langkah berikut:

1. Dia menunggu sampai tetrimino baru dibuat.
2. Periksa jenis tetrimino yang baru dibuat, jenis tetrimino berikutnya (gambar di bidang pratinjau) dan konten dari lapangan bermain.
3. Jelajahi semua cara yang mungkin untuk menambahkan dua tetrimino ke lapangan bermain dan mengevaluasi setiap probabilitas.
4. Memindahkan tetrimino yang baru dibuat sehingga cocok dengan lokasi probabilitas yang paling terdeteksi.

Setiap langkah ini dijelaskan secara rinci di bawah ini.

Kunci pencarian

Pertimbangkan versi Tetris yang disederhanakan, di mana bentuknya tidak jatuh secara otomatis. Satu-satunya cara untuk menurunkan angka adalah dengan menurunkannya dengan lembut. Setelah menghapus timing dari permainan, kita dapat sepenuhnya menggambarkan keadaan tetrimino aktif berdasarkan posisi dan orientasinya. Angka tersebut memiliki tempat penciptaan awal yang diketahui, dan operasi berikut digunakan untuk mengkonversi dari satu kondisi ke kondisi lain:

• Satu langkah ke bawah
• Satu langkah lagi
• Pindahkan satu langkah ke kanan
• Putar satu langkah berlawanan arah jarum jam
• Rotasi searah jarum jam

Operasi ini hanya berlaku ketika kuadrat tetrimino yang dihasilkan sesuai dengan sel-sel kosong dari lapangan bermain. Ketika mustahil untuk bergerak satu langkah ke bawah, negara dianggap diblokir. Namun, karena kami menyederhanakan Tetris dan menunggu penguncian pada dasarnya tidak terbatas, keadaan terkunci dapat diubah lebih lanjut oleh operasi lain dengan menggeser dan menggulir.

Banyak negara yang diblokir dengan urutan operasi minimal yang membuatnya dapat ditemukan menggunakan pencarian breadth-first (BFS). Seperti yang dinyatakan di bawah ini, ia menggunakan antrian untuk menyimpan hasil antara.

1. Kami mengantri negara saat membuat.
2. Kami menyimpulkan negara dari antrian.
3. Kami mendapatkan status berikut menggunakan operasi konversi.
4. Jika tidak ada gerakan ke bawah di antara mereka, maka negara yang dihapus dari antrian diblokir.
5. Kami mengantri status berikutnya yang belum kami kunjungi.
6. Jika antrian tidak kosong, ulangi dari langkah 2.

Program ini mewakili setiap negara sebagai objek dengan bidang-bidang berikut:

{ x, y, rotation, visited, predecessor }

Dalam proses persiapan, program membuat array tiga-dimensi objek negara (20 baris × 10 kolom × 4 putaran), menginisialisasi x , y dan rotation sesuai.

Bidang yang visited ditandai ketika negara antri. Dalam BFS, ini valid karena setiap keadaan berikutnya meningkatkan panjang lintasan total dengan 1. Artinya, dengan meningkatkan panjang lintasan tidak mungkin untuk membuat keadaan berikutnya yang perlu dimasukkan di tempat lain selain akhir antrian untuk menjaga ketertiban.

Bidang predecessor menunjukkan objek keadaan dari mana kondisi saat ini diturunkan. Sudah diatur ketika negara antri. Keadaan penciptaan tidak memiliki status sebelumnya.

Himpunan negara yang diblokir terdeteksi selama pencarian ditentukan oleh jenis tetrimino dan blok yang diisi di lapangan bermain. Urutan gerakan yang menghasilkannya dapat diklarifikasi (dalam urutan terbalik) dengan mengikuti tautan sebelumnya ke kondisi pembuatan. Ketika PLAY_FAST konstan disetel ke true di awal program, ia benar-benar melewatkan status sebelumnya dengan langsung menempatkan tetrimino di lapangan dan memblokirnya.

Array tiga dimensi objek negara, antrian, dan BFS dikemas ke dalam kelas. Dia memiliki metode pencarian yang menerima lapangan bermain (array dua dimensi), jenis tetrimino dan pendengar. Setiap kali keadaan terkunci terdeteksi, lapangan bermain diperbarui dengan menambahkan tetrimino ke lokasi yang sesuai. Kemudian, bidang permainan yang diubah bersama dengan informasi tentang perubahan dikirimkan ke pendengar untuk diproses. Setelah pendengar menyelesaikan pengembalian, bidang bermain dikembalikan.

Pendengar digunakan untuk menggabungkan beberapa operasi pencarian dalam sebuah rantai, yang memungkinkan untuk menemukan semua cara yang mungkin untuk menambahkan dua (atau lebih) tetriminos ke lapangan bermain. Mesin pencari pertama dalam rantai hanya mengeksekusi BFS sekali. Namun, mesin pencari kedua mengeksekusi BFS setiap kali pencarian pertama mendeteksi keadaan terkunci. Dan seterusnya, jika ada mesin pencari lain dalam rantai tersebut.

Pendengar mesin pencari terakhir mengevaluasi bidang permainan yang berubah. Ketika dia menemukan lapangan bermain lebih baik dari apa yang telah diselidiki sebelumnya, dia menuliskan objek yang digunakan dari keadaan terkunci, yang saat ini menggunakan mesin pencari pertama dalam rantai. Karena mesin pencari pertama hanya mengeksekusi BFS sekali, bidang predecessor dari objek-objek negara tetap valid hingga selesainya seluruh proses pencarian. Artinya, pendengar terakhir pada dasarnya mencatat jalur yang harus dilalui tetrimino pertama untuk mencapai konfigurasi terbaik dari lapangan permainan sebagai hasilnya.

Fungsi evaluasi

Fungsi penilaian memberi nilai pada bidang bermain yang diubah - jumlah terbobot dari berbagai parameter yang memengaruhi. Fungsi evaluasi yang digunakan dalam kasus ini didasarkan pada fungsi yang dikembangkan oleh Islam Al-Ashi . Ini menggunakan parameter berikut:

• Total jumlah baris yang dihapus : ini adalah jumlah total baris yang akan dihapus dengan penambahan dua tetriminos.
• Tinggi pemblokiran total : tinggi pemblokiran adalah ketinggian di atas lantai bidang bermain tempat gambar itu dikunci. Ini adalah jarak vertikal yang akan dikunci oleh angka yang dikunci jika Anda menghapus semua kotak yang ditempati lain dari lapangan bermain dan menjaga orientasi gambar tersebut. Tinggi pemblokiran total adalah jumlah ketinggian pemblokiran kedua tetrimino.
• Jumlah total sel "baik" : sel sumur adalah sel kosong yang terletak di atas semua sel yang ditempati dalam kolom sehingga tetangga kiri dan kanannya adalah sel yang ditempati; ketika menentukan sumur, dinding lapangan dianggap sel yang ditempati. Idenya adalah bahwa sumur adalah struktur yang terbuka di bagian atas, ditutup di bagian bawah dan dikelilingi oleh dinding di kedua sisi. Kemungkinan kesenjangan yang terputus-putus di dinding sumur berarti bahwa sel-sel sumur tidak perlu terjadi dalam tumpukan terus menerus dalam kolom.
• Total jumlah lubang di kolom : lubang di kolom adalah sel kosong yang terletak tepat di bawah sel yang ditempati. Jenis kelamin lapangan bermain tidak dibandingkan dengan sel di atasnya. Tidak ada lubang di kolom kosong.
• Jumlah total transisi dalam kolom : transisi dalam kolom adalah sel kosong yang berdekatan dengan sel sibuk (atau sebaliknya) dalam satu kolom. Kombinasi blok kolom yang ditempati paling atas dengan ruang kosong di atasnya tidak dianggap sebagai transisi. Demikian pula, lantai lapangan bermain juga tidak dibandingkan dengan sel di atasnya. Oleh karena itu, tidak ada transisi dalam kolom yang benar-benar kosong.
• Jumlah total transisi dalam baris : transisi dalam baris adalah sel kosong yang berdekatan dengan sel sibuk (atau sebaliknya) dalam baris yang sama. Sel-sel kosong di dekat dinding lapangan bermain dianggap transisi. Jumlah total dihitung untuk semua garis lapangan bermain. Namun, baris yang benar-benar kosong tidak diperhitungkan dalam jumlah total transisi.

El-Ashi menyarankan bahwa bobot yang berguna dapat ditemukan menggunakan algoritme optimasi partikel (PSO), yang secara iteratif meningkatkan serangkaian solusi dengan meniru perilaku kerumunan yang diamati di alam. Dalam kasus kami, setiap solusi adalah vektor bobot, dan kesesuaian opsi ditentukan oleh gim di Tetris; ini adalah jumlah total tetriminos di mana dia selamat sampai akhir pertandingan.

Ide-ide ini diterapkan dalam versi Java yang dijelaskan di bawah ini; ini berjalan di luar FCEUX dan dapat dikonfigurasikan untuk permainan non-grafis, di dalam memori yang berjalan pada kecepatan yang jauh lebih tinggi. Setelah menyiapkan PSO, saya terkejut melihat bahwa algoritma tidak bergerak lebih jauh setelah iterasi awal. Setelah iterasi ini, beberapa varian solusi yang dihasilkan secara acak sudah bermain cukup baik. Selama beberapa hari, ukuran set ini menurun hingga hanya satu opsi yang tersisa. Berikut adalah nilai-nilai untuk solusi ini:

Parameter	Berat
Total jumlah baris yang dihapus	1.000000000000000
Tinggi pemblokiran total	12.885008263218383
Jumlah total sel sumur	15.842707182438396
Jumlah total lubang di kolom	26.894496507795950
Jumlah total transisi dalam kolom	27.616914062397015
Garis Total Melompat	30.185110719279040

Lapangan bermain diperkirakan dengan mengalikan parameter dengan bobot masing-masing dan menambahkan hasilnya. Semakin rendah nilainya, semakin baik solusinya. Karena semua parameter dan bobot memiliki nilai positif, semua parameter membahayakan penilaian keseluruhan; masing-masing harus diminimalkan. Ini juga berarti bahwa skor terbaik adalah 0.

Karena bobot ini dipilih secara acak, kisaran nilai yang cocok bisa sangat luas. Seperangkat angka tertentu dan perkiraan kepentingan relatif dari masing-masing parameter mungkin tidak relevan. Namun demikian, akan menarik untuk memperhatikan mereka dengan seksama.

Parameter yang paling tidak berbahaya adalah jumlah baris yang dihapus. Fakta bahwa opsi ini berbahaya adalah berlawanan dengan intuisi. Tetapi tujuan utama AI adalah bertahan hidup. Dia tidak berusaha untuk mendapatkan poin terbanyak. Sebagai gantinya, ia bermain konservatif, biasanya membersihkan peringkat satu per satu. Untuk mendapatkan Double, Triple atau Tetris, Anda harus menumbuhkan banyak yang bertentangan dengan tujuan jangka panjang.

Berikutnya dalam daftar adalah tinggi total pemblokiran. Ini dapat diminimalkan dengan menurunkan tetrimino sedekat mungkin ke lantai. Ini adalah strategi sederhana yang berkontribusi dalam jangka panjang untuk bertahan hidup, dan dalam jangka pendek untuk pengemasan potongan berkualitas.

Bobot yang ditetapkan untuk jumlah total sel sumur tampaknya sedikit mengejutkan, karena pemain berpengalaman biasanya dengan sengaja membangun sumur dalam untuk mengumpulkan beberapa Tetris (kombinasi empat baris) berturut-turut. Tetapi seperti yang disebutkan di atas, ini adalah permainan yang berisiko, bertentangan dengan tujuan utama - bertahan hidup. Selain itu, jumlah sumur merupakan indikator “kekasaran” tiang. Tingkat ketidakmerataan tertentu bermanfaat ketika menempatkan angka atau kombinasi angka tertentu. Namun kekasaran yang tinggi menyebabkan kerusakan pada pengemasan yang ketat.

Jumlah total lubang di kolom adalah sekitar setengah dari jumlah total transisi dalam kolom. Parameter ini dapat digabungkan dan diciutkan menjadi parameter terkait umum, memperoleh parameter yang lebih luas dan paling berbahaya: jumlah total transisi.

Daerah padat memiliki sejumlah transisi ke segala arah. Oleh karena itu, strategi utama, didorong oleh kecerdasan buatan, dapat secara singkat dijelaskan sebagai berikut: kemas potongan-potongan sedekat mungkin satu sama lain.

Pilihan lain

Berikut adalah daftar beberapa parameter lagi yang saya coba selama pengembangan AI:

• Tinggi tumpukan : blok yang sibuk dapat menggantung di atas sel kosong, menciptakan tonjolan dan lubang; Namun, tidak mungkin untuk mengunci blok yang ditempati di atas garis yang benar-benar kosong. Oleh karena itu, ketinggian tumpukan adalah jumlah baris yang mengandung setidaknya satu blok sibuk.
• Total jumlah kolom yang ditempati : ini adalah jumlah kolom yang mengandung setidaknya satu sel yang ditempati.
• Total jumlah sel yang ditempati : jumlah sel yang ditempati di lapangan bermain.
• Total jumlah area yang terhubung : algoritma pengisian digunakan di sini untuk menghitung jumlah area yang terhubung secara terus-menerus. Selain menemukan "pulau-pulau" yang diduduki, ia menemukan lubang yang membentang di kedua sumbu.
• Penyebaran tinggi kolom : Ini adalah ukuran statistik dari variasi ketinggian kolom. Ini merupakan indikator kekasaran permukaan.
• Nilai adaptasi total : menghitung nilai adaptasi heap untuk gambar tak dikenal berikutnya. Ini menghitung jumlah total cara di mana 7 jenis bentuk dapat ditambahkan ke lapangan bermain tanpa munculnya lubang baru. Untuk penghitungan yang akurat, diperlukan penggunaan BFS berulang kali. Tetapi untuk perhitungan perkiraan, pohon pencarian bisa sangat terpotong.
• Peringkat rata-rata untuk gambar berikutnya : parameter ini memperdalam pencarian dengan menganalisis semua kemungkinan untuk angka yang tidak diketahui berikutnya. Ini menggunakan parameter lain untuk memisahkan lokasi masing-masing jenis angka, dan kemudian mengembalikan rata-rata untuk 7 peringkat. Untuk setiap penempatan gambar, BFS diperlukan.
• Game simulasi rata-rata : parameter mensimulasikan serangkaian game di Tetris, memilih game menggunakan generator nomor pseudo-acak sendiri dan menggunakan AI untuk bekerja dengannya. Di akhir setiap pertandingan, lapangan bermain dievaluasi menggunakan parameter lain. Nilai rata-rata untuk semua batch dikembalikan.

Semua parameter dapat disesuaikan dengan menambahkan faktor khusus. Misalnya, alih-alih hanya menghitung baris yang dihapus, Anda dapat menetapkan bobot Anda sendiri untuk Single, Double, Triple dan Tetris, yang mensimulasikan sistem titik. Jika pembersihan beberapa baris secara bersamaan merusak tujuan jangka panjang untuk bertahan hidup, maka baris tunggal dapat diberi bobot negatif, sementara yang lain bisa menjadi positif.

Faktor lain yang bermanfaat adalah nilai offset. Sebagai contoh, permukaan tumpukan rata yang sempurna memiliki dispersi ketinggian kolom 0. Tetapi permukaan yang rata sempurna tidak beradaptasi dengan S dan Z, serta kombinasi bentuk lainnya. Oleh karena itu, dengan mengurangi konstanta, varians harus dipusatkan di sekitar kekasaran optimal.

Parameter yang disesuaikan dan bias dapat dinaikkan ke tingkat tertentu sehingga sebelum menghitung jumlah tertimbang mereka dapat menskalakan logaritmik atau eksponensial. Semua probabilitas ini dapat dianggap sebagai bobot tambahan yang berpotensi dioptimalkan dengan metode seperti PSO.

Banyak parameter memberikan pemahaman tentang seberapa baik tumpukan dapat menangani potongan tambahan, misalnya, yang berhubungan dengan kekasaran permukaan, tetapi “Jumlah total adaptasi”, “Nilai rata-rata dari gambar berikutnya” dan “Permainan simulasi rata-rata” mengevaluasi bidang permainan yang diubah memasukkan angka yang tidak termasuk dalam dua yang diketahui. Dalam studi angka-angka berikutnya, karena eliminasi seri yang cepat, jumlah pengetahuan tambahan yang diperoleh berkurang dengan kedalaman. Ini berarti bahwa masa lalu yang panjang dari partai tidak begitu penting, dan jalannya partai di masa depan yang jauh juga tidak terlalu penting. Bahkan, jika urutan angka pendek secara acak salah, maka AI dengan cepat mengembalikan permainan, menggunakan beberapa angka berikut untuk menghapus baris yang terpengaruh. Menentukan nilai optimal untuk analisis angka-angka selanjutnya membutuhkan penelitian lebih lanjut.

Aspek lain dari kegunaan parameter adalah biaya komputasi. Biaya sangat meningkat karena fungsi evaluasi dipanggil untuk setiap kemungkinan penempatan dua angka. Karena AI harus dapat memainkan Tetris dalam waktu nyata, faktor biaya yang memberikan informasi berharga dapat ditukar dengan teknik perkiraan lainnya yang berjalan lebih cepat.

Pelatihan AI

Ada urutan patologis yang dapat menyebabkan Game Over, terlepas dari strategi. Contoh paling sederhana adalah urutan tiada akhir dari tetrimino S dan Z, yang, seperti yang ditunjukkan dalam animasi, dengan cepat menyebabkan AI hilang.


Karena dibutuhkan beberapa hari untuk menjalankan varian AI sebelum menyelesaikan beberapa batch dan menghitung rata-rata, maka sama sekali tidak praktis untuk menggunakan durasi batch rata-rata sebagai metrik kontrol PSO. Sebagai gantinya, Anda dapat meningkatkan kompleksitas gim dengan kecepatan terkontrol dengan meningkatkan frekuensi S dan Z, yang seiring waktu akan mengarah pada penciptaan alternatif dari hanya sepasang angka ini.

Saya mencoba menggunakan metode pengajaran ini, tetapi menemukan bahwa mengajar AI untuk bekerja dengan S dan Z sering benar-benar membahayakan kemampuan untuk mengatasi bentuk acak yang didistribusikan secara merata.

Dalam metode alternatif yang terinspirasi oleh game B-Type, metrik PSO mengontrol frekuensi pembersihan baris. Lapangan bermain adalah diagram 10-baris dari blok-blok sampah acak, dan setiap kali garis tersebut dihapus, garis-garis sampah baru muncul di bawah, memulihkan ketinggian tumpukan. Karena lapangan bermain memiliki lebar 10 kolom, dan rata-rata setiap tetrimino terdiri dari 4 kotak, AI harus menghapus setiap baris setiap 2,5 tetrimino. Dan untuk menghilangkan sampah, dia harus melakukannya lebih cepat lagi.

Sayangnya, teknik ini juga tidak meningkatkan kinerja. Salah satu alasan yang mungkin adalah bahwa lubang sampah acak tidak benar-benar cocok dengan string yang ditangani AI dalam permainan nyata. Selain itu, membersihkan baris adalah tujuan jangka pendek; pembersihan baris serakah tidak selalu meningkatkan kelangsungan hidup jangka panjang. Dari waktu ke waktu, baris tidak boleh disentuh untuk memproses kombinasi angka-angka berikutnya.

Colin Fei menyarankan pendekatan berbeda di halaman web-nya. Dia menciptakan histogram yang menunjukkan persentase bentuk yang diblokir di setiap baris selama lot percobaan. Menariknya, semua histogram terlihat hampir identik terlepas dari jumlah angka yang dibuat. Berdasarkan hal ini, ia menyarankan agar Anda dapat menggunakan gambar perkiraan fungsi untuk kumpulan percobaan saat mengevaluasi ekspektasi statistik untuk memblokir angka di garis kreasi, sehingga mendapatkan waktu selama AI akan bermain sampai akhir permainan. Saya memutuskan untuk mengeksplorasi kemungkinan ini.

Di bawah ini adalah peta panas dari banyak batch percobaan, secara total mengandung 2.039.900.000 tetrimino. Setiap sel diwarnai berdasarkan persentase bentuk yang terkunci di dalamnya. Untuk meningkatkan kontras visual, palet non-linear dipilih. Peta dibuat dengan menormalkan nilai sel dengan membaginya dengan persentase sel maksimum, dan kemudian mengumumkan hingga kekuatan 0,19 (lihat "koreksi gamma" ).

Warna Persentase ■ 0.00000000 ■ 0.00000315 ■ 0.00024227 ■ 0.00307038 ■ 0.01860818 ■ 0.07527774 ■ 0.23582574 ■ 0.61928352 ■ 1.42923040 ■ 2.98867416 ■ 5.78182519

Garis-garis oranye dan merah gelap di garis 17 dan 18 berarti bahwa sebagian besar angka berakhir di sana. Rona hijau pucat dari bawah adalah konsekuensi dari geometri angka-angka: hanya 4 dari 7 jenis tetrimino yang dapat muncul di garis bawah. Sudut bawah berwarna hitam karena tidak mungkin untuk sampai ke sana.

Warna di sepanjang setiap garis hampir seragam, dan ini menunjukkan bahwa bentuknya didistribusikan secara horizontal secara merata. Kesenjangan kecil dapat dijelaskan dengan melihat histogram dari masing-masing jenis bentuk:

T

J

Z

O

S

L.

Saya

T ternyata menjadi tipe yang paling universal: histogramnya lebih seragam daripada yang lainnya. Anomali dalam histogram J - hasil dari pengaruh dinding; hanya Jr dan Jl dapat berada di kolom samping, yang membuat AI menggunakan kolom 1 dan 9 lebih sering untuk mengkompensasi. Hal yang sama berlaku untuk L. Histogram Z dan S terlihat kurang lebih sama, yang menekankan ketidakseimbangan karena fakta bahwa Zv dan Sv bukan gambar cermin sempurna satu sama lain. Tipe O terbatas pada bidang bermain 19 × 9, dan sepertinya AI lebih cenderung menggunakan O di sisi daripada di tengah. Tetrimino I bergeser ke kanan, karena titik awalnya terletak di sana; oleh karena itu, mengunci di kolom 1 jarang terjadi.

Tabel menunjukkan persentase angka yang diblokir di setiap baris.

Tali	Persentase
0	0,0000000000
1	0,0000000000
2	0,0000004902
3	0,0000026472
4	0,0000066180
5	0,0000172557
6	0,0000512280
7	0,0001759400
8	0,0006681210
9	0,0023187901
10	0,0077928820
11	0,0259672043
12	0,0866187068
13	0,2901315751
14	0,9771663807
15	3.3000408353
16	10.6989059268
17	28.5687976371
18	50.0335706162
19	6.0077671454

Berikut adalah grafik nilai-nilai:


Jika baris 19 tidak diperhitungkan, maka grafik menunjukkan pertumbuhan eksponensial.

Berikut ini adalah daftar rasio jumlah bentuk terkunci di baris yang berdekatan.

String A / String B	Rasio (%)
1/2	0,00
2/3	18.52
3/4	40.00
4/5	38.35
5/6	33.68
6/7	12/29
7/8	26.33
8/9	28.81
9/10	29,76
10/11	01/30
11/12	29,98
12/13	29.85
13/14	29.69
14/15	29.61
15/16	30.84
16/17	37.45
17/18	57.10
18/19	832.81

Garis-garis 16–19memperhitungkan angka-angka yang berinteraksi dengan lantai lapangan bermain, sehingga mereka dapat dibuang. Dalam baris, 0–5pemilihannya terlalu kecil untuk bermakna. Rasio yang tersisa, pasangan 6 / 7-14 / 15, hampir identik; nilai rata-rata mereka adalah 29,24%. Ini berarti bahwa kemungkinan timbunan tumbuh oleh satu garis kira-kira sama terlepas dari tinggi timbunan. Ini logis, karena aturan Tetris membatasi interaksi di bagian atas tumpukan ketika itu padat.

Grafik berikut menunjukkan log ₁₀ persen dari angka di baris 6-15.


Itu dekat dengan garis lurus sempurna dengan koefisien determinasi mendekati 1 . Rumus yang berasal dari regresi linier yang ditunjukkan di atas memberi kita persimpangan dengan sumbu Y, dengan asumsi bahwa persentase bentuk di baris 0 adalah sekitar 10 ^−7,459 %. Kebalikan dari nilai ini memberi kita harapan statistik dari 2.877.688.349 tetrimino atau 1.151.175.340 baris sampai akhir pertandingan.

Ini membuat kita mengerti bahwa log ₁₀persentase angka di setiap garis tetap linier hingga garis 0. Namun, ketika tumpukan hampir mencapai langit-langit lapangan permainan, kebebasan bergerak dibatasi sedemikian rupa sehingga properti ini dilanggar. Selain itu, memblokir bagian pada baris 0 tidak berarti game over; Anda masih bisa diselamatkan jika ada tempat untuk membuat angka baru.

Cara lain untuk menilai kekuatan AI adalah untuk mengukur jumlah rata-rata bentuk yang dibuat antara pembersihan penuh dari lapangan bermain. Pembersihan lengkap dapat diperoleh hanya dengan 5 tetriminos. Misalnya, di antara kemungkinan-kemungkinan lain, ini dapat dicapai dengan lima angka O yang diletakkan di lantai lapangan bermain.Secara umum, karena setiap tetrimino terdiri dari 4 kotak dan lebar lapangan bermain adalah 10 kotak, jumlah angka yang dibuat antara pembersihan penuh harus kelipatan 5 ( sejak itu4 × 5n = 2 × 10n ).

AI saya memiliki jumlah rata-rata bentuk yang dibuat antara pembersihan lapangan penuh 1.181 - jumlah yang cukup kecil. Karena pembersihan penuh adalah seperti memulai kembali game, batch penuh dapat dilihat sebagai seri restart game yang sangat panjang, diikuti dengan kemajuan cepat ke game over. Seperti urutan alternatif yang dijelaskan di atas SZ, urutan patologis yang mengarah ke akhir permainan biasanya sangat singkat.

Histogram di bawah ini menunjukkan probabilitas (dalam persen) bahwa AI akan mencapai pembukaan lapangan setelah jumlah angka yang dibuat.


Urutan derajat dalam formula di atas menentukan laju penurunan dan, mungkin, kekuatan AI. Menurut rumus ini, sekitar 0,4%, atau sekitar 1 dari 253 pertandingan dimulai dengan lapangan kosong, berakhir dengan pembersihan lengkap setelah hanya 5 tetriminos.

Berbeda dengan apa yang disarankan Faye, konstanta dalam pendekatan linier dan eksponensial membutuhkan ukuran sampel yang sangat besar sehingga R ²mendekati 1, jadi metode ini tidak berlaku untuk PSO. Namun, konstanta yang diperoleh dengan batch panjang dapat digunakan untuk mengoptimalkan fungsi aproksimasi yang menciptakan kemungkinan nilai konstan untuk batch pendek. Dalam semacam loop umpan balik pengembangan, fungsi perkiraan yang dioptimalkan dapat digunakan dalam PSO, yang meningkatkan AI, yang pada gilirannya dapat digunakan untuk menghitung konstanta baru, yang berfungsi sebagai kriteria referensi untuk fungsi aproksimasi.

Versi Java

Tentang program ini

Untuk pengembang yang tidak terbiasa dengan Lua, saya menambahkan port Java AI ke file zip sumber . Kelas adalah terjemahan baris-demi-baris dari objek Lua berdasarkan penutupan .

Paket

Kode ini dibagi menjadi dua paket:

• tetris.ai berisi kelas dan antarmuka AI.
• tetris.gui menciptakan model grafis dari lapangan bermain.

Kelas dan antarmuka AI

Kelas dengan nama yang sesuai Tetriminosmenggambarkan tetrimino. Ini digunakan dengan cara yang sama enumdan mengandung konstanta untuk semua jenis tetrimino:

 public static final int NONE = -1; public static final int T = 0; public static final int J = 1; public static final int Z = 2; public static final int O = 3; public static final int S = 4; public static final int L = 5; public static final int I = 6; 

NONEberarti nilai yang belum ditetapkan. Ini digunakan untuk sel-sel kosong dari lapangan bermain.

Juga Tetriminosberisi dua model tabel orientasi. PATTERNS- ini adalah array bilangan bulat 4 dimensi (tipe × rotasi × ​​kuadrat × koordinat) yang berisi koordinat relatif kuadrat; garis-garis diatur sedemikian rupa sehingga pada setiap jenis orientasi penciptaan bentuk adalah yang pertama. ORIENTATIONSAdalah model lain, array 2 dimensi (tipe × rotasi) objek Orientation. Masing Orientation- masing berisi koordinat bujur sangkar sebagai larik objek Point. Ini juga memiliki bidang yang menggambarkan kisaran posisi yang diizinkan untuk orientasi yang sesuai.

 public class Orientation { public Point[] squares = new Point[4]; public int minX; public int maxX; public int maxY; ... } 

 public class Point { public int x; public int y; ... } 

Rotasi tetrimino (indeks kedua di kedua tabel orientasi) digunakan dalam objek Stateyang dimanipulasi BFS.

 public class State { public int x; public int y; public int rotation; public int visited; public State predecessor; public State next; ... } 

x, ydan rotationbersama - sama menggambarkan posisi dan orientasi gambar. Karena tipe Tetrimino tetap konstan dari saat penciptaan hingga pemblokiran, bidang untuk itu adalah opsional.

Kelas Searcheryang berisi algoritma BFS membuat set lengkap semua objek yang mungkin Stateketika dibuat:

 private void createStates() { states = new State[AI.PLAYFIELD_HEIGHT][AI.PLAYFIELD_WIDTH][4]; for(int y = 0; y < AI.PLAYFIELD_HEIGHT; y++) { for(int x = 0; x < AI.PLAYFIELD_WIDTH; x++) { for(int rotation = 0; rotation < 4; rotation++) { states[y][x][rotation] = new State(x, y, rotation); } } } } 

Meskipun Java memiliki API Koleksi kaya, ini Searcherberisi implementasi antrian sendiri. Kelas Queuedigunakan State.nextuntuk menggabungkan objek Stateke dalam daftar tertaut. Karena semua objek Statesudah ditentukan sebelumnya, dan masing-masing Statedapat ditambahkan ke antrian tidak lebih dari sekali, antrian dapat bekerja di tempat, yang menghilangkan kebutuhan untuk objek kontainer sementara yang tidak perlu digunakan dalam implementasi antrian umum.

"Jantung" BFS adalah metode yang ditunjukkan di bawah ini search.

 public boolean search(int[][] playfield, int tetriminoType, int id) { int maxRotation = Tetriminos.ORIENTATIONS[tetriminoType].length - 1; int mark = globalMark++; if (!addChild(playfield, tetriminoType, mark, null, 5, 0, 0)) { return false; } while(queue.isNotEmpty()) { State state = queue.dequeue(); if (maxRotation != 0) { addChild(playfield, tetriminoType, mark, state, state.x, state.y, state.rotation == 0 ? maxRotation : state.rotation - 1); if (maxRotation != 1) { addChild(playfield, tetriminoType, mark, state, state.x, state.y, state.rotation == maxRotation ? 0 : state.rotation + 1); } } addChild(playfield, tetriminoType, mark, state, state.x - 1, state.y, state.rotation); addChild(playfield, tetriminoType, mark, state, state.x + 1, state.y, state.rotation); if (!addChild(playfield, tetriminoType, mark, state, state.x, state.y + 1, state.rotation)) { lockTetrimino(playfield, tetriminoType, id, state); } } return true; } 

Ini memunculkan antrian dengan keadaan tetrimino yang dibuat, dan kemudian secara berurutan mengambil elemen anak dari status yang dihapus dari antrian, menambahkan mereka kembali ke antrian ketika mereka muncul di lapangan bermain. Bidang permainan yang berisi kombinasi sel sibuk dan kosong, tipe Tetrimino yang dibuat, dan pengidentifikasi sewenang-wenang diteruskan ke

metode search. Selama pelaksanaan BFS, seorang pendengar dipanggil setiap kali posisi kunci terdeteksi.

 public interface ISearchListener { public void handleResult(int[][] playfield, int tetriminoType, int id, State state); } 

Pendengar menerima bidang bermain yang diubah yang berisi tetrimino terkunci di tempatnya. Jenis Tetrimino yang dibuat dan pengidentifikasi arbitrer juga ditransmisikan. Parameter terakhir adalah Statedi mana tetrimino diblokir. Dengan mengikuti rantai tautan State.predecessor, Anda dapat memulihkan sepenuhnya kembali ke Statemembuat bentuk.

State.visiteddapat diimplementasikan sebagai boolean; tapi dengan semua fasilitas yang diperlukan untuk memilah-milah sebelum mencari Stateuntuk bantuan visitedpada false. Sebaliknya, saya membuat visitednilai intdibandingkan dengan penghitung, bertambah dengan setiap panggilan.

MetodeaddChildpra-antrian keadaan selanjutnya. Keadaan berikutnya harus berada di dalam bidang dan terletak di 4 sel kosong dari lapangan bermain. Selain itu, negara bagian berikutnya harus dikunjungi State. Jika posisi itu valid, addChildkembalikan truebahkan jika negara bagian berikutnya tidak dapat antri karena sudah dikunjungi.

Metode ini searchmenggunakan nilai kembali addChilduntuk menentukan apakah suatu bentuk dapat dibuat. Jika angka tidak dapat dibuat, maka tumpukan telah mencapai bagian atas dan pencarian tidak lagi dapat dilakukan; karena itu ia kembali false.

DikembalikanaddChildSignifikansi juga sedang dipelajari untuk kemungkinan turun langkah lain. Jika ini tidak dapat dilakukan, maka keadaan saat ini adalah posisi kunci dan panggilan dimulai lockTetrimino. Metode ini lockTetriminomengubah bidang bermain, memanggil pendengar, dan kemudian mengembalikan bidang bermain.

Setiap baris array playfieldberisi 1 elemen tambahan, yang menyimpan jumlah sel yang ditempati di baris. Menambah elemen dilakukan dengan metode ini lockTetriminokarena menandai sel sebagai sibuk.

Ketika pendengar menerima lapangan bermain yang dimodifikasi, ia memanggilPlayfieldUtil.clearRowsUntuk menghapus baris yang diisi metode mengenalinya dengan memeriksa nilai dalam elemen tambahan dari array. Untuk menghapus string, kode memanfaatkan fakta bahwa di Jawa, array dua dimensi pada dasarnya adalah array array; itu hanya menekan tautan ke string. PlayfieldUtilmengandung garis bebas; dia menyelesaikan proses pembersihan dengan memasukkan tautan ke salah satunya. Sebelum melakukan shift, indeks baris yang dihapus disimpan dalam elemen baris tambahan. Kemudian tautan ke garis didorong ke tumpukan.

Kemudian pendengar memanggilPlayfieldUtil.restoreRowsuntuk membuang perubahan yang dilakukan ke lapangan bermain. Langkah-langkah dibatalkan dalam urutan terbalik. Pertama, kita mendapatkan baris gratis dari atas. Kemudian, baris yang diisi diambil dari tumpukan dan indeks dari elemen tambahan dipulihkan. Ini digunakan untuk menggeser referensi garis dan untuk kembali ke tempat baris yang dihapus. Akhirnya, elemen tambahan dikembalikan, ia diberi nilai lebar lapangan bermain - jumlah sel yang ditempati di baris yang diisi.

Ada PlayfieldUtiljuga metode evaluatePlayfieldyang menghitung dan menulis 4 parameter evaluasi ke dalam kelas wadah yang ditunjukkan di bawah ini.

 public class PlayfieldEvaluation { public int holes; public int columnTransitions; public int rowTransitions; public int wells; } 

Kelas mengelola semua ini AI. Ini berisi dua objek yang Searcherterhubung bersama oleh pendengar yang ditunjukkan di bawah ini.

 public void handleResult( int[][] playfield, int tetriminoType, int id, State state) { if (id == 0) { result0 = state; } Orientation orientation = Tetriminos.ORIENTATIONS[tetriminoType][state.rotation]; int rows = playfieldUtil.clearRows(playfield, state.y); int originalTotalRows = totalRows; int originalTotalDropHeight = totalDropHeight; totalRows += rows; totalDropHeight += orientation.maxY - state.y; int nextID = id + 1; if (nextID == tetriminoIndices.length) { playfieldUtil.evaluatePlayfield(playfield, e); double fitness = computeFitness(); if (fitness < bestFitness) { bestFitness = fitness; bestResult = result0; } } else { searchers[nextID].search(playfield, tetriminoIndices[nextID], nextID); } totalDropHeight = originalTotalDropHeight; totalRows = originalTotalRows; playfieldUtil.restoreRows(playfield, rows); } 

Kelas AIdapat menangani sejumlah objek Searcher, tetapi Nintendo Tetris hanya menunjukkan satu bentuk di muka. Objek Searcherdisimpan dalam array, dan kode yang ditunjukkan di atas berfungsi sebagai pendengar umum mereka. Pengidentifikasi acak yang diteruskan ke metode Searcher.searchsebenarnya adalah indeks array, yang juga merupakan kedalaman pencarian. Ketika pendengar dipanggil, pengenal mengarahkan panggilan ke yang berikutnya Searcherdalam rantai. Jika ia mencapai akhir array, maka evaluasi bidang bermain. Dan ketika dia menemukan lapangan bermain dengan skor kebugaran yang lebih tinggi, dia menuliskan yang diblokir Statedari yang pertama Searcherdalam rantai.

AIberisi metode searchyang menerima lapangan bermain dan array yang berisi jenis tetrimino yang dibuat dan berikutnya. Dia kembaliStateberisi posisi dan rotasi di mana tetrimino pertama harus diblokir. Dia tidak fokus pada tetrimino kedua; pada saat dipanggil, itu menghitung ulang skor. Jika tumpukan terlalu tinggi dan rantai Searchergagal menempatkan kedua tetrimino, maka itu AI.searchakan kembali null.

 public State search(int[][] playfield, int[] tetriminoIndices) { this.tetriminoIndices = tetriminoIndices; bestResult = null; bestFitness = Double.MAX_VALUE; searchers[0].search(playfield, tetriminoIndices[0], 0); return bestResult; } 

Tantangan AI

Karena versi Java tidak terikat dengan FCEUX, ini berpotensi dapat digunakan untuk proyek lain. Bagi mereka yang tertarik untuk mengintegrasikan AI di tempat lain, bagian ini menjelaskan semua yang Anda butuhkan.

Pertama, buat sebuah instance AI, instance, PlayfieldUtildan array untuk menampung semua jenis tetrimino yang diketahui. Selain itu, buat PlayfieldUtil.createPlayfieldinstance lapangan bermain dengan memanggil ; mengembalikan array dua dimensi dengan kolom tambahan, yang kami periksa di atas. Anda mungkin juga membutuhkan generator angka acak.

 AI ai = new AI(); PlayfieldUtil playfieldUtil = new PlayfieldUtil(); int[] tetriminos = new int[AI.TETRIMINOS_SEARCHED]; int[][] playfield = playfieldUtil.createPlayfield(); Random random = new Random(); 

Awalnya, lapangan bermain kosong, dan semua sel relevan Tetriminos.NONE. Jika Anda mengisi sel secara terprogram, maka jangan lupa untuk menuliskan playfield[rowIndex][AI.PLAYFIELD_WIDTH]jumlah sel yang ditempati di setiap baris.

Isi larik jenis tetrimino dengan jenis bentuk yang awalnya dibuat dan bentuk berikutnya, yang biasanya dipilih secara manual.

 tetriminos[0] = random.nextInt(7); tetriminos[1] = random.nextInt(7); 

Lalu kami melewati bidang bermain dan array tipe ke metode AI.search. Dia akan kembali Statedi mana Anda perlu memblokir tetrimino pertama. Jika dia kembali null, maka game over tidak bisa dihindari.

 State state = ai.search(playfield, tetriminos); 

Jika Anda membutuhkan cara dari membuat gambar hingga mengunci, maka meneruskannya ke Statemetode AI.buildStateList.

 State[] states = ai.buildStatesList(state); 

Untuk memperbarui lapangan bermain, kami akan meneruskannya PlayfieldUtil.lockTetriminobeserta jenis dan objeknya State. Metode ini secara otomatis menghapus baris yang diisi.

 playfieldUtil.lockTetrimino(playfield, tetriminos[0], state); 

Sebelum menelepon lagi, AI.searchAnda perlu secara acak memilih tetrimino berikutnya.

 tetriminos[0] = tetriminos[1]; tetriminos[1] = random.nextInt(7); 

Bersama-sama, ini terlihat seperti ini:

 AI ai = new AI(); PlayfieldUtil playfieldUtil = new PlayfieldUtil(); int[] tetriminos = new int[AI.TETRIMINOS_SEARCHED]; int[][] playfield = playfieldUtil.createPlayfield(); Random random = new Random(); tetriminos[0] = random.nextInt(7); tetriminos[1] = random.nextInt(7); while(true) { // ... print playfield ... State state = ai.search(playfield, tetriminos); if (state == null) { break; // game over } playfieldUtil.lockTetrimino(playfield, tetriminos[0], state); tetriminos[0] = tetriminos[1]; tetriminos[1] = random.nextInt(7); } 

Alih-alih menampilkan bidang bermain dalam bentuk teks, Anda dapat menggunakan cara yang lebih menarik untuk menampilkan apa yang terjadi ...

Tampilan bidang bermain

Kelas TetrisFramemeniru grafis Nintendo Tetris, termasuk fitur perilaku yang dijelaskan pada bagian sebelumnya dari artikel.


Untuk melihatnya beraksi, jalankan tetris.gui.Main. Seperti halnya versi Lua, kita dapat menyesuaikan kecepatan game dengan mengubah nilai konstan di awal file.

 public static final boolean PLAY_FAST = true; 

TetrisFramememiliki 4 metode untuk memanipulasi layar. Metode ini displayTetriminomembuat tetrimino aktif dalam koordinat yang ditentukan. Ini menerima parameter penundaan, yang menyebabkan metode menunggu sebelum mengembalikan jumlah frame animasi yang ditentukan.

 public void displayTetrimino(int type, int rotation, int x, int y, int delay) 

Metode ini lockTetriminomengunci gambar pada tempatnya. Penghitung baris, titik, level, dan warna tetrimino diperbarui sesuai, menunjukkan perilaku penasaran yang diharapkan ketika nilai melebihi nilai yang diizinkan. Menetapkan animatenilai ke parameter truemencakup animasi pembersihan baris dan kerlipan layar saat menerima Tetris. Metode ini diblokir sampai animasi selesai.

 public void lockTetrimino(int type, int rotation, int x, int y, boolean animate) 

updateStatisticsAndNext melakukan penambahan penghitung statistik untuk tetrimino yang baru dibuat dan memperbarui tampilan gambar berikutnya.

 public void updateStatisticsAndNext(int activeTetrimino, int nextTetrimino) 

Metode ini dropTetriminomenciptakan bentuk dan memungkinkannya untuk turun di bawah pengaruh "gravitasi", tanpa membuat upaya untuk memutar atau memindahkannya. Mainmenggunakannya untuk dua angka terakhir ketika AI.searchkembali null. Jika parameter animatepenting true, maka jika tidak mungkin untuk membuat angka, tirai akhir permainan akan turun. Seperti semua metode lain, metode ini memblokir hingga animasi selesai. Ini kembali truehanya ketika itu dapat membuat angka di lapangan bermain yang sibuk.

 public boolean dropTetrimino(int type, boolean animate) 

4 metode ini harus dipanggil oleh alur kerja, tetapi TetrisFrameharus dibuat di Thread Pengiriman Acara itu sendiri. Untuk melihat bagaimana ini dilakukan, lihat kelas Main.

Demi kepentingan, ia Mainmenggunakan kelas Randomizeryang mensimulasikan pseudo-random number generator dari Nintendo Tetris.

Paket ini tetris.gui.imagesberisi file terkait tampilan. tiles.png- Ini adalah tabel pola yang berisi semua grafik ubin. background.datmenyimpan pengidentifikasi ubin yang membentuk latar belakang; data diekstraksi dari $BF3F. Dan itu colors.datberisi byte yang menghasilkan warna kotak yang tidak biasa yang muncul dari level 138. Ini

ImageLoaderberisi tabel palet NES, dan ImagePaneset lengkap nilai level yang ditampilkan disimpan.

Proyek lainnya

Berpotensi, kode dapat digunakan alih-alih menulis untuk mode demo. Bahkan, demo seperti itu dapat dilakukan selamanya, mengambil keuntungan dari seberapa cepat AI mampu membersihkan seluruh lapangan bermain. Untuk mencapai hal ini, dalam generator angka pseudo-acak, Anda perlu menggunakan konstanta arbitrer sebagai seed, yang akan memberi kami urutan tetrimino deterministik. Dua urutan tetrimino pertama akan direkam. Ketika AI mencapai pembersihan lapangan penuh, dua tetriminos berikutnya akan dibandingkan dengan dua urutan pertama. Jika mereka cocok (acara ini diharapkan setiap 49 pembersihan lapangan penuh), maka generator angka acak semu dapat dilewati konstan yang sama dengan seed, yang akan membuat loop demo tanpa batas. Durasi siklus bisa sangat lama untuk menyembunyikan fakta bahwa itu adalah siklus. Jugademo dapat dimulai pada titik acak di loop, membuat demo baru setiap kali.

Kemungkinan lain menggunakan AI adalah untuk membuat mode "pemain versus komputer". Dalam Tetris multi-pemain, saat membersihkan beberapa garis pada saat yang sama, garis sampah muncul di bagian bawah bidang lawan, meningkatkan lapangan bermain. AI harus dapat melindungi dirinya sendiri dari puing-puing dengan alasan yang sama bahwa ia dapat memainkan game Tipe-B. Namun, seperti yang dinyatakan sebelumnya, AI bermain secara konservatif, biasanya berusaha untuk menghapus satu baris pada satu waktu. Artinya, ia akan dapat mempertahankan diri dari serangan, tetapi ia tidak dapat menyerang. Untuk dapat mengubah perilakunya, saya membuat antarmuka yang disebut IChildFilter.

 public interface IChildFilter { public boolean validate(int[][] playfield, int tetriminoType, int x, int y, int rotation); } 

AImemiliki konstruktor alternatif yang mendapat implementasi IChildFilter. Jika tersedia, IChildFilter.validateini berfungsi sebagai pemeriksaan tambahan untuk izin negara anak; jika kembali false, maka status anak tidak antri.

WellFilterMerupakan implementasiIChildFilterditujukan untuk mengambil empat baris (Tetris). Seperti pemain yang hidup, dia secara bertahap membangun sumur di kolom paling kanan dari lapangan bermain, naik baris demi baris dari bawah ke atas. Karena ini bekerja baris demi baris, ia menolak status anak yang menambahkan kotak ke kolom paling kanan. Ketika seluruh baris, dengan pengecualian kolom sumur, benar-benar penuh, AI melanjutkan ke baris berikutnya. Ketika 4 atau lebih dari garis-garis ini siap, itu memungkinkan "tongkat" jatuh ke dalam sumur dan mendapatkan Tetris. Selain itu, ketinggian tumpukan dilacak; jika terlalu besar, maka tidak WellFilterlagi mempengaruhi AI.


Untuk mengujinya dalam operasi, buat Mainperubahan berikut:

 AI ai = new AI(new WellFilter()); 

WellFilterbekerja, tetapi tidak terlalu efektif. Berisi heuristik sederhana yang dirancang untuk menunjukkan konsep. Untuk mendapatkan Tetris lebih sering, Anda perlu menggunakan strategi yang lebih canggih, mungkin salah satu yang dapat dioptimalkan menggunakan PSO.

Selain itu, Anda dapat menggunakan pemfilteran status anak untuk menghasilkan pola. Di bawah ini adalah contoh dari apa yang dia mampu PatternFilter.


PatternFilterBuat gambar garis demi garis dari bawah ke atas, mirip dengan cara kerjanya WellFilter; Namun, alih-alih mempertahankan kolom paling kanan, itu PatternFilterhanya menyetujui status anak yang sesuai dengan pola tertentu.

Konstruktor PatternFiltermendapatkan nama salah satu gambar dalam paket tetris.gui.patterns, yang digunakannya sebagai templat. Setiap gambar 20 × 10 berisi piksel hitam dan putih yang terkait dengan sel-sel di lapangan bermain.

 AI ai = new AI(new PatternFilter("tetriminos")); 

Baris kode yang ditunjukkan di atas menciptakan siluet tujuh jenis tetrimino.


Contoh lain dengan T tetrimino besar diputar pada suatu sudut.


Contoh lain. Jika Anda melihat lebih dekat, Anda akan melihat nama permainannya.


Seperti WellFilter, itu PatternFiltertidak lebih dari bukti konsep. Pola yang dia proses terbatas pada dasar lapangan karena fakta bahwa upaya untuk mendapatkannya biasanya berakhir dengan permainan berakhir. Namun, ini adalah ide yang menarik untuk diteliti lebih lanjut.

Versi Gamepad

Skrip Lua dan program Java mengabaikan gravitasi; bagi mereka, kecepatan turun tidak penting, karena tergantung pada konfigurasi, mereka baik memindahkan angka langsung ke lokasi yang diinginkan, atau menyeret sepanjang jalur yang dipilih. Di satu sisi, mereka hanya meniru Tetris, tidak memainkannya. Namun, dalam file zip dengan sumber ada skrip Lua lain yang diputar dengan menghasilkan sinyal dari tombol gamepad, yang memungkinkan game untuk mengontrol pergerakan angka, gravitasi dan segala sesuatu lainnya.

Menambahkan gravitasi sangat memperluas ruang pencarian, memaksa AI untuk memperhitungkan aturan licik memanipulasi bentuk. Detail aturan ini dijelaskan di bagian pertama artikel, dan dapat sepenuhnya dihargai dengan studi kode secara langsung. Inilah yang paling penting:

• : , .
• «» .
• «» «» .
• .
• .
• .
• .
• , .
• A B .
• «» «» 6 16 . «» «» , .
• «» 3 .
• 96 . , — .

Untuk mengakomodasi semua aturan ini, informasi historis harus disematkan di negara pencarian. Mereka membutuhkan bidang di mana jumlah frame penahan untuk setiap tombol dan jumlah frame setelah rilis otomatis terakhir akan disimpan. Setiap rangkaian nilai unik, termasuk koordinat x, ydan rotasi tetrimino mencirikan keadaan yang terpisah dan unik. Sayangnya, jumlah kemungkinan sangat besar sehingga pencarian penuh ruang ini tidak praktis. Versi AI untuk gamepad hanya mengeksplorasi sebagian saja.

AI menggunakan objek Statedengan bidang-bidang berikut:

 { x, y, rotation, Left, Right, Down, A, B, fallTimer, visited, predecessor } 

Alih-alih menggunakan pergeseran AI otomatis dalam bingkai alternatif, tekan dan lepaskan tombol shift. Karena itu, ia perlu memantau hanya kemudian apakah tombol ditekan, dan tidak berapa lama ditekan. Karena tidak ada rotasi otomatis, ide yang sama berlaku untuk tombol A dan B. Oleh karena itu lapangan Left, Right, Adan Bdapat diartikan sebagai daftar yang berisi salah satu dari nilai berikut:

 { RELEASED, PRESSED } 

Di sisi lain, untuk keturunan lembut, Anda harus menekan tombol "Turun" selama tiga frame, yang mensyaratkan adanya 4 status:

 { RELEASED, PRESSED_FOR_1_FRAME, PRESSED_FOR_2_FRAMES, PRESSED_FOR_3_FRAMES } 

Downsecara bertahap meningkat dari nilai RELEASEDke PRESSED_FOR_3_FRAMES, di mana terjadi soft descent. Setelah itu, ia dapat menerima nilai RELEASEDatau kembali ke PRESSED_FOR_2_FRAMES, menyebabkan penurunan lembut setiap frame kedua setelah penundaan awal. Itu tidak bisa RELEASEDdari PRESSED_FOR_1_FRAMEatau dari PRESSED_FOR_2_FRAMES.

Sebenarnya, kode Lua menggunakan konstanta integer, tetapi prinsipnya sama.

Demikian pula, visiteddan predecessor, fallTimeritu ditugaskan nilai yang diperoleh saat menulis di negara anak antrian; itu fallTimerakan menjadi satu lebih dari nilai negara induk. Kondisi yang mengandungfallTimer, sama dengan kecepatan descent, menyiratkan bahwa descent otomatis terjadi pada frame ini, dan untuk keadaan selanjutnya dari state ini nilainya fallTimerakan 0.

Setiap Searcherpre-mendefinisikan 8-array yang berisi semua state yang mungkin ( 20 × 10 × 4 × 2 × 2 × 4 × 2 A × 2 B), dan BFS dieksekusi sama dengan metode yang ditunjukkan untuk array. Pseudo-code yang ditunjukkan di bawah ini menjelaskan bagaimana status selanjutnya diperoleh dari status diam.

 Slide = (Left == PRESSED) or (Right == PRESSED) Rotate = (A == PRESSED) or (B == PRESSED) if Down == RELEASED or Down == PRESSED_FOR_3_FRAMES then if Down == RELEASED then nextDown = PRESSED_FOR_1_FRAME else nextDown = PRESSED_FOR_2_FRAMES end addChild(Down = nextDown) if not Rotate then addChild(A = PRESSED, Down = nextDown) addChild(B = PRESSED, Down = nextDown) end if Slide then addChild() if not Rotate then addChild(A = PRESSED) addChild(B = PRESSED) end else addChild(Left = PRESSED) addChild(Right = PRESSED) if not Rotate then addChild(Left = PRESSED, A = PRESSED) addChild(Left = PRESSED, B = PRESSED) addChild(Right = PRESSED, A = PRESSED) addChild(Right = PRESSED, B = PRESSED) end end else if Down == PRESSED_FOR_1_FRAME then nextDown = PRESSED_FOR_2_FRAMES else nextDown = PRESSED_FOR_3_FRAMES end addChild(Down = nextDown) if not Rotate then addChild(A = PRESSED, Down = nextDown) addChild(B = PRESSED, Down = nextDown) end end 

Seperti yang ditunjukkan pada kode pseudo di bawah ini, fungsi addChildmemperhitungkan urutan peristiwa yang terjadi di setiap frame (misalnya, shift, rotasi, dan keturunan).

 nextFallTimer = fallTimer + 1 if Left == PRESSED and testPosition(x - 1, y, rotation) then x = x - 1 elseif Right == PRESSED and testPosition(x + 1, y, rotation) then x = x + 1 end if A == PRESSED and testPosition(x, y, nextClockwiseRotation) then rotation = nextClockwiseRotation elseif B == PRESSED and testPosition(x, y, nextCounterclockwiseRotation) then rotation = nextCounterclockwiseRotation end if Down == PRESSED_FOR_3_FRAMES or nextFallTimer >= dropSpeed then if testPosition(x, y + 1, rotation) then y = y + 1 nextFallTimer = 0 else lockTetrimino() return end end childState = states[y][x][rotation][Left][Right][Down][A][B] if not childState.visited then childState.visited = mark childState.predecessor = state childState.fallTimer = nextFallTimer queue.enqueue(childState) end 

Seperti pada versi sebelumnya, ia AI.searchmengembalikan serangkaian objek State. Namun dalam hal ini, masing State- masing berisi banyak tombol yang perlu ditekan di setiap frame. Bidang x, ydan rotationtidak digunakan untuk memanipulasi bentuk, tetapi dapat digunakan untuk memverifikasi gerakan bentuk yang benar.

Meskipun ruang pencarian telah berkurang secara signifikan karena keterbatasan yang dijelaskan di atas, dibutuhkan 1-3 detik untuk menyelesaikan pencarian. Jika Anda menjalankannya, Anda akan melihat jeda setelah membuat setiap tetrimino. Selain itu, gerakannya terlihat sangat tidak wajar; biasanya belokan dilakukan sesaat sebelum mengunci. Namun, AI ini memainkan cara yang hampir sama dengan versi yang mengabaikan gravitasi, bahkan pada kecepatan maksimum.

Untuk memeriksanya, jalankan lua/NintendoTetrisAIGamepadVersion.lua, yang terletak di file zip dengan sumber .

Cara yang lebih sederhana untuk memperhitungkan gravitasi adalah membatasi pergerakan figur hanya dengan memutar, diikuti oleh pergeseran, dan kemudian turun ke bawah. Idenya adalah bahwa jika Anda menyingkirkan geser dan gulir, maka kecepatan vertikal dari angka-angka tersebut akan memiliki sedikit efek pada AI; semua yang perlu dia lakukan adalah memberikan angka ke kolom yang diinginkan, dan gravitasi akan melakukan sisanya. Keuntungan lain dari teknik ini adalah ruang pencariannya sangat kecil, yang memungkinkan Anda bermain secara real time, tanpa penundaan untuk perhitungan. Namun, kelemahan dari pendekatan ini adalah bahwa tanpa sliding dan scrolling, AI bermain jauh lebih buruk. Namun, Tetris AI, yang tidak dapat bermain dalam waktu nyata, secara praktis tidak berharga.

Selain itu

Sebelumnya, saya menulis sebuah plugin yang secara prosedural mensimulasikan seorang pemain di Tetris. Namun, proyek saya memiliki beberapa kelemahan:

1. Bot mematikan gravitasi, memungkinkan Anda untuk melakukan luncuran dan pengguliran, melebihi kemampuan pemain di level paling minimum Nintendo Tetris. Dia tidak pernah menaikkan angka ke bawah, tetapi satu-satunya cara untuk menurunkan angka ke bawah adalah keturunan lembut yang terkontrol. Artinya, ia bermain di dunia teoretis dan ideal. Terus terang, dia curang.
2. . — , . Double, Triple Tetris, — , . 90. , , 29 - .
3. . . . , Tetris .

Di bagian ini, saya akan berbicara tentang bot canggih yang memainkan Nintendo Tetris tanpa menonaktifkan gravitasi. Dia menilai risiko dan mengelolanya, secara agresif berusaha untuk mendapatkan jumlah poin maksimum sebelum mencapai kecepatan keturunan yang tinggi.

---

Video

Tonton bot dapatkan jumlah maksimum titik Tetris Nintendo mulai dari level 19 di semua video yang ditunjukkan di bawah ini.

---

Unduh

TetrisAI_2018-01-28.zip

File ini .zipberisi:

• src - pohon kode sumber.
• TetrisAI.jar - Mengompilasi file biner.
• lgpl-2.1.txt - lisensi perangkat lunak gratis.

---

Luncurkan

Prasyarat

• Nintaco adalah emulator NES / Famicom.
• Tetris (U) [!].nes - File Nintendo Tetris ROM.

Peluncuran plugin

1. Luncurkan Nintaco dan buka Tetris (U) [!].nes.
2. Ekstrak TetrisAI.jardari yang diunduh .zip.
3. Buka jendela Jalankan Program dengan memilih Alat | Jalankan Program ...
4. JAR Find JAR… .
5. Load JAR, .
6. Run.
7. , GAME TYPE MUSIC TYPE . D-pad ( ) A-TYPE . Start (Enter), .
8. A-TYPE D-pad ( ) LEVEL 9 . , A Start ( X Enter), 19, .

Patut dipertimbangkan bahwa bot dirancang hanya untuk level 19 dan di atasnya. Pada level yang lebih rendah, dia tidak akan bisa mengendalikan bidak.

Referensi kecepatan

Agar game berjalan lebih cepat, pilih Mesin | Kecepatan | Maks

---

Detail

Dataran tinggi

Di bawah level 10, kecepatan turun di setiap level sedikit lebih tinggi dari yang sebelumnya. Tetapi pada level 10 ke atas ada beberapa dataran tinggi di mana kecepatan tetap konstan untuk beberapa level. Ini adalah konsekuensi dari cara mekanisme pemicu bekerja. Kecepatan disajikan sebagai jumlah frame per keturunan, yang merupakan nilai integer. Yaitu, untuk level yang lebih tinggi tidak ada banyak pilihan yang tersisa: 10–12, 13–15, 16–18, 19–28, dan 29+ adalah 5, 4, 3, 2, dan 1 frame untuk keturunan.

Bot dikembangkan dengan mempertimbangkan hanya dataran tinggi 19-28. Dalam bingkai yang rata, ia mengklik gamepad "Kiri", "Kanan", A, B atau tidak sama sekali. Dan dalam bingkai aneh, ini memungkinkan penurunan otomatis tanpa menekan tombol apa pun. Tampaknya permainan tidak merasakan gerakan horizontal yang bertepatan dengan rotasi; oleh karena itu, setiap tombol ditekan secara independen dalam bingkai genap.

Tidak seperti master yang bermain di level tinggi, bot tidak memanfaatkan Delayed Auto Shift (DAS), yang juga dikenal sebagai auto-repeat, dan teknik terkait. Karyanya lebih mengingatkan pada teknik ibu jari bergetar dari Thor Akerlund . Namun, itu meningkatkan frekuensi getaran ke maksimum teoritis yang diizinkan oleh permainan.

Pemain dihargai dengan 40, 100, 300 dan 1200 poin untuk Single, Double, Triple dan Tetris. Dan poin-poin dikalikan dengan angka level ditambah 1. Dengan kata lain, untuk mendapatkan skor maksimum, pemain harus berjuang untuk jumlah Tetris maksimum, bermain selama mungkin di level tinggi.

Level 19 adalah yang tertinggi yang dapat dipilih sebagai yang awal, yang memungkinkan bot untuk melompat langsung ke dataran 19–28. Namun, karena bug dalam mekanisme perhitungan level yang saya sebutkan di bagian sebelumnya, game akan pergi ke level 20 setelah menghapus 140 baris, bukannya 200 yang diharapkan. Setelah itu, game akan mengubah level setiap 10 baris. Namun, setelah mencapai 230 baris, bot akan naik dari dataran tinggi dan menyerah dengan cepat. Artinya, dia perlu memutar Tetris sebanyak mungkin sebelum membersihkan 230 baris.

Keturunan lembut

Soft descent juga dapat meningkatkan jumlah poin. Untuk mendapatkan poin, angka tersebut harus diturunkan dengan lembut untuk mengunci lapangan permainan. Keturunan lunak jangka pendek apa pun yang terjadi di sepanjang jalan saat memposisikan angka tidak akan memengaruhi skor. Jika keturunan berhasil, pemain akan menerima satu poin untuk setiap garis yang dilintasi selama keturunan lembut. Dan nilai yang dihasilkan tidak dikalikan dengan angka level, bahkan jika keturunan lembut mengarah pada membersihkan baris.

Soft descent tidak banyak berpengaruh pada skor keseluruhan. Namun, jika memungkinkan, bot menyelesaikan penempatan gambar dengan mengklik "Turun" untuk mendapatkan poin ini. Dalam kasus yang jarang terjadi, itu dapat rata-rata perbedaan antara skor yang sangat tinggi dan melebihi skor maksimum.

Algoritma AI

Saat membuat bentuk, bot mengeksplorasi setiap kemungkinan penempatan bentuk saat ini dan selanjutnya. Penempatan yang diizinkan adalah posisi di mana gambar berada di sel yang ditempati atau di lantai lapangan bermain. Dari tempat penciptaan gambar, posisi ini dapat dicapai melalui urutan gerakan horizontal, belokan dan turun. Lokasi dan urutan jalur yang valid ditemukan menggunakan BSF.

Menempatkan sepotong di lapangan bermain memiliki konsekuensi: 4 sel kosong menjadi sibuk, dan semua baris diisi dihapus, membiarkan baris turun. Untuk setiap penempatan yang diperbolehkan dari gambar saat ini dan konsekuensi yang terkait dengannya, bot memeriksa setiap penempatan yang diijinkan dari gambar berikutnya, mengevaluasi kombinasi konsekuensi. Rantai pencarian seperti itu disajikan SearchChain.

Setiap konsekuensi gabungan ditransfer ke fungsi evaluasi yang menghitung isi dari lapangan bermain. Kombinasi dengan skor terendah menang dan bagian saat ini ditempatkan sesuai. Hasil rantai pencarian hanya memengaruhi bentuk saat ini. Saat membuat gambar berikutnya, itu dievaluasi dalam kombinasi dengan angka yang mengikutinya, dan seterusnya.

Fungsi evaluasi

Fungsi evaluasi adalah jumlah tertimbang dari parameter berikut:

• Jumlah baris yang dihapus adalah jumlah baris yang dihapus dengan penambahan kedua tetriminos.
• – , . — , , .
• - – .
• – , -.
• – , . . .
• – . , 1. , , .
• – , . — , — .
• – . , (20).
• – . , 0.
• – , ( ) .
• : — , ( ) . . . .
• – . , 1 , 1, — 0.
• – .
• – .
• – .
• – . .
• – .

Pembelajaran mesin

Untuk menemukan bobot fungsi evaluasi, kami menggunakan varian metode Particle Swarm Optimization (PSO) yang dijelaskan dalam catatan kaki [1]. Untuk mendapatkan perilaku konvergen yang baik, inersia yang diusulkan dan koefisien percepatan diterapkan. Dan ukuran maksimum langkah-langkah partikel ditentukan oleh batasan nilai kecepatannya.

Selama setiap iterasi, partikel dievaluasi secara paralel untuk memanfaatkan sepenuhnya sumber daya komputasi yang tersedia. Selain itu, setelah konvergensi terdeteksi (tidak ada peningkatan setelah sejumlah iterasi), PSO diatur untuk memulai kembali secara otomatis dengan bobot yang dipilih secara acak, yang memungkinkan kami untuk menjelajahi lebih jauh ruang pencarian.

Setiap vektor posisi partikel dievaluasi dengan mensimulasikan penyelesaian 100 batch di dataran tinggi level 19-28. Batch penuh melibatkan pembersihan 230 baris, tetapi banyak yang berakhir dengan luapan lapangan. Skor batch diurutkan, dan skor partikel ditentukan sebagai rata-rata 33 dari 100 batch. Idenya adalah memilih berdasarkan pada agresivitas. Partikel di sepertiga atas hanya digunakan untuk urutan angka yang diinginkan, yang membatasi kebutuhan untuk permainan konservatif. Akibatnya, mereka cenderung mendorong game yang biasa ke jurang, menunggu "tongkat" berikutnya.

Urutan pola untuk 100 batch dihasilkan sebelum PSO, dan urutan yang sama digunakan lagi dan lagi. Ini diperlukan untuk memperbaiki ruang pencarian, sehingga opsi solusi dapat dibandingkan satu sama lain. Urutan dibuat menggunakan logika PRNG Nintendo Tetris nyata, yang dirancang untuk mengurangi kemungkinan duplikat mengikuti satu sama lain. Tetapi PRNG juga memiliki kelemahan (lihat bagian “Memilih Tetrimino” dari artikel sebelumnya): PRNG tidak memilih angka secara merata.

Upaya awal menghasilkan bot bertindak terlalu agresif. Jika mereka mengatasi dataran tinggi 19–28, mereka biasanya mencapai skor maksimum. Namun, sayangnya, mereka sering terlalu dini menyebabkan luapan lapangan. Menanggapi ini, empat langkah diambil untuk "menenangkan" bot:

1. : Tetris, . «» . . ; 230 . , Tetris . Single, Double Triple. ; .
2. . , , 7 . .
3. , , . , 7 .
4. , , . , . , .

Setelah menerapkan semua aturan ini untuk "menenangkan" bot, metode PSO memberikan bobot berikut:

Parameter	Berat
Total jumlah baris yang dihapus	0.286127095297893900
Tinggi pemblokiran total	1.701233676909959200
Jumlah total sel sumur	0.711304230768307700
Total jumlah sumur dalam	0,910665415998680400
Jumlah total lubang di kolom	1.879338064244357000
Total Lubang Kolom Tertimbang	2.168463848297177000
Jumlah total kedalaman lubang di kolom	−0.265587111961757270
Kedalaman Lubang Kolom Minimum	0,289886584949610500
Kedalaman Lubang Kolom Maksimum	0.362361055261181730
Jumlah total transisi dalam kolom	−0.028668795795469625
Garis Total Melompat	0.874179981113233100
Tinggi total kolom	−0.507409683144361900
Tinggi tumpukan	−2.148676202831281000
Sebaran Tinggi Kolom	−1.187558540281141700
Jumlah total sel yang ditempati	−2.645656132241128000
Total jumlah sel yang terisi	0.242043416268706620
Penyebaran Ketinggian Kolom	0.287838126164431440

Karena rantai berusaha untuk kombinasi yang meminimalkan fungsi evaluasi, parameter yang memiliki bobot positif dapat dianggap bonus, dan sisanya - denda. Tetapi bobot tidak selalu menunjukkan signifikansi dari parameter yang sesuai; mereka tidak dinormalisasi, oleh karena itu mereka tidak dapat dibandingkan.

Kekuatan AI

Untuk menilai kekuatan AI, sekitar 1,7 juta hasil (dalam poin) dari game simulasi dikumpulkan di dataran tinggi 19-28. Skor tidak mencerminkan permainan di level 29 atau lebih tinggi, dan tidak memperhitungkan poin akun yang diperoleh dari keturunan lunak. Namun, itu termasuk game yang diselesaikan sebelum waktunya karena luapan lapangan. Logika Nintendo Tetris PRNG digunakan untuk menghasilkan urutan Tetrimino.

Di antara hasil ini, skor terbesar adalah 1.313.600. Minimal adalah 0.

Rata - rata adalah 816.379, dan tampaknya kecil. Tetapi seperti yang disebutkan di bawah ini, data terdistorsi, sehingga skor rata-rata 989.200 poin memberikan ide yang lebih baik dari nilai tipikal.

Seperti yang dinyatakan di atas, PSO mengoptimalkan bobot berdasarkan rata-rata sepertiga terbaik batch. Dalam hal ini, skor rata-rata ketiga terbaik adalah 1 108 860. Faktanya, skor rata-rata 75% terbaik adalah 1.000.000.

Bot memiliki probabilitas 47% untuk mencapai batas poin ke level 29. Ia memiliki probabilitas 61% untuk mendapatkan 900.000 poin ke level tersebut. 29. Grafik di bawah ini menunjukkan probabilitas untuk mencetak hingga level 29.


Tampaknya probabilitasnya menurun secara linear menjadi sekitar 900.000 poin. Kemudian masuk ke kurva sigmoid terbalik.

Di bawah ini adalah histogram yang diperhalus dengan jumlah pihak untuk setiap poin yang dicetak. Bentuknya ditentukan oleh turunan dari grafik yang ditunjukkan di atas.


Jika Anda mengabaikan fluktuasi, maka sekitar 900.000 itu datar, dan kemudian masuk ke distribusi normal dengan pusat sekitar 1.050.000 poin. Alasan fluktuasi tidak jelas. Tampaknya jumlah poin lebih suka untuk melompat dengan peningkatan 20.000 poin. Mungkin ini karena siklus pembangunan tumpukan dan mendapatkan Tetris.

RAM dan alokasi ROM

Untuk memanipulasi memori CPU, kirim klik tombol dan terima acara rendering bingkai, plugin menggunakan Nintaco API . Semua alamat memori ditemukan menggunakan alat debugging Nintaco, dan informasi ditambahkan ke wiki Data Crystal ROMhacking.net . Dalam kode sumber, mereka terlihat seperti konstanta di antarmuka Addresses.

---

Referensi

1. van den Bergh, F.; Engelbrecht, AP (2006)
   A study of particle swarm optimization particle trajectories
   In: Information Sciences 176 (2006) (pp. 937–971)
   Retrieved from http://researchspace.csir.co.za/dspace/bitstream/handle/10204/1155/van%20den%20bergh_2006_D.pdf