AI HACKATHON – Chiến thuật đột phát để giành giải quán quân

Cuộc thi AI HACKTHON 2018 được tổ chức bởi công ty HYBRID TECHNOLOGIES vừa qua đã diễn ra vô cùng thành công, và thu hút gần 50 Colors đầy nhiệt huyết để tạo nên 10 đội chơi hùng mạnh nhất.

Đây là một hoạt động hoàn toàn mới lạ lần đầu tiên có mặt tại HYBRID TECHNOLOGIES – nhằm tạo nên một sân chơi chung cho toàn thể Colors có niềm đam mê với trí tuệ nhân tạo (AI – Artificial Intelligence), khuyến khích mọi người xây dựng tính đồng đội, cũng như học hỏi thêm những lối tư duy, kỹ năng mới từ các đội chơi khác.

Ở phần trước, chúng ta đã biết những thông tin cơ bản về cuộc thi AI HACKTHON này, tuy nhiên vẫn chưa hoàn toàn hiểu rõ được luật chơi cũng như các chiến thuật mà đội chiến thắng (The Pirates) đã sử dụng để trở thành quán quân của mùa giải năm nay.

Do đó, trong phần bài viết này, chúng ta sẽ tìm hiểu chi tiết về luật cuộc thi cũng như chiến thuật mà đội The Pirates đã sử dụng trong các trận đấu là gì nhé.

1. Giới thiệu về cuộc thi AI HACKATHON

Cuộc thi bao gồm sự tương tác giữa 1 máy chủ (gọi là Game Engine – GE) và các AI service cùng thi đấu với nhau.

Nhiệm vụ của GE sẽ call đến các AI service và hiển thị các thông tin, kết quả bằng video và audio. GE cũng sẽ quyết định kết quả thắng thua giữa 2 AI service.

Trong mỗi trận đấu sẽ có 2 AI service được chọn theo cách tính ngẫu nhiên của ban tổ chức.

1. 1 Tổng quan

Mỗi đội chơi phải xây dựng một application (AI service) phục vụ HTTP request với I/F được cung cấp sẵn để làm việc với GE.

• Trong trận đấu, AI của mỗi đội phải cố gắng đoán vị trí các tàu của AI đối phương đã sắp xếp trên bản đồ.
• Đội thắng là đội đầu tiên bắn chìm tất cả các tàu của AI đổi thủ bằng cách đoán chính xác vị trí và hình dạng của chúng.

1.2 Các loại tàu

• Carrier (5 ô, trong đó chỉ 4 ô thẳng hàng )
• BattleShip (4 ô thẳng hàng)
• OilRig (4 ô tạo thành hình vuông)
• Cruiser (3 ô thẳng hàng)
• Destroyer (2 ô bất kỳ)

*Lưu ý: có thể xếp ngang hoặc dọc tùy ý

 1.3 Luật xếp tàu

• Map có kích thước 8 x 20 ô, mỗi ô tương ứng với 1 điểm (x, y) thỏa mãn 0 <= x < 20, 0 <= y < 8
• Mỗi tàu phải được xếp theo chiều ngang hoặc dọc trong phạm vi của Map
• Các tàu không được xếp chồng lên nhau (vị trí đặt tàu bị trùng ở 1 điểm bất kỳ), hoặc ngoài phạm vi của Map, và vị trí tàu không được thay đổi sau khi Game bắt đầu
• GE sẽ tạo ra dữ liệu (đề bài) về các loại tàu (trong 5 loại đã nêu trên) và kèm theo số lượng của mỗi loại tàu cho mỗi Game khi bắt đầu trận đấu

1.4 Luật chơi cơ bản

• Game chơi theo lượt, mỗi lượt AI cần xác định 1 ô để bắn
• Khi bắt đầu trận đấu, GE sẽ call tới mỗi AI để gửi đề bài về Map, danh sách các loại tàu và số lượng
• Tiếp đến, GE sẽ call tới mỗi AI để lấy thông tin sắp xếp tàu. Nếu thông tin không hợp lệ thì AI đó sẽ bị xử THUA
• Với mỗi lượt bắn, GE sẽ call AI để nhận thông tin vị trí (x, y) mà AI đó sẽ bắn
• AI sẽ nhận được thông báo về kết quả của lượt bắn vừa thực hiện (trúng hay trật) và thông tin toàn bộ vị trí của tàu nếu tàu chìm
• AI sẽ bị xử thua trong các trường hợp sau:

1. Bị bắn chìm tất cả các tàu
2. Sắp xếp tàu không hợp lệ (bị chồng lên nhau / ngoài Map)
3. Vị trí bắn (x, y) không hợp lệ
4. Số lượng điểm bắn bằng Combo không hợp lệ (số điểm bắn nhiều hơn số Combo đang có)
5. Xuất hiện lỗi khi GE call yêu cầu đến
6. Xử lý request >=10s
7. Khai thác máy chủ trò chơi hoặc sử dụng dịch vụ trung gian để lấy dữ liệu nội bộ của đối phương

1.5 Luật combo

• Với mỗi tàu bị bắn chìm, AI sẽ nhận được thêm 1 điểm vào Combo (thêm 1 điểm bắn)
• AI có thể quyết định sử dụng Combo hay không cho lần bắn hiện tại. Để sử dụng Combo, AI sẽ gửi lên GE nhiều vị trí bắn (x, y) thay vì chỉ 1 vị trí như thông thường.

Ex: : AI đang có 3 điểm Combo -> AI có thể sử dụng bắn Combo với n vị trí, với 1<n<=(3+1)

• Nếu n=4, AI bắt buộc phải gửi 4 vị trí bắn lên cho GE
• Sau khi thực hiện bắn Combo, tất cả các điểm Combo sẽ bị reset về 0 ( Ex: : số điểm Combo là 3 và AI chỉ sử dụng 2 điểm thì sau khi thực hiện điểm Combo vẫn sẽ bị reset về 0)

2. Chiến thuật của đội chiến thắng – The Pirates

Để giành được chiến thắng trong cuộc thi AI HACKATHON không phải là một chuyện đơn giản. Vậy những chiến thuật nào đã giúp đội The Pirates giành được cúp vô địch.

Hãy cùng theo dõi những bí kíp “cực hay ho” do chính anh Mai Hồng Quân – Team Leader của đội The Pirates chia sẻ dưới đây.

2.1 Chiến thuật xếp tàu

“Về cách sắp xếp tàu, team mình đã hỗ trợ căn chỉnh theo kích thước Map (dynamic) và tàu sẽ được xếp theo pattern được định nghĩa sẵn. Đội mình sử dụng auto placing, nghĩa là tàu sẽ được xếp tự động hoàn toàn bằng hệ thống.

Chức năng này được team mình kết hợp với thiết lập mode xếp tàu dính (STICK mode) hay không dính. Lý do đội mình sử dụng mode này là vì có những đội sẽ sắp xếp tàu sao cho dính nhau nhiều nhất để tạo hoang mang cho đối phương.

Bên cạnh đó, đội mình còn sử dụng cách xếp tàu chủ động theo ID của đối thủ hoặc mặc định. Thông thường nếu trong những vòng đấu trước đội mình đã phân tích được chiến thuật bắn tàu của đối thủ, thì những trận sau đội mình sẽ chủ động setting 1 vài tàu đặc biệt ở những vị trí mà đội mình phán đoán là họ không thể tìm ra, còn những tàu còn lại sẽ sử dụng auto placing, tất cả đều tùy thuộc vào chiến thuật cho từng đối thủ khác nhau.

Ba chiến thuật chính đội mình dùng để xếp tàu.

Dưới đây, mình sẽ demo thử cách xếp tàu hỗ trợ căn chỉnh theo kích thước của map 10×10 , với 1 số tàu cố định sẽ ra cách sắp xếp như bên dưới đây.

Bạn có thể thấy hầu hết các tàu đều khá dính nhau, do kích thước map khá nhỏ.

Với size map 30×30 thì các tàu hoàn toàn ko dính nhau nữa

Kế đến mình sẽ nói đến phần pattern setting, chỉ cần mình input vào điểm bắt đầu thì toàn bộ tàu sẽ được vẽ ra theo pattern.

Ex: mình define tàu mới tên là Pirates, với hình dáng giống cây kiếm theo tọa độ mình đã vẽ bên dưới. Sau khi define và gửi có thông tin size map, cùng việc setting pattern, hệ thống đã tự động vẽ ra 1 chiếc tàu cho  mình.

Bước tiếp theo mình sẽ Demo thử chức năng tự động xếp tàu dính hoặc ko dính. Với:

• O: Dính (không tính trường hợp 2 tàu tiếp xúc theo đường chéo)
• 10: 10% tàu sẽ dính
• 1000:  Không bao giờ dính

Bạn có thể thấy, tàu hình trên dính rất nhiều, nhưng hình dưới thì ko dính.

Chiến thuật tiếp theo là phần khai báo chủ động xếp tàu.

Ex: mình muốn xếp 1 tàu nằm ngang ở vị trí tọa độ x14 y0, mình sẽ setting như sau:

Bên dưới là map của đối thủ (competitor), mình chỉ define map cần dùng, và set hướng theo tỉ lệ phần trăm. Nếu đội nào có thiên hướng bắn ngang, mình sẽ xếp tàu dọc , và chỉnh tỉ lệ % nhỏ xuống 20-30% lúc auto xếp tàu dọc và ngược loại.

Một phần mình muốn giới thiệu nữa với các bạn đó là phần Priority shot – phục vụ cho một đối thủ nhất định.

Ex: đối thủ hay xếp rìa, khi đó Priority shot sẽ define 1-2 điểm thăm dò xung quanh vùng họ hay đặt để xác minh họ có tiếp tục đặt đó hay ko.”

2.2 Chiến thuật bắn tàu

Có 2 dạng Shooting, là HUNT MODE – sử dụng khi chưa tìm thấy tàu nào, tiếp tục tìm để bắn, và TARGET MODE – sử dụng khi đã tìm thấy 1 điểm rồi.

Về phần HUNT MODE, vì luật trận đấu được quyền sử dụng Combo Shooting, nên mình sẽ ưu tiên sử dụng Combo trước. Lý do vì thuật toán mà mình sử dụng đó là càng bắn nhiều thì càng về sau càng có lợi, mình sẽ không save combo về sau.

Ở đây mình sử dụng Max saving shot là 2, nghĩa là khi số điểm được phép bắn trả về >= 2 thì sẽ bắn luôn, nếu nhỏ hơn thì mình sẽ giữ lại. Khi đó khoảng cách giữa 2 điểm bắn sẽ được xác định dựa vào chiều dài lớn nhất của tàu chưa bị chìm bên đối thủ.

Ex:thuyền 5 ô chưa bị chìm nghĩa là ta cần shooting cách bán kính từ 4 đến 5 ô, để khỏi bị dính nhau. Lý do vì nếu bắn 2 điểm quá gần thì có khả năng 2 phát bắn đó đều trúng cùng 1 thuyền. Nếu khoảng cách shooting xa hơn, thì cơ hội tìm kiếm được vị trí của nhiều thuyền trong 1 combo sẽ tốt hơn.Một cách thức khác mình chọn sử dụng là phương thức bàn cờ, vì min của thuyền là 2, nên khi bắn mình chỉ cần chọn bắn chẵn hoặc lẻ là có thể tìm đc thông tin tàu.

Cách khác nữa team mình dùng là probability map nghĩa là khả năng fix 1 con tàu vào 1 điểm trên bản đồ, càng vào giữa mật độ càng đậm, càng xa màu càng nhạt, nghĩa là rất khó bắn trúng. Bạn có thể nhìn vào 4 gốc, thuật toán trả về rất thấp.

2 cách còn lại mình cũng sử dụng để vào vòng bán kết đó là history map và priority – sử dụng lại lịch sử xếp tàu của đối thủ và ưu tiên bắn thăm dò xung quanh vùng họ hay đặt xem họ có tiếp tục đặt đó hay ko.Về dạng Shooting thứ 2 TARGET MODE – Target khi bắn trúng sẽ làm gì?

Đội mình sẽ dựa vào phần pattern setting tàu lúc đầu, và dùng cùng với thông tin điểm đã bắn trúng nhưng tàu chưa chìm, để xếp tàu thử.

Ex:  mình đã bắn trúng 2 điểm cách xa nhau, thuật toán sẽ thử tìm ra vị trí tàu có thể đặt tương ứng với 2 điểm đó.

Nếu có thể đặt vừa mình sẽ lấy ra các tập và so sánh, nếu tập nào chứa thuyền nhỏ nhất sẽ ưu tiên bắn trước. Trường hợp nếu 2 điểm quá xa và ko thuyền nào xếp vừa thì mình sẽ bỏ 1 điểm đi rồi thực hiện việc tìm điểm bắn tiếp theo với thông tin của điểm còn lại trước.

Trong trường hợp bắn trúng 3 điểm và 3 điểm này tạo thành 1 hình tam giác (nghĩa là sẽ không có loại tàu nào có thể xếp vào được), thì mình sẽ bỏ lần lượt từng điểm để hit, lúc đó sẽ tìm ra được tàu.Ngoài ra, mình còn sử dụng 1 phương thức gọi là “Logging”. Mỗi khi có trận đấu diễn ra sẽ lưu thông tin đối thủ, và thông tin đó sẽ được sử dụng cho sau này. Trong trường hợp mình gặp lại đối thủ đó thì mình sẽ biết được cách thức xếp tàu cũng như lối suy nghĩ của đối thủ trong toàn trận đấu.

Các bạn thấy đấy, chỉ với một Game bắn tàu đơn giản, nhưng để chiến thắng bằng cách ứng dụng AI thì không hề đơn giản chút nào. Bạn phải vận dụng thêm cả những kinh nghiệm trong mỗi trận đấu, để tìm ra những chiến thuật bắn tàu hợp lý và giành chiến thắng tuyệt đối.”

Theo: Mai Hồng Quân – Team Leader của The Pirates Công ty HYBRID TECHNOLOGIES.