Tại sao Thất bại nhanh hơn rất nhiều so với Chương trình Cờ vua Đơn giản (TSCP)? (Tối ưu hóa động cơ cờ vua)

Question

Tôi hy vọng đây không phải là quá nhiều câu hỏi tùy ý, nhưng tôi đã xem xét các mã nguồn của Faile và TSCP và tôi đã chơi chúng với nhau. Theo như tôi có thể thấy các công cụ có rất nhiều điểm chung, nhưng thất bại tìm kiếm ~ 1,3 triệu nút mỗi giây trong khi TSCP chỉ tìm kiếm 300k nút mỗi giây.

Mã nguồn cho lỗi có thể tìm thấy tại đây: http://faile.sourceforge.net/download.php. Mã nguồn TSCP có thể tìm thấy ở đây: http://www.tckerrigan.com/Chess/TSCP. Sau khi xem xét chúng, tôi thấy một số điểm tương đồng: cả hai đều sử dụng biểu diễn bảng mảng (mặc dù Faile sử dụng bảng kích thước 144), cả hai đều sử dụng tìm kiếm alpha beta với một số loại bảng chuyển vị, cả hai đều có hàm đánh giá rất giống nhau. Sự khác biệt chính tôi có thể tìm thấy là Faile sử dụng một đại diện dư thừa của hội đồng quản trị bằng cách cũng có mảng của các vị trí mảnh. Điều này có nghĩa là khi các chuyển động được tạo ra (bởi các hàm rất giống nhau cho cả hai chương trình), Faile phải lặp lại ít phần xấu hơn, trong khi duy trì mảng này tốn ít tài nguyên hơn đáng kể.

Câu hỏi của tôi là: tại sao có sự khác biệt 4x về tốc độ của hai chương trình này? Ngoài ra, tại sao Faile luôn đánh bại TSCP (tôi ước tính khoảng 200 điểm ELO chỉ bằng cách theo dõi chuyển động của họ)? Đối với sau này, nó có vẻ là bởi vì Faile đang tìm kiếm một số sâu hơn.

Answer 1

TSCP không có bảng băm (-75 ELO). TSCP không cho phép Killers đặt hàng (-50 ELO). TSCP không di chuyển (-100 ELO). TSCP có thiết kế chức năng tấn công xấu (-25 ELO).

Trong 4 điều này, bạn có khoảng chênh lệch 250 điểm ELO. Điều này sẽ tăng số lượng các nút trên giây nhưng bạn không thể so sánh các nút trên giây trên các công cụ khác nhau vì các lập trình viên có thể sử dụng một cách giải thích khác nhau về nút là gì.

Answer 2

Câu trả lời ngắn: TSCP rất đơn giản (như bạn có thể đoán từ tên của nó). Thất bại là nâng cao hơn, một số thời gian đã được chi tiêu bởi các nhà phát triển để tối ưu hóa nó. Vì vậy, nó chỉ là hợp lý cho thất bại để được nhanh hơn, có nghĩa là tìm kiếm sâu hơn và ELO cao hơn.

Câu trả lời dài: Theo tôi nhớ, phần quan trọng nhất của chương trình, sử dụng tìm kiếm alpha beta (phần ảnh hưởng đến hiệu suất nhiều nhất), là trình tạo chuyển động. TSCP của máy phát điện di chuyển không tạo ra di chuyển trong bất kỳ thứ tự cụ thể. Trình tạo lỗi (như bạn thấy), sử dụng danh sách mảnh, được sắp xếp theo thứ tự giá trị mảnh giảm. Điều này có nghĩa là nó tạo ra những động thái quan trọng hơn trước. Điều này cho phép cắt xén alpha-beta để cắt giảm các động thái không cần thiết và làm cho cây tìm kiếm ít bị phân nhánh hơn. Và cây ít nhánh có thể sâu hơn và vẫn có cùng số lượng nút, cho phép tìm kiếm sâu hơn.

Dưới đây là một ví dụ rất đơn giản về cách thứ tự di chuyển cho phép tìm kiếm nhanh hơn. Giả sử, di chuyển cuối cùng của màu trắng là ngớ ngẩn - họ di chuyển một số mảnh đến vị trí không được bảo vệ. Nếu chúng ta tìm thấy một số di chuyển của màu đen mà loại bỏ phần này, chúng ta có thể bỏ qua tất cả các di chuyển khác, chưa được ước tính và trở lại để xử lý danh sách di chuyển của màu trắng. Nữ hoàng kiểm soát nhiều không gian hơn là một con tốt, vì vậy nó có nhiều cơ hội để loại bỏ mảnh này, vì vậy nếu chúng ta nhìn vào di chuyển của nữ hoàng đầu tiên, chúng ta có nhiều khả năng bỏ qua những động thái không cần thiết.

Tôi không so sánh các phần khác của các chương trình này. Nhưng rất có thể, Faile cũng tối ưu hóa chúng tốt hơn. Những thứ như thuật toán alpha-beta, độ sâu biến đổi của cây tìm kiếm, phân tích vị trí tĩnh cũng có thể được tối ưu hóa.