Đến nội dung

Hình ảnh

Cách thắng trò chơi Nim

* * * * * 1 Bình chọn

  • Please log in to reply
Chủ đề này có 2 trả lời

#1
hoangtrong2305

hoangtrong2305

    Trảm phong minh chủ

  • Phó Quản lý Toán Ứng dụ
  • 861 Bài viết

Một số trò chơi thường thiên về may mắn, như khả năng chiến thắng của bạn dựa trên xúc xắc bạn lắc hay lá bài bạn được phát. Nhưng vẫn có những trò chơi cần chiến lược, nếu bạn chơi khéo léo, bảo đảm bạn sẽ giành chiến thắng.

 

Một ví dụ đó là trò chơi Nim, một trò chơi cổ xưa. Cho dù trò chơi đang ở giai đoạn nào, ta luôn có một chiến thuật thắng cho một trong hai người chơi, và một hình thức bổ sung rất thú vị sẽ cho bạn biết ai là người chiến thắng.

 

I. LUẬT CHƠI NIM

 

Trò chơi truyền thống Nim được chơi với một số đồng xu được sắp xếp thành nhiều đống, cách sắp số lượng đồng xu và đống tùy thuộc vào bạn. Có hai người chơi, khi đến lượt, người chơi có thể lấy một số lượng tùy ý đồng xu từ một đống duy nhất. Họ phải lấy ít nhất 1 đồng xu và họ không được lấy các đồng xu từ đống khác. Người thắng là người lấy đồng xu cuối cùng, nghĩa là không còn đồng xu nào sau nước đi của người đó. (Một số người chơi có cách chơi khác, người lấy đồng xu cuối cùng sẽ thua, nhưng hiện tại chúng ta sẽ bỏ qua phiên bản đó)

 

Rõ ràng ở đây không có sự may mắn. Bạn có thể tìm ra nước đi tốt nhất bằng việc dự đoán kết quả của nước đi trước đó một cách khéo léo.

 

Ví dụ về cách chơi trò này như sau: Giả sử có 3 đống, mỗi đống lần lượt có 3,4,5 đồng xu. Sau đây là quy trình chơi:

nim.png

Trò chơi Nim bắt đầu với 3 đống với mỗi đống lần lượt có 3,4,5 đồng xu. A là người chiến thắng

 

Câu hỏi mà chúng ta quan tâm là: Cho một trạng thái cụ thể các đống và đồng xu, liệu có một chiến lược thắng cho một trong các người chơi? Nghĩa là, liệu có một người chơi được đảm bảo sẽ thắng nếu người đó đi đúng bước?

 

Hãy bắt đầu với một vài ví dụ. Giả sử có 2 người chơi A và B, A là người đi trước. Giả sử có 2 đống, mỗi đống có 1 đồng xu. Rõ ràng, B là người chiến thắng vì A buộc phải lấy 1 trong 2 đồng xu, để lại cho B lấy đồng cuối cùng.

 

Bây giờ giả sử có 2 đống, một đống có 2 đồng xu, đống còn lại có 1 đồng xu. Người chơi A sẽ có chiến lược thắng: Lấy 1 đồng từ đống có 2 đồng xu. Khi đó ta còn lại 2 đống, mỗi đống 1 đồng xu và người chơi B đi tiếp. Như ví dụ trước, A là người thắng cuộc.

 

Chúng ta cùng làm thêm một ví dụ nữa: Giả sử có 2 đống với 2 đồng xu mỗi đống. Lúc này B sẽ là người có chiến thuật thắng. Nếu A lấy hết một đống, B chỉ cần lấy đống còn lại và thắng. Nếu A chỉ lấy 1 đồng của một đống thì chúng ta trở về lại trường hợp trên với B đi trước. Do đó B luôn đảm bảo sẽ thắng nếu B lấy 1 đồng từ đống có 2 đồng xu.

 

nim_coins.jpg

Ai có chiến lược thắng?

 

Từ chuỗi ví dụ trên, bạn có thể cảm giác rằng có một mô hình nào đó cho trò chơi này: Cho một cách sắp xếp các đống và các đồng xu, sẽ có một chiến lược thắng cho một trong hai người chơi. Nhà toán học Charles Bouton (1869-1922) cũng cảm thấy điều tương tự và đặt mình vào nhiệm vụ khó khăn là phân tích toàn bộ trỏ chơi trên. Năm 1902 ông đã tìm ra bí quyết - và bí quyết này thật tinh tế! Để tìm ra có một chiến thuật thắng cho người chơi, đầu tiên bạn cần phải ...

 

II. SỬ DỤNG DÃY NHỊ PHÂN

 

Bí mật ở đây chính là viết số lượng đồng xu trong các đống thành số nhị phân. Để biết làm như thế nào, cần nhớ lại cách viết số thập phân thông thường như thế nào. Lấy 4302 làm ví dụ, 4 ở đây không đơn thuần chỉ là số 4, mà lã 4000 hay $4\times 1000$. Tương tự, 3 không đơn thuần chỉ là số 3 mà là $300=3\times 100$, 0 đại diện cho $0\times 10$, và 2 đại diện cho $2\times 1$. Như vậy 4302 nghĩa là:

                                              $$4\times 1000+3\times 100+0\times 10+2\times 1$$

Tương tự số 7396 được biểu diễn là

                                              $$7\times 1000+3\times 100+9\times 10+6\times 1$$

Các số 1000, 100, 10 và 1, xuất hiện ở các biểu thức trên có điểm chung là gì? Chúng đều là lũy thừa của 10

                                                                                $$1000={{10}^{3}}$$

                                                                                 $$100={{10}^{2}}$$

                                                                                  $$10={{10}^{1}}$$

                                                                                   $$1={{10}^{0}}$$

Để viết các số theo hệ thập phân, đầu tiên bạn cần phải viết chúng dưới dạng tổng liên tiếp các lũy thừa của 10 (với lũy thừa lớn nhất ở bên trái), và sau đó viết các hệ số của các lũy thừa đó. Chúng ta có thể làm tương tự với lũy thừa của 2 thay vì 10. Ví dụ, giá trị của dãy nhị phân 110 viết dưới hệ thập phân là:

                                $$1\times {{2}^{2}}+1\times {{2}^{1}}+0\times {{2}^{0}}=4+2+0=6$$

Và dãy nhị phân 10001 biểu diễn trong hệ thập phân là

$$1\times {{2}^{4}}+0\times {{2}^{3}}+0\times {{2}^{2}}+0\times {{2}^{1}}+1\times {{2}^{0}}=16+0+0+0+1=17$$

Bạn có thể hiểu rằng dãy nhị phân chỉ chứa duy nhất hai giá trị là 0 hoặc 1, khi bạn viết một số dưới dạng tổng liên tiếp các lũy thừa của 2, các hệ số khác là không cần thiết.

 

III. CỘNG THEO CÁCH CHƠI NIM

 

Bí mật để tìm ra chiến lược thắng nằm ở cách viết số kích thước của các đống (số lượng đồng xu của từng đống) theo dạng nhị phân và cộng chúng lại với nhau, nhưng không phải cộng theo cách thông thường, mà là cộng theo một cách khác, gọi là "Phép cộng Nim".

 

Để cộng một số số nhị phân cho trước bằng "phép cộng Nim", đầu tiên bạn viết chúng theo dạng cột (viết số sau đứng dưới số trước), như cách thực hiện phép cộng thông thường. Sau đó bạn nhìn từng cột theo thứ tự. Nếu số lượng các con số 1 là lẻ, bạn viết 1 ở dưới chúng, nếu số lượng chẵn, viết số 0 dưới chúng. Làm như vậy với từng cột cho ra số nhị phân mới, và đó là kết quả của "phép cộng Nim".

nimrod.png

Một trong những trò chơi máy tính đầu tiên có tên là Nimrod, được thế kế để chơi trò chơi Nim.

Trò chơi này được triển lãm vào năm 1951 tại Festival Anh quốc

 

Ví dụ, hãy cộng (theo cách Nim) các số nhị phân 10, 11, và 100 (các số này biểu diễn dưới thập phân là 2, 3 và 4):

Capture.PNG

 

Vậy kết quả của "phép cộng Nim" là số số nhị phân 101. "Phép cộng Nim" không giống với phép cộng thông thường, số nhị phân 101 là 5 ở hệ thập phân, không bằng với phép cộng thông thường là $2+3+4=9$

 

IV. AI THẮNG CUỘC?

 

Khi Charles Bouton phân tích trò chơi Nim, ông phát hiện ra 2 điều nắm giữ chìa khóa dẫn đến chiến lược thắng.

 

Điều 1: Giả sử đến lượt bạn và tổng Nim các đồng xu trong các đống bằng 0. Cho dù bạn làm gì đi nữa, tổng Nim các đồng xu sau khi bạn thực hiện nước đi đều khác 0.

 

Điều 2: Giả sử đến lượt bạn và tổng Nim các đồng xu trong các đống khác 0. Lúc đó, luôn có một nước đi đảm bảo rằng sau khi bạn thực hiện nước đi, tổng Nim các đồng xu trong các đống bằng 0.

 

Không khó để chứng minh các điều trên luôn đúng, nhưng bạn có thể tự trải nghiệm bằng cách chơi với các đống xu.

 

Bây giờ giả sử bạn là người chơi A, bạn đi trước, cũng giả sử rằng tổng Nim số lượng các đồng xu trong các đống khác 0. Chiến lược của bạn như sau: Đi nước đi sao cho có thể làm giảm tổng Nim tiếp theo (tổng Nim sau khi bạn đi) về 0. Điều này nghĩa là cho dù B đi thế nào ở nước kế tiếp thì theo "điều 1" nước đi đó sẽ biến tổng Nim tiếp theo thành một số khác 0.

 

Chúng ta hãy xem tổng Nim trong bảng sau:

 

$$\begin{array}{|c|c|c|c|} \hline \textbf{Người chơi đi nước tiếp theo} & \textbf{Tổng Nim} & \textbf{Tổng Nim có thể giảm về 0?} &\textbf{Tổng Nim tiếp theo}\\ \hline A     & \text{Khác } 0 & \text{Có} & 0 \\  \hline B     & 0 & \text{Không} & \text{Khác } 0 \\  \hline A     & \text{Khác } 0 & \text{Có} & 0 \\  \hline B     & 0 & \text{Không} & \text{Khác } 0 \\ \hline A     & \text{Khác } 0 & \text{Có} & 0 \\  \hline ...     & ... & ... & ... \\     \hline \end{array}$$

 

Các giá trị 0 và khác 0 của tổng Nim theo bảng trên sẽ đảm bảo bạn là người chiến thắng! Nếu B thắng, B sẽ thực hiện nước đi không chừa lại đồng xu nào, nghĩa là B sẽ tạo ra nước đi mà kết quả tổng Nim bằng 0 mà như chúng ta đã thấy là không thể. Ngược lại, nước đi của bạn luôn làm tổng Nim giảm về 0 và tại một số thời điểm của trò chơi thì tổng Nim bằng 0 sẽ tương ứng với không còn đồng xu còn lại, khi đó bạn thắng.

Điều này chỉ ra rằng nếu tổng Nim các đồng xu trong các đống ở thời điểm bắt đầu khác 0, thì A có chiến lược thắng. Chiến lược này luôn tạo ra nước đi làm giảm tổng Nim tiếp theo về 0. (Bạn có thể kiểm tra điều này bằng cách xem đây là chiến lược được A chơi trong ví dụ ở đầu bài viết.)

 

Nếu tổng Nim các đồng xu trong các đống ở thời điểm bắt đầu của trò chơi bằng 0, thì B là người có chiến thuật thắng. Cho dù A có đi nước đầu như thế nào thì kết quả tổng Nim vẫn khác 0 khi đến lượt B và như đã đề cập ở trên, điều này có nghĩa B có chiến lược thắng.

 

V. PHÉP CỘNG NIM THỐNG TRỊ THẾ GIỚI

 

Phép cộng Nim rõ ràng rất có lợi khi chơi trò chơi Nim, nhưng phép cộng Nim chỉ có tác dụng trong trò chơi này, đúng chứ? Sai rồi! Thật ra trong mỗi ngày ta đều sử dụng cách cộng số kỳ lạ này.

 

Máy tính là thiết bị nhị phân. Tất cả thông tin lưu trữ (bao gồm các con số) được chuyển hóa thành các dãy 0 và 1. Nhưng máy tính không chỉ lưu trữ dữ liệu, chúng còn thực hiện được các lệnh logic, dựa trên câu trả lời có/không. Ví dụ, cho một tên tài khoản và mật khẩu, máy tính tự hỏi:"Đây có là tài khoản chính xác?" và "Đây có là mật khẩu chính xác?" và dựa trên câu trả lời để quyết định có để người dùng truy cập vào hay không. Lưu ý rằng các lệnh này dùng 2 lệnh nhập (tài khoản đúng? Mật khẩu đúng?) và xuất ra một lệnh (truy cập hoặc không truy cập),

Viết 0 cho giá trị "không" và 1 cho giá trị "có", những lệnh logic này cũng có thể chuyển hóa thành dãy nhị phân chứa các số 0 và 1. May mắn thay, hóa ra tất cả các lệnh logic bạn muốn thực hiện được tạo ra từ 6 loại cơ bản. Bạn đơn giản chỉ cần thiết lập đúng cách.

binary.jpg

Máy tính là thiết bị nhị phân

 

Một trong những lệnh cơ bản là XOR. Lệnh này cần 2 đầu vào (input), mỗi đầu vào có giá trị 0 hoặc 1, và chuyển thành một đầu ra (output), cũng có giá trị là 0 hoặc 1. Đây là bảng chân trị XOR

Capture.PNG

Nhìn kĩ hơn thì ta thấy rằng XOR giống hoàn toàn với tổng Nim của các số 0 và 1:

Capture.PNG

Do đó, rất nhiều lệnh mà máy tính của bạn thực hiện hằng ngày đều dựa trên tổng Nim. Không có máy tính, mọi thứ sẽ rất khác. 

 

Bài viết do thành viên Chuyên san EXP dịch.

 

Nguồn: https://plus.maths.o...t/play-win-nim 


Toán học là ông vua của mọi ngành khoa học.

Albert Einstein

(1879-1955)

Hình đã gửi


-------------------------------------------------------------------------------------------------------------------


Click xem Đạo hàm, Tích phân ứng dụng được gì?

và khám phá những ứng dụng trong cuộc sống


#2
toanhochay

toanhochay

    Binh nhất

  • Thành viên
  • 49 Bài viết

Đây đã có game để thử nghiệm thuật toán Nim:  sử dụng hệ điều hành điện thoại android để tải trên shop play:  Tên search:  Eat apple ( Có vài tên trùng nhau nên chọn ứng dụng cho đúng)  hoặc tải từ link trên shop :  https://play.google....me.casidanglong

và đây là video hướng dẩn: 



#3
Nguyen Duy Q

Nguyen Duy Q

    Binh nhì

  • Thành viên mới
  • 10 Bài viết

Đây đã có game để thử nghiệm thuật toán Nim:  sử dụng hệ điều hành điện thoại android để tải trên shop play:  Tên search:  Eat apple ( Có vài tên trùng nhau nên chọn ứng dụng cho đúng)  hoặc tải từ link trên shop :  https://play.google....me.casidanglong

và đây là video hướng dẩn: 

nhung ma cai nay ko quan tam den so luong lay. them luat nguoi choi chi dc an max 3 qua tao thoi thi game se hap dan hon nhieu!






0 người đang xem chủ đề

0 thành viên, 0 khách, 0 thành viên ẩn danh