Sáng tạo trong thuật toán và lập trình với ngôn ngữ Pascal và C# Tập 2 - Chương 3

Trò chơiCác bài toán trò chơi khá đa dạng và thường là khó. Chúng ta xét loại trò chơi thứ nhất với các gỉa thiết sau đây: 1. Trò chơi gồm hai đấu thủ là A và B, luân phiên nhau, mỗi người đi một nước. Ta luôn giả thiết đấu thủ đi trước là A. 2. Hai đấu thủ đều chơi rất giỏi, nghĩa là có khả năng tính trước mọi nước đi. 3. Đấu thủ nào đến lượt mình không thể đi được nữa thì chịu thua và ván chơi kết thúc. 4. Không có thế hòa,...
Nội dung trích xuất từ tài liệu:
Sáng tạo trong thuật toán và lập trình với ngôn ngữ Pascal và C# Tập 2 - Chương 3 C hươ ng 3 T rò chơ i Các bài toán trò chơi khá đa dạng và thường là khó. Chúng ta xét loại trò chơi thứ nhất với các gỉa thiết sau đây: 1. Trò chơi gồm hai đấu thủ là A và B, luân phiên nhau, mỗi người đi một nước. Ta luôn giả thiếtđấu thủ đi trước là A. 2. Hai đấu thủ đều chơi rất giỏi, nghĩa là có khả năng tính trước mọi nước đi. 3. Đấu thủ nào đến lượt mình không thể đi được nữa thì chịu thua và ván chơi kết thúc. 4. Không có thế hòa, sau hữu hạn nước đi sẽ xác định được ai thắng, ai thua. Giả thiết chơi giỏi nhằm tránh các trường hợp “ăn may”, tức là các trường hợp do đối phương hớhênh mà đi lạc nước. Điều này tương đương với giả thiết cả hai đấu thủ đều có thể tính trước mọi nước đi(với loại trò chơi hữu hạn) hoặc cả hai đấu thủ đều biết cách đi tốt nhất. Để tiện trình bày chúng ta gọi cáctrò chơi loại này là chơi cờ, mỗi thế của bàn cờ là một tình huống với dữ liệu cụ thể, ta thường gọi là mộtcấu hình. Các bài toán tin liên quan đến loại trò chơi này thường là:  Lập trình để xác định với một thế cờ cho trước thì người đi trước (đấu thủ A) sẽ thắng hay thua.  Lập trình để máy tính chơi với người. Dĩ nhiên chương trình bạn lập ra là dành cho máy tính.  Lập trình để hai máy tính chơi với nhau. Với loại trò chơi này có một heuristic mang tính chỉ đạo sau đây: Trước hết cần xác định được một tính chất T thỏa các điều kiện sau đây: a) Thế thua cuối cùng thỏa T, b) Mọi nước đi luôn luôn biến T thành V = not T, c) Tồn tại một nước đi để biến V thành T. Tính chất T được gọi là bất biến thua của trò chơi. Việc chuyển thế X thành not X thường được gọi là lật thế X. Các qui tắc a - c có thể phát biểu lạinhư sau: 89T được gọi là bất biến thua nếu Đấu thủ nào có cách đẩy đấu thủ khác vào thế thua T thì đấu thủ đó sẽ thắng. a) Thế thua cuối cùng thỏa T, Đấu thủ nào không thể đẩy đấu thủ khác vào thế b) Mọi nước đi từ T đều lật T thành V, thua T thì đấu thủ đó sẽ thua. c) Tồn tại một nước đi để lật V thành T. Nước đi ở đây được hiểu là nước đi hợp lệ tức là nước đi tuân thủ các qui định của trò chơi, thí dụxe liền, pháo cách trong cờ tướng qui định rằng quân xe có thể ăn trực tiếp các quân của đối phươngnằm trên đường đi của nó, còn quân pháo thì phải ăn qua một quân đệm. Điểm khó nhất của loại toán này là xác định bất biến thua.Bài 3.1. Bốc sỏi A Trên bàn có một đống sỏi N viên, hai đấu thủ A và B lần lượt đi, A đi nước đầu tiên. Mỗi nước điđấu thủ buộc phải bốc từ 1 đến M viên sỏi khỏi bàn. Đấu thủ nào đến lượt mình không đi nổi thì thua. Cảhai đấu thủ đều chơi rất giỏi. Với hai số N và M cho trước hãy cho biết A thắng (ghi 1) hay thua (ghi 0). Ta thử chơi với M = 3 và vài dữ liệu ban đầu N = 1, 2 ,… Để tính nước đi cho đấu thủ A bạn hãy kẻmột bảng gồm 2 dòng. Dòng thứ nhất là các giá trị của N. Dòng thứ hai được ghi 0 ứng với tình huống Athua và 1 cho tình cho trường hợp A thắng, nếu A là đấu thủ đi nước đầu tiên. M=3 N= 0 1 2 3 4 5 6 7 8 9 10 11 12 13 … 01110111011 1 0 1 … A thắng (1) hay thua (0)? #123#123#12 3 # 1 … Cách đi: số viên cần bốc để chắc thắng Một vài tình huống cho bài Bốc sỏi A, M = 3; # - đầu hàng/bốc tạm 1 viên Thí dụ, với M = 3 cho trước và cố định, A là đấu thủ đi trước, ta có N = 0 là một thế thua, vì A không có cách đi. N = 1 là một thế thắng, vì A sẽ bốc 1 viên, B hết cách đi. N = 2 là một thế thắng, vì A sẽ bốc 2 viên, B hết cách đi. N = 3 là một thế thắng vì A sẽ bốc 3 viên, B hết cách đi. N = 4 là một thế thua, vì dù A bốc 1, 2, hoặc 3 viên đều dẫn đến các thế thắng là 3, 2, 1… Làm thế nào để xác định được bất biến của trò chơi? Phương pháp đơn giản là tư duy Nhân - Quảhay là lập luận lùi. Cụ thể là, nếu biết kết quả là Q ta hãy gắng tìm nguyên nhân N sinh ra Q. Ta để ý rằng, Qui tắc xác định thế thắng / thua Từ một thế X đang xét,  nếu tìm được một nước đi dẫn đến thế thua T thì X sẽ là thế thắng V, và  ...