Ramadhan lalu saya ikut lomba IT yang cukup menarik yang diselenggaralan oleh IIIT Lucknow, India. Lomba ini rangkaian event besar Equinox 2022 yang terdiri dari banyak lomba IT (yang juga unik) dan kegiatan lain. Axelrod Duels adalah lomba yang unik dan kreatif. Pada lomba ini, peserta akan submit source code python, lalu source code tersebut “ditandingkan” dengan source code peserta lain. Kita akan dapat poin dari hasil dari tiap pertandingan, pemenang adalah yang memiliki akumulasi poin tertinggi hingga akhir perlombaan.
Saya alhamdulillah dapat posisi ketiga di lomba ini, tapi sejujurnya saya benar-benar tidak yakin kenapa bisa juara :/ Sudah sempat diskusi dengan peserta lain, tapi karena tidak ada official release jadi masih merasa tidak yakin. Salah satu tujuan post ini selain berbagi konsep lomba yang unik, tapi juga bisa jadi bahan diskusi atau analisis bagaimana source code saya bisa masuk Top-3.
Aturan lengkap perlombaan bisa dibaca di halaman Axelrod Duels, tetapi ringkasan aturan juga akan saya tuliskan di bawah. Halaman itu adalah mirror, karena official page nya sudah ditutup.
Peringkat akhir bisa dilihat di halaman ini.
Aturan Axelrod Duels
- Pada kompetisi ini setiap peserta diharuskan untuk submit sebuah source code python.
- Source code python tersebut harus memiliki sebuah fungsi yang akan menerima input sintaks source code python lain (dalam bentuk string), template disediakan
- Fungsi tersebut harus me-return satu diantara dua string: “cooperate” atau “defect”. Contoh source code yang membaca string dan me-return kedua string secara random.
def random_strategy(opponent_source: str) -> str:
if random() > 0.5: # or, any some threshold in place of 0.5
return 'cooperate'
else:
return 'defect'
Panitia berharap output dari fungsi tersebut dihasilkan dengan memperhatikan source code lawan.
Prisoner’s Dilemma
Lomba ini terinspirasi dari Prisoner’s Dilemma. Bayangkan ada dua pengedar narkoba yang ditangkap, A dan B, lalu ditanya, “Di mana bosmu tinggal?” Keduanya ditanya di tempat yang terpisah sehingga mereka tidak bisa berdiskusi.
- Jika keduanya diam, maka mereka akan dihukum 2 tahun penjara
- Jika A memberi info, dan B diam, maka A akan bebas, dan B akan dihukum 5 tahun penjara
- Sebaliknya, jika B memberi info, dan A diam, maka B akan bebas, dan A akan dihukum 5 tahun penjara
- Jika keduanya memberi informasi, maka mereka berdua akan dihukum 3 tahun penjara.
Jika diperhatikan dari sudut pandang A: Kedua pilihan memberi untung dan rugi, tergantung apa jawaban B. jika A memilih diam saja, dan B juga diam, maka ini menguntungkan bagi A, karena lumayan lah dia hanya dapat 2 tahun. Tetapi, jika ternyata B memberi informasi saat A memilih diam, maka A akan mendapat hukuman 5 tahun. Tentu akan merugikan.
Sebaliknya, kalau A memilih memberi informasi itu juga bukan berarti dia aman. Jika B memilih diam, maka ini keuntungan baginya karena dia akan bebas. Tetapi jika B juga memberi informasi, maka hukuman dia jadi lebih banyak daripada ketika keduanya diam, yakni dari 2 tahun bertambah jadi 3 tahun.
Ini yang menyebabkan dilema!
Dalam perlombaan ini, panitia menggunakan penilaian yang “mirip” dengan konsep prisoner’s dilemma, bedanya kita punya kesempatan untuk membaca kode atau apa yang dibuat oleh lawan:
- +5 jika kodemu dan kode lawan memberi output “cooperate“
- +6 jika kodemu memberi output “defect” dan kode lawan memberi output “cooperate“
- +1 jika kodemu dan kode lawan memberi output “defect“
- 0 jika kodemu memberi output “cooperate” dan kode lawan memberi output “defect“
- -4 jika programmu kehabisan waktu untuk memberi output, dan +4 untuk lawanmu. -4 jika kedua program kehabisan waktu
- -4 jika programmu crash atau memberi output yang tidak valid, dan +4 untuk lawanmu. -4 jika kedua program crash atau memberi output yang tidak valid
Pause dulu bacanya di sini, jika teman-teman pembaca mau mencoba mengerjakannya
Analisis dan Solusi Axelrod Duels
Untuk analisis pertama, saya coba membuat tabel penilaian prisoner’s dilemma ini. Sebagai contoh, untuk kasus yang narkoba tadi bisa dituliskan dalam bentuk tabel berikut:
| A diam | A memberi info | |
| B diam | A – 2 B – 2 | A – 0 B – 5 |
| B memberi info | A – 5 B – 0 | A – 3 B – 3 |
Sekarang kita buat tabel untuk soal Axelrods Duel
| A defect | A cooperate | |
| B defect | A + 1 B + 1 | A + 0 B + 6 |
| B cooperate | A + 6 B + 0 | A + 5 B + 5 |
oke, coba bandingkan kedua tabel di atas. Apakah kalian menemukan suatu yang menarik? Jika kalian menemukannya, berarti selamat! satu poin besar dari lomba ini telah terpecahkan, jika belum, jawabannya adalah: soal Axelrod Duels ternyata bukan soal Prisoner’s Dilemma! Perhatikan, pilihan “defect” selalu memberi keuntungan tidak peduli apapun pilihan lawan dibanding pilihan “cooperate”. Berbeda dengan prisoner’s dilema yang aslinya, kedua pilihan bisa memiliki kelebihan dan kekurangan. (teks putih, biar tidak spoiler silakan di highlight)
Dari poin di atas, kita jadi tahu apa yang sebaiknya kita outputkan, bahkan, kita tidak perlu membaca kode lawan, karena pilihan kita selalu menguntungkan di kasus apapun. Loh kalau semua peserta melakukan seperti itu, lalu bagaimana kita bisa memperoleh poin yang lebih banyak agar bisa menang?
Tentu saja “semua peserta melakukan itu” hanyalah asumsi, karena pastinya akan ada peserta lomba lain menggunakan pendekatan yang berbeda. Dari aturan penilaian dan analisis di atas, kira-kira ada dua cara untuk bisa mendapatkan poin:
- Kita buat lawan “tertipu” dan mengoutputkan pilihan yang salah
- Kita buat program lawan crash atau timeout.
Strategi
1. Buat lawan “salah baca” program kita
Lawan mungkin akan berusaha membaca kode saya dan mengecek apakah kode saya memilih “cooperate” atau “defect”. Maka saya akan buat seakan-akan terus mengoutputkan “cooperate” dan tidak pernah mengoutputkan “defect”, salah satu caranya bisa seperti ini:
...
return "cooperate" # explicitly and put it everywhere in the code
...
return "".join("dxexfxexcxt".split("x")) # print "defect: without "defect"
Ini menguntungkan bagi saya karena kalau lawan mengira saya “cooperate” dan lawan (dengan harapan dia dapat +5) jadi ikutan print “cooperate”, saya akan dapat +6 karena yang sebenarnya terjadi saya melakukan “defect”
Di grup QA, sempat ada yang spill kalau dia mau menggunakan parse tree untuk membaca kodenya. Cara lain yang juga saya lakukan adalah mencoba mengacaukan teknik parsing yang dilakukan lawan (memunculkan cornercase). Maka yang saya lakukan:
def \
strategy(opponent_source: \
str) \
-> str:
...
return "cooperate"
def strategy(opponent_source: str) -> str:
...
return "cooperate"
def strategy(opponent_source: str) -> str:
...
return "".join("dxexfxexcxt".split("x"))
Pada kode di atas, saya membuat beberapa fungsi dengan nama yang sama (di python, hanya fungsi terakhir yang nantinya akan dieksekusi). Selain itu, ada beberapa baris yang saya buat multiline dengan “\”, dan juga banyak saya sebar spasi dan tab tanpa konteks yang harapannya bikin bingung parsing saja :D.
2. Buat program lawan crash
Strategi kedua ini sebenarnya tergantung dari cara ngoding lawan. Harusnya, untuk lawan yang punya cukup pengalaman di Python saya rasa strategi saya ini tidak begitu berhasil.
Pertama, saya buat variabel-variabel menggunakan karakter-karakter yang tidak umum, seperti Emoji bahkan simbol arab. Ketika ada programmer yang tidak membaca file dengan teknik yang benar, bisa akan bikin masalah:
y = "اشكرًاشكرًا" π = 3.14 x = "🙄😰😰🙄"
Cara lain yang juga saya pakai, saya namai String Bomb (ini nama-namain sendiri). Awalnya ragu teknik ini akan berhasil, tapi selama lomba beberapa kali coba non aktifin teknik ini bikin ranking turun. Idenya adalah memperbesar ukuran file source code.
Tapi hati-hati membuat file menjadi berukuran besar bisa juga membuat memory yang kita pakai besar dan bisa jadi bikin program kita crash. Trik yang saya pakai adalah membuat variabel berisi string berukuran tidak terlalu besar, tapi dibuat berkali-kali hingga source code file menjadi besar:
stringbomb = "abcdebcdeabcdebcdeabcdebcdeabcdebcde...." stringbomb = "abcdebcdeabcdebcdeabcdebcdeabcdebcde...." stringbomb = "abcdebcdeabcdebcdeabcdebcdeabcdebcde...." ...
Dengan menyalin variabel yang sama, (berdasarkan eksperimen sendiri, bukan berdasar teori) ini tidak akan membuat memory “meledak” saat kita eksekusi, karena objek string yang tidak terpakai akan terhapus. Dengan teknik ini, saya buat source code saya sampai ukuran sekitar 4MB.
Hasilnya?
Saya kombinasikan teknik-teknik di atas tadi dan menghasilkan source code yang lumayan berantakan, terlihat kompleks, dan susah dibaca. Saya pakai metode emoji dan menyembunyikan defect sejak awal submission, dan membuat cukup lama bertahan di Top-3. Tapi di akhir-akhir Axelrod Duels ranking saya sempat turun hingga hampir tidak masuk Top-10. Saat situ saya nemu ide string bomb dan pemanfaatan “\”-spasi-tab untuk mengacaukan parser, yang entah gimana, berhasil membawa saya jadi juara 3. Alhamdulillah..
Saya sejujurnya tidak tahu apa yang membuat bisa ranking 3. Lawan-lawan saya, saya kira pakai metode yang lebih kompleks (di grup QA sempat ada yang spill kalau pakai ML dan Parse Tree). Metode-metode yang saya pakai juga tidak terlalu berdasar, seperti apakah string bomb benar-benar efektif, atau emoji beneran bisa crash program atau tidak. Karenanya, jika teman-teman pembaca menemukan ada yang menarik untuk didiskusikan seputar solusi saya yang agak gimana, feel free to comment!
Sebagai penutup, saya merasa panitia Axelrod Duels melakukan “kesalahan” dalam mendesain lomba ini, yang mungkin niatnya menjadikan Prisoner Dilemma Challenge menjadi lomba yang sedikit berbeda (kelihatan dari solusi saya). Tapi, overall bener-bener pengalaman yang unik, menarik, dan menyenangkan. Lomba ini membuat saya jadi lebih mengenal Python dan menambah wawasan jenis lomba yang cukup menarik.
