Algoritma Facemash (bag. 1)

Udah pada nonton film keren yang judulnya “The Social Network” belom kawan? Kalo belom, wajib nonton deh! Saya recomended nih film. Film ini bercerita tentang gimana si bossnya Facebook memulai ide dan karirnya. Di film ini nyeritain juga sejarah pembuatan facebook, tapi inti dari film ini menceritakan tentang masalah kalo ternyata ide Facebook bukan asli dari si Mark Zuckerberg, tapi dari 3 temennya di Harvard University, dan dari situ copyright Facebook dipermasalahkan. Yah, inti ceritanya begitulah sedikit aja soalnya postingan kali ini ga ngebahas tentang review film The Social Network, kalo mau lebih lengkap tonton aja filmnya ya!

Di awal film itu, ada suatu scene dimana Mark Zuckerberg (boss Facebook) diputusin sama cewenya dan karena perasaan marahnya dia ke mantannya itu, dia berfikir untuk membuat sebuah website yang membanding-bandingkan ke-“hot”-an para wanita-wanita di kampusnya (hebat banget sampe bisa punya ide begitu). Website tersebut kemudian diberi nama Facemash. Nah, pas nonton film itu, yang kepikiran di kepala saya adalah bagaimana membuat algoritma facemash itu. Di film itu sempat juga dibahas sedikit rumus facemash yang dijelasin temennya Mark yaitu Eduardo. Pas saya liat rumus-rumus yang ditulis di jendela rumahnya, kok kayaknya rumit banget, pake rumus Ekspektasi X terhadap Y gitu deh. Yang ada di kepala saya bikin algoritma kaya gitu aja kayaknya mudah deh, ga perlu pake Ekspektasi X terhadap Y segala, kenapa gak pake algoritma sepakbola aja yang kalo dia menang dapet 3 poin, kalah 0 poin dan seri 1 poin, kan lebih mudah.

Ok, saya coba bikin facemesh tiruan itu pake algoritma sepakbola tadi, menang dia langsung dapet 3 poin tambahan berarti:

SiA = SiA + 3
SiB = SiB + 0
kalo SiA menang dan SiB kalah (berlaku sebaliknya)…

SiA = SiA + 1
SiB = SiB + 1
buat SiA dan SiB seri…

Begitu ajah? Nah, sama gw juga mikirnya “masa begitu aja!”. Kemudian muncul seribu pertanyaan di kepala (#lebay seribu), nih sedikit ilustrasi yang muncul dikepala td:

Misal si A punya poin tinggi, kasih deh 2400, dibandingin sama si B yang punya poin masih rendah, kasih deh 400. Selisihnya kan jadi 2000 poin, nah harusnya kalo si A menang lawan si B itu wajar-wajar aja, tapi kalo si B yang menang? harusnya kan bisa mendongkrak poinnya si B karena ngalahin si A yang poinnya jauh lebih besar. Iya nggak?

Ok, saya stuck cukup lama untuk pikirin ini. Kebetulan saya kuliah di jurusan matematika, saya coba cari teori-teori yang berkaitan dengan itu and I’VE GOT NOTHING BUT TROUBLE!! haha.. Setelah itu, TADAAAA, 3 bulan kemudian secara ga sengaja saya menemukan algoritma namanya Elo Rating System, yaitu algoritma yang dipakai untuk me-rating para grandmaster catur yang gue rasa cocok untuk membuat facemash tiruan ini.

Gimana algoritma Elo Rating bekerja?
Jadi begini, di Elo Rating ini ada Ekspektasi dari si A terhadap si B yang dirumuskan begini:

juga Ekspektasi si B terhadap si A yang dirumuskan:

Atau ekspektasi bisa juga dirumusin seperti ini (yang saya pelajari di kuliah):
Ekspektasi si A dengan syarat si B:

Ekspektasi si B dengan syarat si A:

dimana dan .

dengan
Ea = ekspektasi A terhadap B
Eb = ekspektasi B terhadap A
Ra = rating/poin A
Rb = rating/poin B

Apa sih gunanya Ekspektasi? Jadi Ekspektasi itu adalah nilai yang diharapkan sebelumnya (benerin kalo salah). Nilai Ekspektasi diantara 0 sampai 1, bergantung poin A dan poin B yang dibandingkan. Makin besar perbandingan nilai antara A dan B, nilai ekspektasi akan semakin menuju 0 atau 1. Jika nilai yang dibandingkan hampir sama, maka nilai ekspektasi akan mendekati 0,5. Juga perlu dicatat bahwa Ea + Eb = 1.

Nilai untuk menang, kalah dan seri juga ada di sini tapi pastinya nggak sama dengan sepakbola. Di Elo Rating System ini, kalo si A menang dikasih nilai 1, kalah 0 dan seri 0,5. Selanjutnya nilai ini gue kasih nama Sa, yaitu nilai hasil pertandingan.

Selain nilai hasil pertandingan dan nilai ekspektasi, terdapat sebuah nilai penting di Elo Rating System. Nilai ini berada pada selang kondisi tertentu, yaitu jika poin dari A masih sedikit, pastinya A membutuhkan lebih banyak poin untuk menaikkan level poin yang dimilikinya. Namun jika A telah memiliki poin yang tinggi, dikondisikan A tidak terlalu membutuhkan banyak poin untuk bersaing di level yang ia miliki. Nilai ini biasa disebut faktor-K (K-factor). Tidak ada standar yang tetap untuk nilai K ini. Masing-masing organisasi mempunyai nilai K yang berbeda-beda. Berikut nilai K yang digunakan beberapa federasi catur internasional, antara lain:

FIDE (World Chess Federation)
– K = 25 untuk pemain yang telah bermain minimal 30 pertandingan
– K = 15 untuk pemain dengan poin di bawah 2400
– K = 10 untuk pemain dengan poin di atas 2400

USCF (United States Chess Federation)
– K = 32 untuk pemain dengan poin di bawah 2100
– K = 24 untuk pemain dengan poin antara 2100 sampai 2400
– K = 16 untuk pemain dengan poin di atas 2400

Misalkan data telah terkumpul, dengan Ekspektasi A adalah Ea, nilai hasil pertandingan A adalah Sa, maka perhitungan Elo Rating System adalah:

dengan Ra’ adalah poin A setelah melakukan pertandingan.

Oke kia-kira begitu penjelasan algoritma Elo Rating Systemnya, untuk lebih jelasnya mengenai Elo Rating System, serach aja google, wikipedia atau bisa mendownload paper dari Dr. Mark Glickman di websitenya.

Dan 1 hal yang cukup mengejutkan saya adalah, ternyata algoritma Elo Rating inilah yang ditulis oleh Eduardo di kaca jendela rumah tinggalnya di film The Social Network. Yang ditulis di kaca jendela tersebut adalah perhitungan ekspektasi menggunakan cara pertama (wow.. ternyata pemikiran saya bisa sama, setidaknya sama sutradara filmnya, karena gak tau algoritma asli buatan Mark Zuckerbergnya apakah pake Elo juga atau tidak).

Mungkin bagian 1 cukup sampai disini dulu (udah pusinggg!). Di bagian dua akan dijelaskan penggunaan Elo Rating System dan penulisan algoritma Elo ke bahasa pemrograman PHP.

PS: diperbolehkan mengcopy-paste tulisan ini, namun hargai penulis dengan menyertakan sumbernya: http://hotswaps.blogspot.com, https://hotswaps.wordpress.com.

Wass.

 

Referensi:
http://en.wikipedia.org/wiki/Elo_rating_system
http://www.glicko.net/
Paper “Elo-rating as a tool in the sequential estimation of dominance strengths” oleh PAUL C. H. ALBERS & HAN DE VRIES, Utrecht University
Paper “Rating The Chess Rating System” oleh Mark E. Glickman & Albyn C. Jones, Boston University

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s