SpawELO - ระบบจับคู่แมตช์ขนาดเล็กฟรีสำหรับ LAN party
(blog.spawek.com)- SpawELO ถูกสร้างขึ้นเพื่อทำให้การเลือกทีมเป็นอัตโนมัติ หลังจากการเลือกทีม Dota 2 ด้วยมือใน LAN party ของกลุ่มเพื่อนที่จัดต่อเนื่องมา 16 ปีเริ่มยากขึ้นเรื่อย ๆ
- เนื่องจากความต่างของฝีมือและจำนวนผู้เข้าร่วมที่เปลี่ยนแปลงตลอด การดราฟต์ด้วยมือจึงมักทำให้เกิด ทีมหน้าตาคล้ายเดิมซ้ำ ๆ และความไม่สมดุลเมื่อมีผู้เล่นเป็นจำนวนคี่
- การทำงานรุ่นแรกใช้แมตช์ย้อนหลัง 35 เกมและ คะแนน Elo เพื่อหาชุดทีมที่มีผลรวมคะแนนใกล้เคียงกันที่สุด จากนั้นปรับคะแนนซ้ำ ๆ โดยนำผลการแข่งขันเข้ามาสะท้อนเพิ่มเติม
- หลังเปลี่ยนเป็นโมเดลทำนายอัตราชนะ ได้ปรับ Elo ของผู้เล่นด้วย L2 loss และ backpropagation แต่เมื่อถือว่าชัยชนะทุกครั้งเป็น 100% ก็เกิด overfitting ที่เหมือนจดจำแมตช์ในอดีต
- วิธีสุดท้ายมองผลการแข่งขันเป็น ชัยชนะแบบความน่าจะเป็น ที่ 75% หรือ 95% เพื่อลด overfitting และตั้งเป้าจับคู่ทีมที่ใช้ได้แม้ในจำนวนผู้เล่นคี่ เช่น 4v5
ปัญหาการเลือกทีมที่เห็นชัดใน LAN party
- กลุ่มเพื่อนจัด LAN party อย่างน้อยปีละครั้งมาตลอด 16 ปี โดยปกติจัด 4–5 วัน และช่วงพีคมีผู้เข้าร่วมประมาณ 12 คน
- เกมหลักคือ Dota 2 และยังเล่นเกมอื่นร่วมด้วย เช่น Counter-Strike, Wolfenstein: Enemy Territory, Warcraft 3 และ Blobby Volley
- ผู้เข้าร่วมมีเวลาเดินทางมาถึงและกลับไม่เหมือนกัน บางคนต้องออกไปดูแลลูกระหว่างงาน ทำให้จำนวนคนที่เล่นแต่ละเกมไม่เท่ากันทุกครั้ง
- Dota 2 ปกติเล่นแบบ 5v5 และหนึ่งเกมใช้เวลาประมาณ 40 นาที แมตช์ที่ไม่สมดุลอย่าง 4v5 จึงมักเอนไปทางฝ่ายหนึ่งได้ง่าย
- ในกลุ่มมีทั้งคนที่เล่น Dota 2 เป็นประจำและคนที่เล่นเฉพาะตอน LAN party ทำให้ ช่องว่างด้านฝีมือ ค่อนข้างมาก
ข้อจำกัดของการดราฟต์ด้วยมือ
- วิธีเดิมมักให้ผู้เล่นที่เก่งที่สุดหรือมีประสบการณ์น้อยที่สุดสองคนเป็นหัวหน้าทีม แล้วผลัดกันเลือกสมาชิกเหมือนเลือกทีมในสนามกีฬาที่โรงเรียน
- ลำดับการเลือกคือหัวหน้าคนแรกเลือก 1 คน หัวหน้าคนที่สองเลือก 2 คน จากนั้นหัวหน้าคนแรกกลับมาเลือกครั้งละ 2 คน และตอนท้ายหัวหน้าแต่ละคนเลือกอีกคนละ 1 คน
- เป็นการดัดแปลงเพื่อลดความได้เปรียบของฝ่ายที่ได้เลือกก่อน
- เนื่องจากความต่างของฝีมือสูง ผลลัพธ์จึงมักกลายเป็นทีมที่คล้ายกันหรือทีมเดิมซ้ำ ๆ และความสนุกของการดราฟต์ทุกครั้งก็ลดลง
- การเลือกทีมด้วยมือใช้เวลาและยุ่งยาก อีกทั้งมีปัญหาว่าไม่มีใครอยากรับบทหัวหน้าทีม
- โดยเฉพาะเมื่อจำนวนผู้เล่นไม่พอดี ความไม่สมดุลของทีม จะยิ่งมากขึ้น
การทำงานรุ่นแรก: แมตช์ย้อนหลังและผลรวม Elo
- เมื่อความไม่พอใจต่อกระบวนการเลือกทีมเพิ่มขึ้นใน LAN party ครั้งล่าสุด จึงรีบเขียนโค้ดอัตโนมัติขึ้นมา
- เริ่มจากรวบรวมข้อมูลแมตช์ย้อนหลัง 35 เกมใส่ใน Colab โดยแต่ละเกมมีรายชื่อผู้เล่นของทีมชนะและทีมแพ้
- แนวคิดพื้นฐานคือคำนวณคะแนนผู้เล่นด้วย Elo rating
- ผู้เล่นทุกคนเริ่มที่ 1000 คะแนน
- ชนะแล้วได้คะแนน แพ้แล้วเสียคะแนน
- คำนวณอัตราชนะจากความต่าง Elo ของผู้เล่นสองคนเท่านั้น
- การทำงานแบบง่ายรุ่นแรกคือเพิ่ม 20 คะแนนให้ผู้เล่นที่ชนะ และลด 20 คะแนนจากผู้เล่นที่แพ้
- การจัดทีมสร้างขึ้นโดยดูชุดผสมทั้งหมดของผู้เล่นที่ถูกร้องขอ แล้วเลือกชุดที่มีความต่างของ ผลรวม Elo ของทีม น้อยที่สุด
- ในตัวอย่าง แบ่งผู้เล่น 8 คนออกเป็นสองทีม ทีมหนึ่งได้ 4100 คะแนน อีกทีมได้ 4080 คะแนน
โมเดล Elo ที่ปรับปรุงด้วยการคำนวณซ้ำ
- มองว่าการไล่ดูแมตช์ 35 เกมเพียงครั้งเดียวใช้ข้อมูลไม่เต็มที่ จึงประมวลผลข้อมูลแมตช์ย้อนหลังซ้ำหลายรอบ
- การอัปเดต Elo ที่ปรับปรุงแล้วไม่ใช่แค่ใช้ ±20 คะแนนแบบง่าย แต่เป็นโครงสร้างที่หากชนะคู่แข่งที่แข็งแกร่งกว่าจะได้คะแนนมากขึ้น และหากแพ้คู่แข่งที่แข็งแกร่งกว่าจะเสียคะแนนน้อยลง
- ตัวอย่างเช่น Spawek ที่มี 1260 คะแนนชนะ Goovie ที่มี 900 คะแนน จะได้เพิ่มเพียง 4.47 คะแนน
- Status ที่มี 900 คะแนนชนะ Dragon ที่มี 1100 คะแนน จะได้เพิ่ม 30.38 คะแนน
- เนื่องจากไม่ได้คำนวณแบบตัวต่อตัว แต่คำนวณในระดับทีม จึงใช้ ผลรวม Elo ของทีม ฝ่ายชนะและฝ่ายแพ้ และแบ่งคะแนนอัปเดตให้สมาชิกทีมเท่า ๆ กัน
- วิธีนี้ถูกใช้ระหว่าง LAN party ด้วย และหลังจบแต่ละเกมสามารถเพิ่มข้อมูลใหม่เพื่อสร้างทีมใหม่สำหรับช่วงที่เหลือของงานได้
- บางครั้งเมื่อระบบสร้างแมตช์ที่ไม่สมดุลอย่างชัดเจน ก็จะเพิ่ม “แมตช์ปลอม” ที่ใส่ผู้ชนะที่คาดไว้ลงในข้อมูล แล้วสร้างทีมใหม่อีกครั้ง
การปรับปรุงครั้งที่สองโดยเปลี่ยนเป็นโมเดลทำนายอัตราชนะ
- การปรับปรุงถัดมาคือมอง Elo ไม่ใช่แค่ตารางคะแนนธรรมดา แต่เป็นเหมือน โมเดล สำหรับทำนายอัตราชนะของทีม
- โมเดลเก็บ Elo ของผู้เล่นแต่ละคน และคำนวณความน่าจะเป็นที่จะชนะโดยเปรียบเทียบ
SUM(Elo)ของสองทีม - ใช้ L2 loss แบบง่ายกับข้อมูลการแข่งขันทั้งหมด
- คำนวณผลรวม Elo ของทีมชนะและทีมแพ้
- คำนวณความน่าจะเป็นที่จะชนะ
- ยกกำลังสองความต่างระหว่างความน่าจะเป็นจริงกับความน่าจะเป็นที่ทำนาย แล้วบวกเข้าเป็น loss
- การฝึกใช้ backpropagation
- คำนวณอัตราชนะที่ทำนายด้วย forward propagation
- ใช้อนุพันธ์ของ loss และฟังก์ชันอัตราชนะเพื่อคำนวณว่า Elo ของผู้เล่นแต่ละคนส่งผลต่อ loss แค่ไหน
- อัปเดตค่า Elo ด้วย
LEARNING_RATE = 10_000.0,ITERATIONS = 10001
- วิธีนี้ลด loss ได้สำเร็จ แต่ค่า Elo ไม่ converge
ผลการแข่งขันแบบความน่าจะเป็นเพื่อลด overfitting
- โมเดลแบบ ML เกิด overfitting เพราะปฏิบัติต่ออัตราชนะจริงของแมตช์ในอดีตทั้งหมดเป็น 1.0 หรือ ชนะ 100%
- เมื่อโมเดลไม่ได้ generalize แต่จดจำแต่ละแมตช์ บางเกมจึงมีอัตราชนะที่ทำนายใกล้ 1 มาก เช่น 0.999994567526197
- เป้าหมายไม่ใช่การ encode ผลลัพธ์ในอดีตไว้ตรง ๆ แต่คือการจัดทีมที่ดี จึงเปลี่ยนมาใช้ผลลัพธ์แบบความน่าจะเป็นแทนผลแพ้ชนะที่ตายตัว
- ตรวจสอบบันทึกแมตช์ย้อนหลังเพิ่มเติม แล้วแบ่งลักษณะเกมออกเป็นสองประเภท
- เกมที่สูสีกำหนดให้อัตราชนะจริงของทีมชนะเป็น 75%
- เกมที่เอนไปทางฝ่ายหนึ่งอย่างชัดเจนกำหนดให้อัตราชนะจริงของทีมชนะเป็น 95%
- ความต่าง Elo ที่จำเป็นสำหรับอัตราชนะ 75% อยู่ที่ประมาณ 200 คะแนน ส่วนความต่าง Elo ที่จำเป็นสำหรับอัตราชนะ 100% อยู่ในช่วงประมาณ 500 คะแนนจนถึงอนันต์ จึงทำให้โมเดลจดจำทุกเกมได้ยากขึ้น
- หลังเปลี่ยนให้ฟังก์ชัน
lossและbackpropagationใช้real_probability = game["win_probability"]แทนreal_probability = 1ค่า loss ก็ลดลงอย่างรวดเร็ว และ Elo ของผู้เล่นก็ converge ในระดับที่สมเหตุสมผล
ไลน์อัปที่สร้างได้แม้มีจำนวนผู้เล่นคี่
- ระบบใหม่สามารถทำนายความน่าจะเป็นที่จะชนะและสร้างทีมได้แม้เป็นทีมที่มี จำนวนผู้เล่นคี่
- ตัวอย่างไลน์อัปแรกของ LAN party ที่จะเริ่มในอีก 2 สัปดาห์เป็นดังนี้
- team 1: Elo 2660
- team 2: Elo 2655
- ไลน์อัปตัวอย่างเป็นโครงสร้างที่ฝ่ายหนึ่งมี 4 คน และอีกฝ่ายมี 5 คน
- team 1: Spawek, Bixkog, Bania, Goovie
- team 2: Hypys, Muhah, J, Vifon, Status
1 ความคิดเห็น
ความคิดเห็นใน Hacker News
สงสัยว่ามีใครเคยใช้วิธีที่ไม่ได้อิง Elo/TrueSkill ในเกมแบบทีมบ้างไหม
การจับคู่ด้วยการรวม Elo ของทีม หรือเอามาเฉลี่ยกัน รู้สึกเหมือนเป็นวิธีแก้ขัดที่ยัดโมเดลสำหรับการจับคู่รายบุคคลให้มาใช้กับการจับคู่แบบทีม
อีกทั้งยังทำให้ข้อมูลเรื่อง ความเข้ากันได้ภายในทีม หายไปมาก เช่น A กับ B เล่นด้วยกันแล้วแข็งแกร่งกว่าผลรวม Elo รายบุคคล แต่ A กับ C เล่นด้วยกันแล้วอ่อนลง
ในกีฬา ต่อให้ทีมแพ้ หลังจบฤดูกาลก็อาจมีผู้เล่นติด All-Star หรือได้ MVP ได้ และในทางกลับกัน ถึงอยู่ในทีมแชมป์ก็อาจไม่ใช่ตัวหลัก
อีสปอร์ตแบบทีมให้ทุกอย่างผูกกับชัยชนะ จึงติดตามหรือยอมรับการแสดงออกของผู้เล่นอย่างกองหลัง กองหน้า หรือซัพพอร์ตระดับท็อปของลีกโดยรวมได้ไม่ดี
ควรติดตามและสะท้อน สถิติขั้นสูง ในระดับหนึ่งเหมือนกีฬาหลายประเภท ผู้เล่นไม่ได้ใกล้เคียงกับ Elo เอง แต่ใกล้เคียงกับค่าต่าง ๆ เช่น แอสซิสต์ต่อเกม รีบาวด์ คะแนนที่ทำได้ RBI หรือจำนวนหลา
ถ้าเป็นแบบนั้นก็จะเห็นได้ง่ายว่าทีมต้องการการทำคะแนนเพิ่ม หรือต้องการเกมรับเพิ่ม ทำให้การจับคู่ลงตัวได้เป็นธรรมชาติกว่าแค่ “ต้องการผู้ชนะเพิ่ม/ต้องการผู้แพ้เพิ่ม”
จุดแข็งของ Elo คือให้ข้อมูลคุ้มเมื่อเทียบกับต้นทุน ประเด็นสำคัญคือมันเป็นตัวเลขเดียวที่แทนทุกอย่าง
มันอธิบายความหลากหลายอันงดงามของธรรมชาติได้ไม่สมบูรณ์ แต่ก็ใกล้เคียงกับ นามธรรมที่มีประสิทธิภาพที่สุด ซึ่งบรรจุประมาณ 70% ของสิ่งที่ควรรู้เกี่ยวกับฝีมือคู่แข่ง
ถ้ามี เวกเตอร์ทักษะผู้เล่นหลายมิติ หรือ embedding ที่เก็บข้อมูลได้มากกว่า และมีโมเดลที่ไม่เชิงเส้นมากขึ้นวางอยู่บนมันก็คงดี
เช่น ในหลายเกม ทีมมักต้องมีผู้เล่นซัพพอร์ต แต่ตัวเลขเดียวไม่พอจะใส่ข้อมูลนั้นเข้าไปในการจับคู่
เช่น ในโต๊ะฟุตบอล มีผู้เล่นที่เล่นทั้งเดี่ยวและคู่ แต่กองหลังเก่ง ๆ สองคนมาอยู่ทีมเดียวกันก็อาจแพ้คู่แข่งที่อ่อนกว่าแต่เหมาะกับแต่ละตำแหน่งมากกว่าได้
เกมที่ทีมช่วยแบกกันได้มากอย่าง Counter-Strike, Apex, Overwatch และในระดับหนึ่ง Dota ก็แตกต่างกัน ใน Counter-Strike สมาชิกทีมที่อ่อนหนึ่งคน หรือไม่มีเฮดเซ็ต อาจทำให้ทั้งเกมพังได้ แต่ใน Overwatch อาจเลือกคลาสซัพพอร์ตแล้วพักอยู่ข้างหลัง รอให้ทีมที่เหลือชนะก็ได้
ยังมีเรื่อง เคมีของทีม ด้วย อย่างที่เห็นในที่ทำงาน ซินเนอร์จีที่เกิดขึ้นเฉพาะบางชุด หรือความต่างของสไตล์การเล่นธรรมดา ๆ ก็เปลี่ยนผลลัพธ์ได้
แม้แต่เกมย่อยที่ดูคล้ายกันอย่างบิลเลียด ผู้เล่นบางคนก็โดดเด่นในประเภทหนึ่ง แต่ไปไม่ค่อยได้ในอีกประเภทหนึ่ง
เหมือนว่า Kaggle เคยมีหรือยังมีการแข่งขันระบบจัดอันดับอยู่
https://www.kaggle.com/competitions/chess/discussion/107
มี ระบบจัดอันดับ อยู่หลายแบบที่ทำผลงานได้ดีกว่า Elo
สำหรับทัวร์นาเมนต์ ผมชอบ ระบบสวิส ซึ่งเท่าที่รู้เป็นที่นิยมในหมากรุก
[1]: https://en.wikipedia.org/wiki/Swiss-system_tournament
ระบบสวิสเหมาะกับผู้เล่นสูงสุดราว 40 คนเมื่อจัด 6 รอบ แต่ถ้าจะเชิญเกิน 100 คน ต้องใช้สายแบบแพ้ 2 ครั้งตกรอบ ไม่อย่างนั้นทัวร์นาเมนต์จะกินเวลาเป็นสัปดาห์
ข้อดีที่สุดคือคุ้มค่าเมื่อเทียบกับต้นทุน ไม่ว่าผลจะเป็นอย่างไร ทุกคนได้เล่นต่อเนื่องตลอดทัวร์นาเมนต์ และเมื่อดำเนินไป คู่แข่งจะถูกปรับให้เข้ากับระดับของตัวเอง จึงสนุกได้สำหรับทุกคน
ผมไม่แน่ใจว่าควรกำหนดจำนวนรอบอย่างไร แต่ก็ไม่รู้ว่ารายละเอียดนั้นเป็นหัวใจสำคัญหรือไม่
จากส่วนวิเคราะห์ เมื่อเทียบกับทัวร์นาเมนต์แบบน็อกเอาต์ หากสมมติว่าไม่มีเสมอ จำนวนรอบที่ต้องใช้เพื่อหาผู้ชนะที่ชัดเจนจะเท่ากับแบบน็อกเอาต์
ข้อดีของระบบสวิสคือไม่คัดใครออก และอันดับสุดท้ายไม่เพียงแสดงผู้ชนะ แต่ยังพอบอกฝีมือสัมพัทธ์ของผู้เข้าร่วมทั้งหมดได้ด้วย
อย่างไรก็ตาม หากผู้เล่นคนใดนำห่างมากเกินไป ก็อาจการันตีแชมป์ก่อนรอบสุดท้าย ทำให้ไม่ได้จบแบบดราม่าเสมอไป
สงสัยว่าลองใช้ ค่า Shapley ดูจะเป็นอย่างไร
แทบจะเหมือนคำนำใน Wikipedia เป๊ะ ๆ แต่อ่านแล้วยังไม่เข้าใจอยู่ดี สงสัยว่าส่วนเกินรวมของเกมร่วมมือในที่นี้คืออะไร เป็นเหมือนปริมาณไม้ที่ทีมรวบรวมได้ใน AoE หรือเปล่า
แล้วการ “แจกแจง” สิ่งนั้นช่วยอย่างไร ก็ยังไม่เข้าใจ แถมรู้สึกว่ามันควรเป็นผลลัพธ์ของเกมมากกว่า ถ้าอธิบายให้ง่าย ๆ ได้ก็คงดี