Mario gặp Pareto: tối ưu hóa đa mục tiêu cho các build trong Mario Kart

Tìm tổ hợp tối ưu trong Mario Kart 8

• Trong Mario Kart 8, việc chọn tay đua, thân xe, lốp và tà lượn không chỉ là vấn đề phong cách mà còn là yếu tố quan trọng để giành chiến thắng trong cuộc đua.
• Mỗi thành phần có hàng chục lựa chọn, và mỗi lựa chọn đều có các chỉ số ảnh hưởng đến hiệu năng như tốc độ, gia tốc, v.v.
• Ngay cả khi loại bỏ những lựa chọn thiên về phong cách nhưng có chỉ số tương tự nhau, việc tìm ra tổ hợp tốt nhất trong hàng nghìn khả năng vẫn là điều khó khăn.

Tối ưu Pareto

• Việc tìm tay đua có tốc độ cao nhất đơn giản như sắp xếp chỉ số tốc độ của họ theo thứ hạng.
• Nhưng để tìm ra tổ hợp tối ưu, cần cân nhắc sự cân bằng giữa nhiều chỉ số như tốc độ, gia tốc, điều khiển, trọng lượng, off-road và mini-turbo, chứ không chỉ riêng tốc độ.
• Một số lựa chọn luôn bị những lựa chọn khác lấn át, vì vậy có thể loại chúng ra và xác định các tay đua hiệu quả tạo thành biên Pareto.
• Hiệu quả Pareto cung cấp một tiêu chuẩn khách quan để lọc bỏ các lựa chọn không tối ưu, nhưng để đưa ra quyết định cuối cùng vẫn cần xem xét sở thích và phong cách của người chơi.

Tối ưu hóa trong gameplay thực tế

• Trong game thực tế, người chơi không chỉ chọn tay đua mà còn phải chọn trọn bộ gồm thân xe, bánh xe và tà lượn.
• Có 585 tổ hợp với các thuộc tính tốc độ và gia tốc khác nhau, nhưng khi áp dụng phương pháp Pareto có thể thu gọn xuống còn 14 lựa chọn hiệu quả.
• Có thể thêm chỉ số quan trọng thứ ba là mini-turbo và khái quát khái niệm biên Pareto sang không gian ba chiều.
• Trong đa chiều, biên Pareto mở rộng theo cấp số nhân khi số chiều tăng lên, khiến việc lựa chọn trở nên khó hơn.
• Để tìm tổ hợp tối ưu, cần gán trọng số cho từng chiều; các tổ hợp được người chơi hàng đầu ưa chuộng nằm trên biên này khi tối ưu hóa tốc độ, gia tốc và mini-turbo.

Bài toán tối ưu đa mục tiêu

• Những đánh đổi tương tự cũng thường xuyên xuất hiện trong cuộc sống hằng ngày.
• Bữa ăn rẻ mà ngon, công việc lương tốt nhưng dễ làm và thỏa mãn, danh mục đầu tư rủi ro thấp mà lợi nhuận cao, vật liệu linh hoạt nhưng bền chắc và dễ sản xuất, hệ thống thuế công bằng mà hiệu quả, hay LLM có chất lượng cao nhưng nhanh và hiệu quả chi phí — tất cả đều là các bài toán tối ưu đa mục tiêu.
• Nếu biết chính xác các trọng số thì có thể đơn giản hóa thành bài toán tối ưu một mục tiêu, nhưng khi hàm utility không chắc chắn hoặc chưa biết, biên Pareto sẽ giúp loại bỏ khách quan các phương án không tối ưu.

Lời cảm ơn

• Bài viết này đã đơn giản hóa một số giả định để công chúng dễ hiểu hơn.
• Trong game thực tế, các chỉ số không phải lúc nào cũng có quan hệ tuyến tính với chỉ số cơ bản; ngoài ra, với mọi trang bị trừ tay đua còn có 4 chỉ số tốc độ và 4 chỉ số điều khiển, nhưng tác giả quyết định dùng giá trị trung bình.
• Dạng hàm của utility function cũng đóng vai trò quan trọng, nhưng phần này đã được ẩn đi hoàn toàn.
• Nếu muốn biết thêm hậu trường của bài viết này hoặc nhiều thông tin hơn, tác giả có lời kêu gọi cân nhắc ủng hộ bằng đóng góp.

Ý kiến của GN⁺

• Tối ưu Pareto là một công cụ rất hữu ích để đưa ra quyết định tối ưu giữa nhiều lựa chọn khác nhau. Nó có thể được áp dụng không chỉ trong game mà cả trong nhiều tình huống ra quyết định ngoài đời thực.
• Bài viết này sử dụng ví dụ quen thuộc là Mario Kart để giải thích, giúp người đọc có trải nghiệm học hỏi thú vị và dễ hiểu hơn về một bài toán tối ưu hóa phức tạp.
• Tuy nhiên, khi áp dụng thực tế vẫn cần cân nhắc tầm quan trọng của từng chỉ số hoặc các trọng số có thể thay đổi theo bối cảnh, và điều này có thể khác nhau tùy theo sở thích và kinh nghiệm cá nhân của mỗi người.
• Trong các bài toán tối ưu, không chỉ quan trọng ở việc tìm ra phương án hiệu quả mà còn ở quá trình thử nghiệm và trải nghiệm xem phương án đó hoạt động thế nào trong thực tế.
• Bài viết sử dụng một mô hình đơn giản hóa để giải thích, nhưng trong ứng dụng thực tế có thể cần xem xét các mô hình phức tạp hơn hoặc thêm nhiều biến số khác.

[GN⁺]

Ý kiến trên Hacker News

• Bài trình bày đẹp mắt

  • Thật tuyệt khi phần trực quan hóa phục vụ đúng mục đích. Ngay cả Tufte chắc cũng sẽ tự hào.

• Cách tiếp cận thiên về web design

  • Yếu tố web design khá mạnh và có thể phù hợp với khán giả không quá thiên về kỹ thuật. Tuy nhiên, tôi nghĩ bài viết gốc ở dạng notebook cung cấp thông tin hữu ích hơn.

• Lốp đỏ nhỏ trong Mario Kart

  • Tôi luôn biết lốp đỏ nhỏ là tốt nhất. Nhưng vì tôi coi trọng phong cách và tình yêu dành cho Zelda, nên cá nhân tôi đành phải phớt lờ thông tin này.

• Bài trình bày ấn tượng

  • Tôi vốn đã biết về hiệu quả/biên Pareto, nhưng giờ thì sẽ không thể quên nó nữa khi nghĩ đến Mario Kart (và Bowser bị lấn át).

• Cân nhắc dùng như một công cụ thiết kế

  • Tôi thấy thú vị khi nghĩ đến việc, trong thiết kế game, có thể cân nhắc một biên Pareto lớn của những build vừa vui vừa khả thi.

• Kết hợp với Halo Kart (2)

  • Cần suy nghĩ thêm về cách tính toán biên Pareto.

• Lời giải tối ưu bằng thuật toán di truyền

  • Việc xác định sở thích và trọng số rồi dùng thuật toán di truyền để tìm lời giải tối ưu có lẽ đỡ phải suy nghĩ hơn so với việc định nghĩa một hàm điểm và dùng random API.

• Những điểm quan trọng

  • 1. Kỹ năng vẫn là yếu tố quan trọng nhất, còn quan trọng hơn cả chiếc kart bạn chọn hay những thứ tương tự. Nhìn các tuyển thủ chơi bằng những build kỳ lạ, có thể thấy họ vẫn chơi rất hay dù bất lợi.
  • 2. Thực ra không cần biết giá trị của chỉ số mini-turbo ẩn. Vì gia tốc cao đồng nghĩa với mini-turbo cao, nên với đa số người chơi, có thể dùng gia tốc làm chỉ dấu thay cho mini-turbo.

• Đua Mario Kart với đứa con 9 tuổi

  • Đứa con 9 tuổi của tôi chơi Mario Kart giỏi hơn tôi, nhưng tôi biết ơn vì kiến thức này có thể tạo ra khác biệt cho mình.

• Các tuyển thủ dùng build khác nhau theo từng bản đồ

  • Ví dụ, liệu họ có thích tốc độ tối đa ở các bản đồ có đoạn thẳng dài, còn ở các bản đồ có nhiều cua gắt thì lại ưu tiên gia tốc hay không?