Dalam permainan Flood Paint, tujuan dari permainan ini adalah untuk membuat seluruh papan menjadi warna yang sama dalam beberapa putaran mungkin.
Gim dimulai dengan papan yang terlihat seperti ini:
3 3 5 4 1 3 4 1 5
5 1 3 4 1 1 5 2 1
6 5 2 3 4 3 3 4 3
4 4 4 5 5 5 4 1 4
6 2 5 3[3]1 1 6 6
5 5 1 2 5 2 6 6 3
6 1 1 5 3 6 2 3 6
1 2 2 4 5 3 5 1 2
3 6 6 1 5 1 3 2 4
Saat ini, angka (mewakili warna) di tengah papan adalah 3. Setiap belokan, persegi di pusat akan berubah warna, dan semua kotak dengan warna yang sama yang dapat dijangkau dari pusat dengan bergerak secara horizontal atau vertikal ( yaitu di wilayah banjir pusat alun-alun) akan berubah warna dengan itu. Jadi jika alun-alun pusat berubah warna menjadi 5:
3 3 5 4 1 3 4 1 5
5 1 3 4 1 1 5 2 1
6 5 2 3 4 3 3 4 3
4 4 4 5 5 5 4 1 4
6 2 5 5[5]1 1 6 6
5 5 1 2 5 2 6 6 3
6 1 1 5 3 6 2 3 6
1 2 2 4 5 3 5 1 2
3 6 6 1 5 1 3 2 4
maka 3 yang ada di sebelah kiri tengah 3 juga akan berubah warna. Sekarang ada total tujuh 5 yang dapat dicapai dari satu pusat, dan jadi jika kita kemudian berubah warna menjadi 4:
3 3 5 4 1 3 4 1 5
5 1 3 4 1 1 5 2 1
6 5 2 3 4 3 3 4 3
4 4 4 4 4 4 4 1 4
6 2 4 4[4]1 1 6 6
5 5 1 2 4 2 6 6 3
6 1 1 5 3 6 2 3 6
1 2 2 4 5 3 5 1 2
3 6 6 1 5 1 3 2 4
daerah yang dicat kembali bertambah besar secara dramatis.
Tugas Anda adalah membuat program yang akan mengambil kisi warna 19-by-19 dari 1 hingga 6 sebagai input, dalam bentuk apa pun yang Anda pilih:
4 5 1 1 2 2 1 6 2 6 3 4 2 3 2 3 1 6 3
4 2 6 3 4 4 5 6 4 4 5 3 3 3 3 5 4 3 4
2 3 5 2 2 5 5 1 2 6 2 6 6 2 1 6 6 1 2
4 6 5 5 5 5 4 1 6 6 3 2 6 4 2 6 3 6 6
1 6 4 4 4 4 6 4 2 5 5 3 2 2 4 1 5 2 5
1 6 2 1 5 1 6 4 4 1 5 1 3 4 5 2 3 4 1
3 3 5 3 2 2 2 4 2 1 6 6 6 6 1 4 5 2 5
1 6 1 3 2 4 1 3 3 4 6 5 1 5 5 3 4 3 3
4 4 1 5 5 1 4 6 3 3 4 5 5 6 1 6 2 6 4
1 4 2 5 6 5 5 3 2 5 5 5 3 6 1 4 4 6 6
4 6 6 2 6 6 2 4 2 6 1 5 6 2 3 3 4 3 6
6 1 3 6 3 5 5 3 6 1 3 4 4 5 1 2 6 4 3
2 6 1 3 2 4 2 6 1 1 5 2 6 6 6 6 3 3 3
3 4 5 4 6 6 3 3 4 1 1 6 4 5 1 3 4 1 2
4 2 6 4 1 5 3 6 4 3 4 5 4 2 1 1 4 1 1
4 2 4 1 5 2 2 3 6 6 6 5 2 5 4 5 4 5 1
5 6 2 3 4 6 5 4 1 3 2 3 2 1 3 6 2 2 4
6 5 4 1 3 2 2 1 1 1 6 1 2 6 2 5 6 4 5
5 1 1 4 2 6 2 5 6 1 3 3 4 1 6 1 2 1 2
dan kembalikan urutan warna yang akan diubah pusat persegi untuk setiap belokan, sekali lagi dalam format yang Anda pilih:
263142421236425431645152623645465646213545631465
Pada akhir setiap urutan gerakan, kotak dalam kisi 19-by-19 semuanya harus memiliki warna yang sama.
Program Anda harus sepenuhnya bersifat deterministik; solusi pseudorandom diperbolehkan, tetapi program harus menghasilkan output yang sama untuk test case yang sama setiap waktu.
Program yang menang akan mengambil jumlah langkah paling sedikit untuk menyelesaikan semua 100.000 kasus uji yang ditemukan dalam file ini (file teks zip, 14,23 MB). Jika dua solusi mengambil jumlah langkah yang sama (misalnya jika mereka berdua menemukan strategi yang optimal), program yang lebih pendek akan menang.
BurntPizza telah menulis sebuah program di Jawa untuk memverifikasi hasil pengujian. Untuk menggunakan program ini, jalankan kiriman Anda dan kirimkan output ke file bernama steps.txt
. Kemudian, jalankan program ini dengan steps.txt
dan floodtest
file di direktori yang sama. Jika entri Anda valid dan menghasilkan solusi yang benar untuk semua file, itu harus lulus semua tes dan kembaliAll boards solved successfully.
import java.io.*;
import java.util.*;
public class PainterVerifier {
public static void main(String[] args) throws FileNotFoundException {
char[] board = new char[361];
Scanner s = new Scanner(new File("steps.txt"));
Scanner b = new Scanner(new File("floodtest"));
int lineNum = 0;
caseloop: while (b.hasNextLine()) {
for (int l = 0; l < 19; l++) {
String lineb = b.nextLine();
if (lineb.isEmpty())
continue caseloop;
System.arraycopy(lineb.toCharArray(), 0, board, l * 19, 19);
}
String line = s.nextLine();
if (line.isEmpty())
continue;
char[] steps = line.toCharArray();
Stack<Integer> nodes = new Stack<Integer>();
for (char c : steps) {
char targetColor = board[180];
char replacementColor = c;
nodes.push(180);
while (!nodes.empty()) {
int n = nodes.pop();
if (n < 0 || n > 360)
continue;
if (board[n] == targetColor) {
board[n] = replacementColor;
if (n % 19 > 0)
nodes.push(n - 1);
if (n % 19 < 18)
nodes.push(n + 1);
if (n / 19 > 0)
nodes.push(n - 19);
if (n / 19 < 18)
nodes.push(n + 19);
}
}
}
char center = board[180];
for (char c : board)
if (c != center) {
s.close();
b.close();
System.out.println("\nIncomplete board found!\n\tOn line " + lineNum + " of steps.txt");
System.exit(0);
}
if (lineNum % 5000 == 0)
System.out.printf("Verification %d%c complete...\n", lineNum * 100 / 100000, '%');
lineNum++;
}
s.close();
b.close();
System.out.println("All boards solved successfully.");
}
}
Juga, papan skor, karena hasilnya tidak benar-benar diurutkan berdasarkan skor dan di sini itu sangat penting:
- 1.985.078 - smack42, Jawa
- 2.075.452 - user1502040, C
- 2.098.382 - tigrou, C #
- 2.155.834 - CoderTao, C #
- 2.201.995 - MrBackend, Jawa
- 2.383.569 - CoderTao, C #
- 2.384.020 - Herjan, C
- 2.403.189 - Origineil, Jawa
- 2.445.761 - Herjan, C
- 2.475.056 - Daftar Jeremy, Haskell
- 2.480.714 - SteelTermite, C (2.395 byte)
- 2.480.714 - Herjan, Jawa (4,702 bytes)
- 2.588.847 - BurntPizza, Java (2,748 bytes)
- 2.588.847 - Gero3, node.js (4,641 bytes)
- 2.979.145 - Teun Pronk, Delphi XE3
- 4.780.841 - BurntPizza, Jawa
- 10.800.000 - Joe Z., Python
Jawaban:
Java - 1.985.078 langkah
https://github.com/smack42/ColorFill
Entri terlambat lainnya. File hasil yang berisi langkah-langkah 1.985.078 dapat ditemukan di sini .
Beberapa info latar belakang:
Saya menemukan tantangan ini beberapa tahun yang lalu, ketika saya mulai memprogram klon saya sendiri dari game Flood-it.
Algoritma DFS dan A * "terbaik-tidak lengkap"
Sejak awal, saya ingin membuat algoritma pemecah yang baik untuk game ini. Seiring waktu, saya dapat memperbaiki solver saya dengan memasukkan beberapa strategi yang melakukan pencarian tidak lengkap berbeda (mirip dengan yang digunakan dalam program lain di sini) dan dengan menggunakan hasil terbaik dari strategi tersebut untuk setiap solusi. Saya bahkan menerapkan kembali algoritma A * tigrou di Java dan menambahkannya ke solver saya untuk mencapai solusi keseluruhan yang lebih baik daripada hasil tigrou.
Algoritma DFS lengkap
Lalu saya fokus pada algoritma yang selalu menemukan solusi optimal. Saya menghabiskan banyak upaya untuk mengoptimalkan strategi pencarian mendalam-pertama saya. Untuk mempercepat pencarian, saya menyertakan peta hash yang menyimpan semua status yang dieksplorasi, sehingga pencarian dapat menghindari menjelajahinya lagi. Meskipun algoritma ini berfungsi dengan baik dan menyelesaikan semua 14x14 teka-teki dengan cukup cepat, ia menggunakan terlalu banyak memori dan berjalan sangat lambat dengan 19x19 teka-teki dalam tantangan kode ini.
Algoritma Puchert A *
Beberapa bulan yang lalu saya dihubungi untuk melihat pemecah Flood-It oleh Aaron dan Simon Puchert . Program itu menggunakan algoritma tipe A * dengan heuristik yang dapat diterima (berbeda dengan tigrou) dan memindahkan pemangkasan yang mirip dengan Pencarian Titik-Langsung. Saya dengan cepat memperhatikan bahwa program ini sangat cepat dan menemukan solusi optimal !
Tentu saja, saya harus mengimplementasikan kembali algoritma yang hebat ini dan menambahkannya ke program saya. Saya berupaya mengoptimalkan program Java saya agar berjalan secepat program C ++ asli oleh saudara-saudara Puchert. Kemudian saya memutuskan untuk mencoba 100.000 uji kasus dari tantangan ini. Di mesin saya, program berjalan selama lebih dari 120 jam untuk menemukan 1.985.078 langkah, menggunakan implementasi saya dari algoritma Puchert A * .
Ini menjadi solusi terbaik untuk tantangan ini, kecuali ada beberapa bug dalam program yang akan menghasilkan solusi yang kurang optimal. Umpan balik apapun diterima!
sunting: menambahkan bagian kode yang relevan di sini:
kelas AStarPuchertStrategy
bagian dari kelas AStarSolver
bagian dari kelas AStarNode
sumber
C # - 2.098.382 langkah
Saya mencoba banyak hal, kebanyakan dari mereka gagal dan tidak berfungsi sama sekali, sampai saat ini. Saya mendapat sesuatu yang cukup menarik untuk mengirim jawaban.
Pasti ada cara untuk meningkatkan ini lebih jauh. Saya pikir akan di bawah langkah 2M mungkin.
Butuh kira-kira
7 hours
untuk menghasilkan hasil. Ini adalah file txt dengan semua solusi, jika seseorang ingin memeriksanya: results.zipLebih detail tentang cara kerjanya:
Ini menggunakan algoritma A * Pathfinding .
Yang sulit adalah menemukan yang baik
heuristic
. Jikaheuristic
itu meremehkan biaya, itu akan tampil seperti hampir seperti algoritma Dijkstra dan karena kompleksitas papan 19x19 dengan 6 warna itu akan berjalan selamanya. Jika itu melebih-lebihkan biayanya, ia akan menyatu dengan cepat ke sebuah solusi tetapi tidak akan memberikan yang baik sama sekali (sesuatu seperti 26 gerakan adalah 19 adalah mungkin). Menemukan yang sempurnaheuristic
yang memberikan jumlah langkah yang tepat untuk mencapai solusi adalah yang terbaik (akan cepat dan akan memberikan solusi sebaik mungkin). Tidak mungkin (kecuali saya salah). Sebenarnya perlu menyelesaikan papan itu sendiri terlebih dahulu, sementara ini yang sebenarnya Anda coba lakukan (masalah ayam dan telur)Saya mencoba banyak hal, inilah yang bekerja untuk
heuristic
:node
mewakili satu set kotak, berdekatan berwarna sama. Menggunakan itugraph
, saya dapat dengan mudah menghitung jarak minimal yang tepat dari pusat ke node lain. Misalnya jarak dari tengah ke kiri atas adalah 10, karena minimal 10 warna memisahkannya.heuristic
: Saya memainkan papan saat ini sampai akhir. Untuk setiap langkah, saya memilih warna yang akan meminimalkan jumlah jarak dari root ke semua node lainnya.Jumlah gerakan yang diperlukan untuk mencapai tujuan tersebut adalah
heuristic
.Estimated cost
(digunakan oleh A *) =moves so far
+heuristic
Ini tidak sempurna karena sedikit melebih-lebihkan biaya (sehingga solusi yang tidak optimal ditemukan). Pokoknya itu cepat untuk menghitung dan memberikan hasil yang baik.
Saya bisa mendapatkan peningkatan kecepatan besar dengan menggunakan grafik untuk melakukan semua operasi. Pada awalnya saya punya
2-dimension
array. Saya membanjiri dan menghitung ulang grafik bila diperlukan (misalnya: untuk menghitung heuristik). Sekarang semuanya dilakukan dengan menggunakan grafik, yang dihitung hanya di awal. Untuk mensimulasikan langkah-langkah, mengisi banjir tidak diperlukan lagi, saya menggabungkan node sebagai gantinya. Ini jauh lebih cepat.sumber
code blocks
untuk menekankan teks. Kami memiliki huruf miring dan berani untuk itu.Python - 10.800.000 langkah
Sebagai solusi referensi tempat terakhir, pertimbangkan urutan ini:
Bersepeda melalui semua waktu warna
n
berarti setiapn
langkah persegi akan dijamin dengan warna yang sama dengan pusat persegi. Setiap kotak paling banyak 18 langkah dari pusat, jadi 18 siklus akan menjamin semua kotak memiliki warna yang sama. Kemungkinan besar itu akan selesai dalam waktu kurang dari itu, tetapi program tidak diharuskan untuk berhenti begitu semua kotak berwarna sama; itu jauh lebih bermanfaat untuk melakukannya. Prosedur konstan ini adalah 108 langkah per test case, dengan total 10.800.000.sumber
1 2 3 4 5 6 ...
bukan solusi Anda saat ini yang memberi123456...
.Jawa - 2.480.714 langkah
Saya membuat sedikit kesalahan sebelumnya (saya meletakkan satu kalimat penting sebelum satu lingkaran, bukan dalam satu lingkaran:
sumber
C - 2,075,452
Saya tahu saya sangat terlambat ke pesta, tetapi saya melihat tantangan ini dan ingin mencobanya.
Algoritma ini didasarkan pada Pencarian Pohon Monte-Carlo dengan pengambilan sampel Thompson, dan tabel transposisi untuk mengurangi ruang pencarian. Butuh sekitar 12 jam di mesin saya. Jika Anda ingin memeriksa hasilnya, Anda dapat menemukannya di https://dropfile.to/pvjYDMV .
sumber
hash ^= zobrist_table[i][(int)solution[i]];
untuk mengubahhash ^= zobrist_table[i%len][(int)solution[i]];
untuk memperbaiki crash program.Jawa -
2.434.1082.588.847 langkahSaat ini menang (~ 46K di atas Herjan) pada 4/26Welp, jadi bukan hanya MrBackend mengalahkan saya, tetapi saya menemukan bug yang menghasilkan skor yang sangat bagus. Sudah diperbaiki sekarang (juga di verifikasi! Ack), tapi sayangnya saya tidak punya waktu saat ini untuk mencoba dan mengambil kembali mahkota. Akan berusaha nanti.
Ini didasarkan pada solusi saya yang lain, tetapi alih-alih mengecat dengan warna yang paling umum pada tepi isian, cat ini melukis dengan warna yang akan menghasilkan pinggiran yang memiliki banyak kotak yang berdekatan dengan warna yang sama. Sebut saja LookAheadPainter. Saya akan golf nanti jika perlu.
EDIT: Saya menulis verifier, jangan ragu untuk menggunakannya, ia mengharapkan file steps.txt yang berisi langkah-langkah output program Anda dan juga file floodtest: Edit-Edit: (Lihat OP)
Jika ada yang menemukan masalah, tolong laporkan kepada saya!
sumber
C - 2.480.714 langkah
Masih belum optimal, tetapi sekarang lebih cepat dan skor lebih baik.
sumber
Java -
2.245.5292.201.995 langkahPencarian pohon paralel & caching pada kedalaman 5, meminimalkan jumlah "pulau". Karena peningkatan dari kedalaman 4 ke kedalaman 5 sangat kecil, saya tidak berpikir ada banyak gunanya memperbaikinya lebih jauh. Tetapi jika perlu perbaikan, firasat saya mengatakan untuk bekerja dengan menghitung jumlah pulau sebagai perbedaan antara dua negara, bukannya menghitung ulang semuanya.
Saat ini output ke stdout, sampai saya tahu format input verifier.
sumber
24
akan menghasilkan runtime yang jauh lebih efisien.Entri Terakhir Saya: C - 2.384.020 langkah
Kali ini yang 'periksa semua kemungkinan' ... Skor ini diperoleh dengan Kedalaman yang ditetapkan pada 3. Kedalaman pada 5 harus memberikan ~ langkah 2.1M ... TERLALU LAMBAT. Kedalaman 20+ memberikan jumlah langkah seminimal mungkin (hanya memeriksa semua pertandingan dan kemenangan tersingkat dari kursus) ... Ini memiliki jumlah langkah paling sedikit, meskipun saya benci karena ini hanya sedikit lebih baik, tetapi kinerjanya payah. Saya lebih suka entri C saya yang lain, yang juga ada di posting ini.
Peningkatan AI lainnya ditulis dalam langkah C - 2.445.761
Berdasarkan SteelTermite:
sumber
Java -
2.610.7974.780.841 langkah(Isi-Bug diperbaiki, skor sekarang secara dramatis lebih buruk -_-)
Ini adalah pengajuan algoritma referensi dasar saya, cukup membuat histogram dari kotak di tepi area yang dicat, dan melukis dengan warna yang paling umum. Menjalankan 100k dalam beberapa menit.
Jelas tidak akan menang, tetapi tentu saja itu tidak bertahan lama. Saya mungkin akan membuat pengajuan lain untuk hal-hal pintar. Jangan ragu untuk menggunakan algoritma ini sebagai titik awal.
Hapus komentar pada baris komentar untuk output penuh. Default untuk mencetak # langkah yang diambil.
Golf hingga 860 karakter (tidak termasuk baris baru untuk format), tetapi bisa menyusut lebih banyak jika saya ingin mencoba:
sumber
Haskell - 2.475.056 langkah
Algoritma mirip dengan yang disarankan oleh MrBackend dalam komentar. Perbedaannya adalah: sarannya menemukan jalur termurah ke kuadrat biaya tertinggi, tambang dengan rakus mengurangi eksentrisitas grafik di setiap langkah.
sumber
C # - 2.383.569
Ini adalah traversal mendalam dari solusi yang mungkin yang secara kasar memilih jalur peningkatan terbaik (mirip / sama dengan entri C Herjan), kecuali saya dengan cerdik membalik urutan kandidat generasi solusi setelah melihat Herjan memposting angka yang sama. Butuh 12+ jam untuk menjalankannya.
sumber
Jawa - 2.403.189
Ini seharusnya menjadi upaya saya pada kekuatan brutal. Tapi! Implementasi pertama saya dari pilihan "terbaik" dalam kedalaman tunggal menghasilkan:
Kode yang digunakan untuk keduanya sama dengan brute force yang menyimpan "snapshot" dari gerakan lain yang mungkin dan menjalankan algoritma di atas semuanya.
Jika berjalan dengan pendekatan "multi" pass kegagalan acak akan terjadi. Saya mengatur 100 entri puzzle pertama dalam unit test dan dapat mencapai 100% lulus tetapi tidak 100% dari waktu. Untuk mengimbanginya, saya baru saja melacak nomor puzzle saat ini pada waktu yang gagal dan memulai Thread baru untuk mencari di mana yang terakhir ditinggalkan. Setiap utas menulis hasil masing-masing ke file. Kumpulan file kemudian diringkas menjadi satu file.
Node
mewakili ubin / kotak papan dan menyimpan referensi ke semua tetangga itu. Lacak tigaSet<Node>
variabel:Remaining
,Painted
,Targets
. Setiap iterasi melihatTargets
untuk mengelompokkan semuacandidate
node berdasarkan nilai, memilihtarget value
dengan jumlah "terpengaruh" node. Node yang terkena dampak ini kemudian menjadi target untuk iterasi berikutnya.Sumber tersebar di banyak kelas dan cuplikan tidak terlalu berarti dari konteks keseluruhan. Sumber saya dapat diakses melalui GitHub . Saya juga bermain- main dengan demo JSFiddle untuk visualisasi.
Namun demikian, metode kerja keras saya dari
Solver.java
:sumber
C # -
2.196.4622.155.834Ini secara efektif sama dengan pendekatan 'mencari keturunan terbaik' seperti pemecah saya yang lain, tetapi dengan beberapa optimisasi yang nyaris, dengan paralelisme, memungkinkannya mencapai kedalaman 5 dalam waktu kurang dari 10 jam. Dalam proses pengujian ini saya juga menemukan bug di aslinya, sehingga algoritma kadang-kadang akan mengambil rute yang tidak efisien ke keadaan akhir (itu tidak memperhitungkan kedalaman negara dengan skor = 64; ditemukan saat bermain-main dengan hasil kedalaman = 7).
Perbedaan utama antara ini dan pemecah sebelumnya adalah bahwa ia menyimpan Flood Game States dalam memori, sehingga tidak harus membuat ulang 6 ^ 5 status. Berdasarkan penggunaan CPU selama menjalankan, saya cukup yakin ini telah pindah dari CPU terikat ke bandwidth memory terikat. Sangat menyenangkan. Begitu banyak dosa.
Sunting: Karena alasan, algoritme kedalaman 5 tidak selalu menghasilkan hasil terbaik. Untuk meningkatkan kinerja, mari lakukan kedalaman 5 ... dan 4 ... dan 3 dan 2 dan 1, dan lihat mana yang terbaik. Apakah mencukur gerakan 40k lain. Karena kedalaman 5 adalah sebagian besar waktu, menambahkan 4 hingga 1 hanya meningkatkan runtime dari ~ 10 jam hingga ~ 11 jam. Yay!
sumber
Delphi XE3 2.979.145 langkah
Ok jadi ini usaha saya. Saya menyebut bagian pengubah gumpalan, setiap belokan akan membuat salinan array dan menguji setiap warna yang mungkin untuk melihat warna mana yang akan memberikan gumpalan terbesar.
Menjalankan semua teka-teki dalam 3 jam dan 6 menit
Berpikir tentang metode backtracing bruteforce juga.
Mungkin menyenangkan untuk akhir pekan ini ^^
sumber
Javascript / node.js - 2.588.847
Algoritme agak berbeda daripada kebanyakan di sini karena menggunakan daerah yang dihitung sebelumnya dan perbedaan status antar perhitungan. Ini berjalan di bawah 10 menit di sini jika Anda khawatir tentang kecepatan karena javascript.
sumber
Kode C yang dijamin untuk menemukan solusi optimal dengan kekuatan kasar sederhana. Bekerja untuk kisi ukuran yang sewenang-wenang dan semua input. Butuh waktu yang sangat, sangat lama untuk dijalankan di sebagian besar grid.
Isi banjir sangat tidak efisien dan bergantung pada rekursi. Mungkin perlu membuat tumpukan Anda lebih besar jika sangat kecil. Sistem brute force menggunakan string untuk menahan angka dan menambahkan-dengan-carry sederhana untuk menggilir semua opsi yang mungkin. Ini juga sangat tidak efisien karena mengulangi sebagian besar langkah segi empat kali.
Sayangnya saya tidak dapat mengujinya terhadap semua kasus uji, karena saya akan mati karena usia tua sebelum selesai.
Sejauh yang saya tahu ini adalah pemenang saat ini. Kompetisi mensyaratkan bahwa:
Memeriksa
Karena ini selalu menemukan jumlah langkah terendah untuk menyelesaikan setiap papan dan tidak ada yang melakukannya, saat ini ada di depan. Jika seseorang dapat membuat program yang lebih pendek, mereka dapat menang, jadi saya menyajikan versi teroptimalkan ukuran berikut. Eksekusi sedikit lebih lambat, tetapi waktu eksekusi bukan bagian dari kondisi kemenangan:
sumber