Tic Tac Toe “Tanpa Batas”

Tic-tac-toe ... semua orang memainkannya, saya yakin. Permainan ini menarik dalam kesederhanaannya, terutama ketika Anda menyeret jam di suatu tempat dalam pelajaran, pasangan, dan tidak ada yang ada di sana kecuali lembar notebook dan pensil sederhana. Saya tidak tahu siapa yang pertama kali menebak menggambar salib dan lingkaran dalam 9 kotak, tetapi sejak itu permainan tidak kehilangan permintaan, terutama karena orang-orang telah datang dengan banyak variasi.



Artikel ini adalah tentang proses pengembangan AI pada javascript untuk memainkan salah satu variasi tic-tac-toe ini: Saya punya banyak materi, tapi saya melarutkannya dengan animasi dan gambar. Bagaimanapun, setidaknya ada baiknya mencoba memainkannya.
Perbedaan antara versi gim ini dan yang asli adalah sebagai berikut:

1. Bidang dapat menjadi besar secara sewenang-wenang (Berapa lama notebook akan bertahan)
2. Pemenangnya adalah orang yang menempatkan 5 buah (jika Anda bisa menyebutnya begitu) berturut-turut.

Semuanya sederhana ... dan pada saat yang sama rumit: hasil permainan tidak dapat dihitung sebelumnya, seperti pada analog klasik. "Proyeksi kecil" ini menghilangkan banyak waktu dan saraf saya. Semoga Anda menemukan itu menarik.

Sebelum kita mulai

Terpaksa untuk meminta maaf sebelumnya atas volume artikel dan di beberapa tempat presentasi pemikiran yang tidak cukup masuk akal, bagaimanapun, saya tidak bisa memeras kawanan tanpa kehilangan konten dan kualitas.
Saya sarankan Anda membiasakan diri dengan hasilnya . Kode

Tombol cepat dan perintah:

• D - AI akan bergerak untuk Anda
• T - lihat berat sel
• Tulis SHOW_WEIGHTS = true di konsol untuk melihat bobot semua sel yang dianalisis.

Mari kita mulai

Anda harus mulai dengan implementasi game itu sendiri, mis. menulis aplikasi untuk dua pemain, sejauh ini tanpa bot. Untuk tujuan saya, saya memutuskan untuk menggunakan javascript + jquery + bootstrap4, meskipun secara praktis tidak digunakan di sana, tetapi lebih baik meninggalkannya - atau tabel akan mengambang. Tidak ada yang istimewa untuk diceritakan, ada banyak materi tentang js, jquery dan bootstrap. Saya hanya bisa mengatakan bahwa saya menggunakan MVC. Bagaimanapun, saya tidak akan menjelaskan sepenuhnya semua kode - sudah ada banyak materi.

Jadi, lapangan sudah siap. Anda bisa mengatur bentuk dalam sel. Tapi kemenangan salah satu pemain itu tidak pasti.

Akhir pemindaian game

Permainan berakhir ketika salah satu pemain menempatkan 5 buah berturut-turut. "Sederhana!" Saya pikir. Dan dia mulai memindai sepenuhnya semua sel lapangan: pertama semua horizontal, lalu vertikal, dan akhirnya diagonal.

Ini cara yang bodoh, tetapi berhasil. Namun, itu bisa ditingkatkan secara signifikan, yang saya lakukan: Sebagian besar sel akan tetap kosong sepanjang permainan - lapangan bermain terlalu besar untuk diisi seluruhnya. Karena itu perlu untuk memindai setiap gerakan, dan hanya satu bagian ditempatkan dalam satu gerakan - Anda hanya dapat fokus pada bagian ini (sel): memindai hanya satu horisontal, vertikal dan dua diagonal sel yang memiliki sel yang sama.

Plus, Anda tidak perlu memindai semua garis sel. Karena akhir permainan adalah 5 buah berturut-turut, potongan-potongan yang 6 sel terpisah satu sama lain tidak menarik bagi kami. Cukup dengan memindai lima sel di setiap sisi. Tidak mengerti Lihat animasi di bawah ini.

Mari kita turun ke bot itu sendiri

Jadi, kami sudah menulis halaman dengan tic-tac-toe. Kami lolos ke tugas utama - AI.
Anda tidak bisa hanya mengambil dan menulis kode jika Anda tidak tahu caranya: Anda perlu memikirkan logika bot.

Intinya adalah untuk menganalisis lapangan bermain, setidaknya sebagian darinya, dan menghitung harga (berat) setiap sel di lapangan. Sel dengan berat tertinggi - yang paling menjanjikan - bot akan meletakkan angka di sana. Kesulitan utama adalah dalam menghitung berat satu sel.

Terminologi

Persilangan dan jari kaki adalah angka.
Sebuah serangan akan disebut beberapa tokoh identik yang berdiri berdampingan di garis yang sama. Sebenarnya, ini banyak. Jumlah bagian dalam serangan adalah kekuatannya . Satu bagian yang terpisah juga merupakan serangan (kekuatan 1).

Pada sel serangan yang berdekatan (di ujung) mungkin ada sel kosong atau potongan musuh. Adalah logis untuk berpikir bahwa serangan dengan dua sel kosong di "ujung" dapat dikembangkan dalam dua arah, yang membuatnya lebih menjanjikan. Jumlah sel kosong di "ujung" serangan akan disebut potensinya . Potensinya bisa 0, 1 atau 2.
Kami menyatakan serangan sebagai berikut: [kekuatan serangan, potensial] . Misalnya, serangan [4: 1] .


Gambar 1. Serang [4: 1]

Dalam proses analisis, kami akan mengevaluasi semua sel yang memasuki area tertentu. Setiap sel akan menghitung beratnya . Itu dihitung berdasarkan bobot semua serangan yang mempengaruhi sel ini.

Esensi dari analisis

Bayangkan di lapangan bermain sudah ada beberapa serangan pemain satu dan yang kedua. Salah satu pemain bergerak (biarkan umpan silang). Secara alami, ia pindah ke sel kosong - dan dengan demikian ia dapat:

1. Kembangkan serangan Anda, dan mungkin lebih dari satu, tingkatkan kekuatannya. Dapat meluncurkan serangan baru, dll.
2. Cegah pengembangan serangan musuh atau blokir sepenuhnya.

Artinya, protagonis kita dapat menyerang dan bertahan. Atau mungkin sekaligus sekaligus. Baginya, yang pertama dan yang kedua adalah penting.

Inti dari analisis adalah sebagai berikut:

1. Bot menggantikan angka-angka di sel yang diperiksa: pertama sebuah salib, lalu nol.
2. Kemudian dia mencari semua serangan yang diterima oleh gerakan seperti itu dan merangkum bobotnya.
3. Jumlah yang diterima adalah berat sel.
4. Algoritma serupa dilakukan untuk semua sel bidang bermain.

Faktanya, kami memeriksa dengan algoritme seperti apa yang akan terjadi jika kami pergi dengan cara ini ... dan apa yang akan terjadi jika lawan seperti itu. Kami menantikan satu langkah dan memilih sel yang paling cocok - dengan bobot tertinggi.

Jika sebuah sel memiliki bobot lebih dari yang lain, maka itu mengarah pada penciptaan serangan yang lebih berbahaya, atau untuk memblokir serangan musuh yang kuat. Semuanya logis ... menurut saya.
Jika Anda pergi ke halaman dan menulis di konsol SHOW_WEIGHTS = true, Anda dapat secara visual merasakan operasi algoritma (Bobot sel akan ditampilkan).

Berat Serangan

Saya memeriksa otak saya dan membawa korespondensi serangan dan beban:

 ATTACK_WEIGHT = [[],[],[],[],[],[]]; ATTACK_WEIGHT[1][1] = 0.1; ATTACK_WEIGHT[2][1] = 2; ATTACK_WEIGHT[3][1] = 4; ATTACK_WEIGHT[4][1] = 6; ATTACK_WEIGHT[5][1] = 200; ATTACK_WEIGHT[1][2] = 0.25; ATTACK_WEIGHT[2][2] = 5; ATTACK_WEIGHT[3][2] = 7; ATTACK_WEIGHT[4][2] = 100; ATTACK_WEIGHT[5][2] = 200; ATTACK_WEIGHT[5][0] = 200; 

Dipilih secara empiris - mungkin ini bukan pilihan terbaik.

Saya menambahkan kekuatan serangan 5 dengan bobot yang sangat besar ke array. Hal ini dapat dijelaskan oleh fakta bahwa bot menganalisis permainan, melihat langkah maju (menggantikan sosok di dalam sel). Melewati serangan seperti itu hanyalah kekalahan. Ya, atau kemenangan ... tergantung siapa.

Serangan dengan potensi tinggi dihargai lebih tinggi.

Serang [4: 2] dalam banyak kasus menentukan hasil pertandingan. Jika pemain berhasil membuat serangan seperti itu, maka lawan tidak akan lagi dapat memblokirnya. Namun, ini bukan kemenangan. Musuh dapat menyelesaikan permainan lebih cepat, bahkan jika kita memiliki serangan [4: 2] di lapangan, jadi bobotnya lebih rendah daripada serangan dengan kekuatan 5. Lihat contoh di bawah ini.


Gambar 2. Serang [4: 2]

Serangan Robek

Kode tidak disajikan dalam paragraf ini. Di sini kami memperkenalkan konsep pembagi serangan dan menjelaskan esensi dari "serangan robek" .

Pertimbangkan situasi berikut: ketika mengganti gambar untuk menghilangkan beberapa sel kosong, tetapi tidak lebih dari 5, satu lagi terletak.

Dan, tampaknya, dua tokoh yang identik, pada baris yang sama ... secara visual terlihat seperti serangan, tetapi kenyataannya tidak. Bukan perintah, karena serangan "sobek" seperti itu juga membawa potensi ancaman.

Khusus untuk kasus seperti itu, untuk setiap serangan kami akan menghitung pembagi. Awalnya, nilainya 1.

1. Kami menghadirkan serangan "sobek" sebagai beberapa serangan biasa
2. Kami menghitung jumlah sel kosong antara serangan pusat dan samping
3. Untuk setiap sel kosong, pembagi akan bertambah 1
4. Kami menghitung berat serangan pusat seperti biasa, berat serangan samping - dibagi dengan pembagi

Gambar 3. Analisis "Serangan robek". Sel dengan palang kuning dipindai.

Dengan demikian, serangan yang terkoyak juga akan diperhitungkan oleh AI. Sebenarnya, ini akan menjadi serangan biasa, tetapi semakin jauh mereka dari sel yang dipindai, semakin sedikit pengaruh yang dimilikinya terhadapnya, dan karenanya, mereka memiliki berat yang lebih sedikit (terima kasih kepada pembagi).

Algoritma Pencarian Serangan

Pertama, buat kelas serangan. Serangan itu akan memiliki 3 atribut, yang saya tulis sebelumnya:

 class Attack{ constructor( cap = 0, pot = 0, div = 1 ){ this.capability = cap; // this.potential = pot; // this.divider = div; // } 

Dan satu metode yang akan mengembalikan bobot serangan yang diberikan:

 countWeigth(){ return ATTACK_WEIGHT[ this.capability, this.potential ] / this.divider } } 

Selanjutnya Kami akan membagi pencarian untuk semua serangan untuk satu sel menjadi:

1. Pencarian Horisontal
2. Pencarian vertikal
3. Pencarian diagonal 45 derajat
4. Pencarian diagonal 135 derajat

Semua ini adalah garis , dan algoritma untuk mencari serangan pada garis ini dapat digeneralisasi: kelas checkLine .

Namun, kami tidak perlu memeriksa seluruh baris. Kekuatan serangan maksimum yang menarik minat kita adalah 5. Tentu saja, dimungkinkan untuk membuat serangan dengan kekuatan, katakanlah, 6. Tetapi untuk AI yang menganalisis situasi permainan dari langkah selanjutnya, itu sama dengan 6 atau 5. Prospek mendapatkan salah satu dari serangan ini menunjukkan akhir dari permainan di langkah berikutnya. Dengan demikian, berat sel yang dianalisis akan sama dalam kedua kasus.

Atribut kelas:

 class checkLine{ constructor(){ //,        this.subFig = "×"; //     .    «0» - . this.Attacks = []; //  this.curAttack = new Attack; // (      ) this.iter = 1; //,     this.checkEdge = false; 

Penting untuk berhenti di sini, karena pertanyaan mungkin muncul: mengapa memeriksa sel ke-6 jika kekuatan serangan maksimum adalah 5. Jawabannya adalah untuk menentukan potensi jarak jauh dari pusat serangan.

Berikut ini sebuah contoh: serangan dengan kekuatan 1 pada gambar terletak di perbatasan area yang dipindai. Untuk mengetahui potensi serangan ini, Anda perlu "mencari ke luar negeri."


Fig. 3. Memindai sel ke-6. Jika Anda tidak memindai sel ke-6, Anda dapat salah menentukan potensi serangan.

  //   this.attackplace = 1; } 

Mungkin tidak ada cukup ruang untuk menyelesaikan beberapa serangan. Setelah menghitung tempat penyerangan, kita dapat memahami sebelumnya serangan mana yang tidak menjanjikan.


Fig. 4. Tempat untuk menyerang

Algoritma adalah sebagai berikut:

1) Mari kita mulai dengan sel pusat. Itu harus kosong (kita akan bergerak ke dalamnya, kan? Tapi kita tidak lupa bahwa AI kita harus mengganti angka dalam sel ini untuk analisis langkah selanjutnya. Angka yang kita gantikan adalah ini. Subfig - defaultnya adalah salib. Karena sel pusat awalnya akan berisi beberapa bentuk setelah substitusi, itu akan menjadi milik beberapa serangan ini.

• kekuatannya tidak kurang dari 1 (angka di sel pusat)
• divider - 1, karena itu adalah serangan pusat (itu milik sel yang dipindai);
• potensi belum diketahui - standarnya adalah 0;

Kami menampilkan semua titik ini dalam nilai konstruktor default - lihat kode di atas.

2) Selanjutnya, mengurangi iterator, mengulangi lebih dari 5 sel di satu sisi yang dipindai. Fungsi getAttacks (cellX, cellY, subFig, dx, dy) bertanggung jawab untuk ini, di mana:

cellX, cellY - koordinat dari sel yang diperiksa
subFig - gambar yang kami gantikan dalam sel yang diperiksa
dx, dy - perubahan dalam koordinat x dan y dalam siklus - ini adalah bagaimana kami menetapkan arah pencarian:

• Horisontal (dx = 1, dy = 0)
• Vertikal (dx = 0, dy = 1)
• Diagonal 45 (dx = 1, dy = -1)
• Diagonal 135 (dx = 1, dy = 1)

Dalam arti tertentu, ini adalah paralel vektor ke baris pencarian. Dengan demikian, satu fungsi akan dapat mencari dalam 4 arah dan kami tidak akan melanggar prinsip KERING sekali lagi.

Kode fungsi:

 getAttacks( cellX, cellY, subFig, dx, dy ){ this.substitudeFigure( subFig ); //  –  ... for( var x = cellX - dx, y = cellY - dy; Math.abs( x - cellX ) <= 5 && Math.abs( y - cellY ) <= 5; x -= dx, y -= dy ) if( this.checkCell( x, y ) ) break; //: //    (  ) this.turnAround(); //  -    ... for( var x = cellX + dx, y = cellY + dy; Math.abs( x - cellX ) <= 5 && Math.abs( y - cellY ) <= 5; x += dx, y += dy ) if( this.checkCell( x, y ) ) break; return this.Attacks; } 

Harap dicatat bahwa jika checkCell () mengembalikan sesuatu, maka loop berhenti.

3) Kami memeriksa angka sel-sel ini.
Fungsi checkCell (x, y) bertanggung jawab untuk ini:

Pertama, tulis bentuk ke variabel ara :
Model.Field adalah lapangan bermain kami.

 checkCell( x, y ){ var fig = Model.Field[x] && Model.Field[x][y] !== undefined ? Model.Field[x][y] : 'b'; 

ara dapat berupa 'x', 'o', 'b' (perbatasan), 0 (sel kosong).

• Jika angka seperti itu bertepatan dengan angka sel pusat ( this.subFig ), maka kami melanjutkan algoritme - maka kami terus memindai serangan, semuanya baik-baik saja, kami melanjutkan dengan semangat yang sama. Bagian tambahan dalam serangan adalah nilai tambah untuk kekuatannya ( this.curAttack.capability ) dan tempat ( this.attackplace ).
  
  (Lihat kode pada paragraf berikutnya)
• Jika ini adalah angka yang berbeda, maka serangan yang kami pindai sebelumnya (this.curAttack) diblokir dari sisi ini. Kami tidak mengubah apa pun di parameter serangan, menulisnya ke array serangan dan keluar dari loop.
  
  

   if( fig == '○' || fig == '×' ){ if( this.subFig != fig ){ //  this.Attacks.push( this.curAttack ); //  return fig; //      } else{ //    this.curAttack.capability++; // +   this.attackplace++; // +   } } 

  
  
• Jika tidak ada sel seperti itu, itu berarti mereka jatuh dari batas lapangan, yang berarti serangan diblokir. Kami menulisnya ke dalam array semua serangan dan keluar dari loop.
  
  

   else if( fig == 'b' ){ // this.Attacks.push( this.curAttack ); return 'b'; } 

  
  
• Jika Anda menangkap sangkar kosong, itu berarti serangan saat ini sudah berakhir atau kami sedang menghadapi "serangan sobek." Ditambah potensi dan tempat untuk menyerang (karena serangan tidak terhalang). Namun, kami tidak keluar dari loop - mungkin ini adalah "serangan robek" - kami hanya menulis ini.curAttack ke array semua serangan dari baris ini. Serangan []. Buat serangan "saat ini" baru dan tingkatkan pembagi sebesar 1 (ini adalah serangan samping).
  
  

   else{ //  if( this.curAttack.capability ){ this.curAttack.potential++; this.Attacks.push( this.curAttack ); this.curAttack = new Attack; this.curAttack.potential++; } this.curAttack.divider++; this.attackplace++; } 

  
  

4) Jika pada sel ke 5 angkanya bertepatan dengan sel pusat, maka serangan "beristirahat" terhadap perbatasan dan untuk menentukan potensi serangan Anda harus "memeriksa perbatasan" ( this.checkEdge = true ).

 if( this.iter == 4 && fig == this.subFig ) // 5-  this.checkEdge = true; else if( this.iter == 5 ){ if( this.checkEdge ){ if( fig == this.curFig || fig == 0 ) this.curAttack.potential++; this.Attacks.push( this.curAttack ) } return 0; } this.iter++ 

Fungsi checkCell sudah siap. Namun, kami terus bekerja pada kelas checkLine .

5) Setelah menyelesaikan siklus pertama, Anda perlu "berbalik." Kami menerjemahkan iterator ke pusat dan serangan pusat, dengan indeks 0, menghapusnya dari susunan serangan dan menetapkannya sebagai serangan saat ini.

 turnAround(){ this.iter = 1; this.checkEdge = false; this.curAttack = this.Attacks[0]; this.Attacks.splice(0,1) } 

6) Selanjutnya, pergi ke sisi lain dari sel saat ini, meningkatkan iterator.
Benar-benar cek angka yang sama. (Kode sudah ditulis - fungsi getAttacks )

7) Semuanya, kami mengumpulkan semua serangan yang ada di baris dalam satu array.
Itu saja dengan kelas checkLine ... semuanya dilakukan.

Nah, maka semuanya sederhana - buat objek checkLine untuk masing-masing garis (2 diagonal, horizontal dan vertikal) dan panggil fungsi getAttacks . Yaitu, untuk setiap baris - objek checkLine sendiri dan, karenanya, set serangannya sendiri.

Biarkan fungsi getAllAttacks () bertanggung jawab untuk semua ini - sudah terpisah dari kelas yang dijelaskan di atas;

 getAllAttacks( cellX, cellY ){ // ,  , //       if( Model.Field[ cellX ][ cellY ] ) return false var cX = []; var cO = []; //   ... cX['0'] = this.getAttacksLine( cellX, cellY, '×', 1, 0 ); cX['90'] = this.getAttacksLine( cellX, cellY, '×', 0, 1 ); cX['45'] = this.getAttacksLine( cellX, cellY, '×', 1, -1 ); cX['135'] = this.getAttacksLine( cellX, cellY, '×', 1, 1 ); //  ... cO['0'] = this.getAttacksLine( cellX, cellY, '○', 1, 0 ); cO['90'] = this.getAttacksLine( cellX, cellY, '○', 0, 1 ); cO['45'] = this.getAttacksLine( cellX, cellY, '○', 1, -1 ); cO['135'] = this.getAttacksLine( cellX, cellY, '○', 1, 1 ); return { //     'x': cX, 'o': cO } } getAttacksLine( cellX, cellY, subFig, dx, dy ){ //      var C = new checkLine; C.getAttacks( cellX, cellY, subFig, dx, dy ); return this.filterAttacks( C ) //   } 

Pada output, kami memiliki objek dengan semua serangan untuk sel yang diuji

Namun, Anda mungkin telah memperhatikan semacam fungsi filter. Tugasnya adalah untuk menyaring serangan "sia-sia":

• Dengan nol daya (Anda tidak pernah tahu apakah mereka masuk ke array)
• Serangan yang kekurangan ruang (tempat serangan <5)
• Dengan nol potensi.

Namun, jika serangan memiliki kekuatan lebih besar dari 5, maka filter akan melewatinya. Bot harus melihat serangan seperti itu, skrining mereka akan mengarah ke tiang tembok di akhir pertandingan.

 filterAttacks( attackLine ){ var res = [] if( attackLine.attackplace >= 5 ) attackLine.Attacks.forEach( ( a )=>{ if( a.capability && a.potential || a.capability >= 5 ) res.push( a ) }) attackLine.Attacks = res; return res } 

Breakpoints

Ya ... lagi, maaf! Jadi kami akan memanggil situasi dalam permainan, ketika satu langkah yang salah menentukan hasil pertandingan.

Sebagai contoh, serangan [3: 2] adalah breakpoint. Jika lawan tidak menghalanginya dengan menempatkan sepotong di sebelahnya, maka langkah selanjutnya, kita sudah memiliki serangan [4: 2] di lapangan bermain - yah, hasil pertandingan diputuskan, apa pun yang orang katakan (dalam sebagian besar kasus).

Atau serangan [4: 1]. Satu menguap - dan permainan bisa dengan mudah diselesaikan.


Gambar 5. Breakpoint

Semuanya jelas dan dapat dimengerti, dan algoritma yang dijelaskan di atas sudah dapat memperhitungkan breakpoint akun dan memblokirnya tepat waktu. Bot melihat ke depan. Dia akan melihat bahwa pada giliran berikutnya lawan dapat membuat serangan [5: 1], misalnya, yang beratnya 200 - yang berarti bahwa kutu buku yang licik akan pergi ke sini.

Namun, bayangkan sebuah situasi ketika salah satu pemain berhasil mendapatkan 2 breakpoint di lapangan. Dan ini, jelas, tidak meninggalkan peluang bagi lawan, karena dalam satu langkah kita hanya dapat memblokir satu breakpoint. Bagaimana cara mengajarkan AI kami untuk memblokir serangan seperti itu?


Gambar 6. 2 Breakpoints

Semuanya sederhana, ketika menganalisis sel, ketika mengganti bagian di dalamnya, kita akan menghitung jumlah breakpoint yang akan kita dapatkan pada langkah berikutnya (bot melihat langkah maju, jangan lupa). Dengan menghitung 2 breakpoint, kami menambah berat sel sebanyak 100.

Dan sekarang, bot tidak hanya akan mencegah situasi permainan seperti itu, tetapi juga akan dapat menciptakannya, yang membuatnya sekarang menjadi lawan yang lebih tangguh.

Bagaimana memahami bahwa serangan adalah sebuah breakpoint

Mari kita mulai dengan yang sudah jelas: setiap serangan dengan kekuatan 4 adalah breakpoint. Hanya satu gerakan yang terlewat memberi kita kesempatan untuk menyelesaikan permainan, mis. letakkan 5 buah berturut-turut.

Lebih lanjut, jika potensi serangannya adalah 2, maka kita akan menghabiskan 1 turn lebih untuk memblokir serangan seperti itu, yang berarti ada breakpoint dengan kekuatan 3. Tetapi hanya ada satu breakpoint seperti itu - ini adalah serangan [3: 2].

Dan selanjutnya lebih sulit - "serangan robek" .
Kami hanya akan mempertimbangkan serangan dengan satu sel kosong di tengah - tidak lagi. Ini karena untuk menyelesaikan serangan dengan dua sel kosong di tengah, Anda harus menghabiskan setidaknya 2 gerakan - ini jelas bukan breakpoint.

Seperti yang kita ingat, kita menganggap serangan robek sebagai beberapa serangan konvensional: satu serangan sentral dan serangan samping. Serangan pusat adalah milik sel yang dipindai, pembagi samping memiliki lebih dari 1 - ini dijelaskan di atas.

Algoritma untuk menemukan breakpoint (lebih mudah, baca di bawah):

1. Kami memperkenalkan skor variabel
2. Kami mengambil serangan sentral, kami mempertimbangkan kekuatan
3. Kami mengambil salah satu yang samping jika pembagi nya tidak lebih dari 2x.
4. Skor - jumlah kekuatan serangan pusat dan samping
5. Jika potensi serangan pusat dan samping adalah 2, maka untuk memblokir serangan seperti itu Anda perlu menghabiskan satu putaran lagi. Oleh karena itu, skor bertambah 1
6. Jika skor > = 4, maka ini adalah breakpoint
   Bahkan, breakpoints bisa saja disebutkan, tidak banyak dari mereka, tetapi saya tidak segera mengerti ini.

 isBreakPoint( attackLine ){ if( ! attackLine || ! attackLine.length ) return false; var centAtk; attackLine.forEach( ( a )=>{ if( a.divider == 1 ) centAtk = a; }) if( centAtk.capability >= 4 ) return true if( centAtk.potential == 2 && centAtk.capability >= 3 ) return true; var res = false; attackLine.forEach( ( a )=>{ var score = centAtk.capability; if( a.divider == 2 ){ //side attack if( centAtk.potential == 2 && a.potential == 2 ) score++; if( score + a.capability >= 4 ){ res = true; return; } } }) return res; } 

Ya, kami akhirnya akan menyatukan semuanya

Jadi, neraka utama di belakang dijelaskan di atas. Sudah waktunya untuk membentuk sesuatu yang bekerja darinya. Function countWeight (x, y) - mengambil koordinat sel sebagai input, dan mengembalikan beratnya. Apa yang ada di bawah tudungnya?

Pertama, kita mendapatkan berbagai serangan yang dimiliki sel. ( getAllAttacks (x, y) ). Melewati semua baris, kami menghitung jumlah breakpoints. Jika ada 2 breakpoint, kami ingat bahwa situasi seperti itu dapat menentukan hasil permainan, dan menambah berat sel hingga 100.
Namun, semua breakpoint harus dimiliki oleh satu pemain, jadi saya harus menerapkan pemeriksaan dalam 2 langkah: salib pertama, lalu nol.

Karena dalam deretan bobot serangan ( ATTACK_WEIGHTS [] ) saya tidak memberikan serangan dengan kekuatan 6 atau lebih, saya harus menggantinya dengan serangan dengan kekuatan 5. Tidak ada bedanya - mereka semua mengarah ke akhir permainan.

Ya, kami merangkum bobot serangan - itu saja.

Poin kecil lainnya: agar bot tidak bodoh pada akhir permainan, ketika telah membangun serangan dengan kekuatan 4 dan berpikir tentang gerakan saat ini, perlu untuk secara signifikan meningkatkan berat sel untuk menyelesaikan serangan seperti itu. Tanpa ini, AI, secara sederhana, dapat mulai mempertahankan diri dari serangan "berbahaya" lawan, meskipun permainan tampaknya dimenangkan. Langkah terakhir itu penting.

 countWeight( x, y ){ var attacks = this.getAttacks( x, y ) if( ! attacks ) return; var sum = 0; sum += count.call( this, attacks.x, '×' ); sum += count.call( this, attacks.o, '○' ); return sum function count( atks, curFig ){ var weight = 0; var breakPoints = 0; [ "0", "45", "90", "135" ].forEach( ( p )=>{ if( this.isBreakPoint( atks[p] ) ){ debug( "Break point" ) if( ++breakPoints == 2 ){ weight += 100; debug( "Good cell" ) return; } } atks[p].forEach( ( a )=>{ if( a.capability > 5 ) a.capability = 5; if( a.capability == 5 && curFig == Model.whoPlays.char ) weight += 100; weight += a.getWeight(); }); }) return weight } } 

Sekarang, ketika memanggil fungsi ini untuk sel tertentu, kita akan mendapatkan bobotnya. Kami melakukan operasi ini untuk semua sel dan memilih yang terbaik (dengan bobot terbesar). Disana dan pergi)

Anda dapat menemukan sisa kode di github . Sudah ada banyak materi, dan presentasinya, karena saya belum mencoba, meninggalkan banyak yang harus diinginkan. Tetapi jika Anda dapat membaca sampai titik ini, pembaca yang budiman, maka saya berterima kasih kepada Anda.

Pendapat saya tentang hasilnya

Turun! Ya, Anda bisa mengalahkannya, tetapi melakukannya sedikit bermasalah bagi saya secara pribadi. Mungkin saya tidak cukup berhati-hati. Coba kekuatanmu juga.

Saya tahu itu lebih mudah, tetapi saya tidak tahu caranya. Saya ingin mendengarkan orang-orang yang tahu atau melihat implementasi lain dari bot semacam itu.

Saya tahu apa yang bisa lebih baik. Ya ... Anda dapat menggunakan algoritme terkenal, seperti minimax, tetapi untuk ini Anda perlu memiliki basis pengetahuan di bidang teori permainan, yang sayangnya tidak dapat saya banggakan.

Di masa depan saya berencana untuk menambahkan analisis breakpoint beberapa langkah ke depan, yang akan membuat bot menjadi lawan yang lebih serius. Namun, sekarang saya tidak memiliki ide yang jelas tentang implementasi ini; Saya hanya memiliki sesi mendatang dan diploma tidak lengkap - yang menyedihkan saya.

Terima kasih sudah membaca sampai akhir.