GIỚI THIỆU
Tính cấp thiết của đề tài
Cùng với sự phát triển công nghiệp hóa và xu hướng công nghệ, ngành kỹ thuật công nghệ trong nước cần phải phát triển mạnh mẽ Game Tic Tac Toe là một trò chơi trí tuệ không yêu cầu tốc độ, vì vậy người chơi nên cân nhắc kỹ lưỡng mỗi bước đi để chọn vị trí hợp lý, không chỉ cho lượt chơi hiện tại mà còn cho các bước đi tiếp theo Dù bước đi hiện tại có thể không mang lại kết quả ngay lập tức, nhưng nó sẽ tạo nền tảng cho những thắng lợi sau này Trạm Tic Tac Toe sẽ giúp người chơi giải trí và thư giãn, mang lại cảm giác thoải mái trong cuộc sống hàng ngày.
Ý nghĩa khoa học và thực tiễn của đề tài
Trạm Tic Tac Toe được thiết kế nhằm đáp ứng mục tiêu phát triển công nghệ hiện đại của đất nước và nhu cầu thiết yếu trong cuộc sống hàng ngày của con người, đồng thời hỗ trợ cho dự án Smarthome.
Mục tiêu nghiên cứu của đề tài
Nghiên cứu thiết kế trạm Tic Tac Toe với hiệu suất cao, làm việc ổn định, chất lượng tốt, sản phẩm có hình dáng cơ bản
Cùng với sự nghiệp công nghiệp hóa, hiện đại hóa của đất nước.
Đối tượng và phạm vi nghiên cứu
Tập trung chủ yếu vào việc tương tác giữa máy và người
Phát triển sản phẩm phục vụ cho cuộc sống hàng ngày là một nhiệm vụ quan trọng Tuy nhiên, do thời gian thực hiện đồ án có hạn, nên kết quả cuối cùng chỉ đạt được ở mức độ mô hình.
Phương pháp nghiên cứu
1.5.1 Cơ sở phương pháp luận
Phương pháp nghiên cứu chia làm các phần chính:
+ Phân tích, tính toán lý thuyết: chọn động cơ, thuật toán Tic Tac Toe
+ Thiết kế mô hình thực tiễn, thực nghiệm, đánh giá, cải tiến
1.5.2 Các phương pháp nghiên cứu cụ thể Để thực hiện đề tài này, em đã sử dụng nhiều phương pháp nghiên cứu như: Tham khảo tài liệu trên thư viện, internet, hội thảo trí tuệ nhân tạo…Đặc biệt là phương pháp tham khảo tài liệu trên internet (Hình ảnh, sách báo, video) giúp em hình thành ý tưởng mới Đồng thời em còn sử dụng phương pháp quan sát thực nghiệm vô cùng hiệu quả: Tạo ra sản phẩm, từ đó đánh giá chất lượng rút kinh nghiệm
Bên cạnh đó em còn nhận được hỗ trợ vô cùng quý báu từ tài liệu giảng viên hướng dẫn
TỔNG QUAN NGHIÊN CỨU ĐỀ TÀI
Lịch sử ra đời game Tic-Tac-Toe
Các trò chơi trên các bảng ba liên tiếp có nguồn gốc từ Ai Cập cổ đại, nơi các bảng trò chơi đã được phát hiện trên các tấm lợp có niên đại khoảng 1300 trước Công nguyên.
Biến thể ban đầu của trò chơi Tic-Tac-Toe, được gọi là terni lapilli, đã được chơi ở Đế chế La Mã vào khoảng thế kỷ thứ nhất trước Công nguyên Trong trò chơi này, mỗi người chơi chỉ có ba viên sỏi và phải di chuyển chúng đến các khoảng trống để tiếp tục Các dấu hiệu lưới của trò chơi đã được phát hiện trên khắp Rome Ngoài ra, còn có trò chơi cổ xưa khác là ba morris, cũng yêu cầu ba mảnh liên tiếp để hoàn thành, và Picaria, một trò chơi của người Malta, có liên quan chặt chẽ.
Trò chơi Tic-Tac-Toe, còn được gọi là "noughts and crosses," có nguồn gốc từ những tài liệu tham khảo đầu tiên vào năm 1858 và 1884 Tên gọi "tick-tack-toe" xuất hiện trong một mô tả về trò chơi trẻ em, trong khi "Tic-Tac-Toe" có thể liên quan đến phiên bản cổ của backgammon Đến thế kỷ 20, tên gọi "noughts and crosses" đã được đổi thành "Tic-Tac-Toe" tại Hoa Kỳ Năm 1952, OXO, do nhà khoa học máy tính Sandy Douglas phát triển cho máy tính EDSAC tại Đại học Cambridge, trở thành một trong những trò chơi video đầu tiên, cho phép người chơi đối đầu hoàn hảo với máy tính trong trò chơi này.
Vào năm 1975, sinh viên MIT đã sử dụng trò chơi Tic-Tac-Toe để chứng minh khả năng tính toán của các yếu tố Tinkertoy Máy tính Tinkertoy, được xây dựng chủ yếu từ Tinkertoys, có khả năng chơi Tic-Tac-Toe một cách hoàn hảo Hiện nay, nó đang được trưng bày tại Bảo tàng Khoa học ở Boston.
Giới thiệu Tic-Tac-Toe
Tic-Tac-Toe là trò chơi kết hợp không thể chia nhỏ, kết thúc khi đạt được cấu hình chiến thắng hoặc hòa Trò chơi kết thúc khi một người chơi có ba vị trí liên tiếp hoặc khi bảng đầy mà không có người thắng Tic-Tac-Toe thuộc loại trò chơi vị trí, cùng với cờ đam và cờ vua, được phân tích trong cuốn sách "Trò chơi kết hợp: Lý thuyết Tic-Tac-Toe" của Beck Một trò chơi vị trí bao gồm tập hợp hữu hạn E của các điểm trên bảng và bộ W của các tập con E gọi là bộ chiến thắng Hai người chơi, Xgi và Ogi, lần lượt chiếm các điểm trên bảng, với Xgi luôn chơi trước Trạng thái trò chơi được xác định bởi các vị trí đã chiếm Người chơi đầu tiên chiếm được bộ chiến thắng sẽ thắng, trong khi nếu bảng đầy mà không có người thắng, trò chơi kết thúc với tỷ số hòa, được gọi là trạng thái rút ra Bảng (E, W) được coi là thừa nhận trạng thái rút ra nếu có thể phân vùng E thành X và O sao cho mọi bộ thắng A ∈ W có ít nhất một điểm trong đó.
Trong lý thuyết trò chơi, nếu một hội đồng thừa nhận trạng thái rút thăm, điều đó không có nghĩa là trò chơi sẽ luôn kết thúc với tỷ số hòa, mà chỉ cho phép khả năng bốc thăm Ngược lại, nếu không thừa nhận trạng thái rút ra, trò chơi phải có người thắng Chiến lược trong trò chơi kết hợp là thuật toán giúp người chơi quyết định bước đi tiếp theo dựa trên trạng thái hiện tại Một chiến lược tối ưu sẽ tạo ra động thái đảm bảo kết quả tốt nhất cho người chơi trong mọi trạng thái của trò chơi.
Chiến lược giành chiến thắng cho Xgi là cách mà anh ta có thể đạt được chiến thắng trong mọi chuỗi di chuyển của Ogi, mà không cần xác định trước mọi nước đi trong trò chơi Thay vào đó, chiến lược này dựa vào các bước di chuyển dẫn đến trạng thái hiện tại của trò chơi Khi nghiên cứu một trò chơi, câu hỏi quan trọng là xác định ai có lợi thế, từ đó xác định lớp kết quả của trò chơi Một người chơi được coi là chơi tối ưu nếu họ thực hiện chiến lược tối ưu mà không mắc lỗi Sự tồn tại của chiến lược tối ưu của một người chơi có thể ngăn cản sự tồn tại của chiến lược khác Nếu Xgi có chiến lược chiến thắng và chơi tối ưu, anh ta sẽ chắc chắn chiến thắng, trong khi Ogi không thể có chiến lược hòa hoặc chiến thắng Ngược lại, nếu không có người chơi nào có chiến lược chiến thắng, cả hai phải có chiến lược hòa Điều này cho thấy rằng người chơi đầu tiên không nhất thiết phải thắng nếu họ mắc lỗi Trong một trò chơi được chơi tối ưu, có ba kết quả có thể xảy ra: người chơi đầu tiên có chiến lược chiến thắng, người chơi thứ hai có chiến lược chiến thắng, hoặc cả hai có chiến lược hòa Tuy nhiên, người chơi thứ hai không thể có chiến lược chiến thắng khi đối đầu với một người chơi đầu tiên hoàn hảo, điều này được khẳng định trong định lý cho rằng trong một trò chơi định vị, Xgi luôn có thể ép ít nhất một trận hòa.
Trong trò chơi chiến lược giữa Ogi và Xgi, Xgi có thể giành chiến thắng bằng cách áp dụng chiến lược S của Ogi Khi Xgi thực hiện một động thái tùy ý, anh ta giả vờ là người chơi thứ hai và tiếp tục theo chiến lược S Nếu Xgi có một động thái khả dụng, anh ta nên thực hiện, và bất kỳ động thái nào của anh ta đều có thể dẫn đến một vị trí có lợi cho mình Điều này cho thấy rằng chiến lược S không phải là một chiến lược chiến thắng cho Ogi, vì cả hai người chơi không thể thắng Trong trường hợp không còn vị trí mở trên bảng, trò chơi sẽ kết thúc với tỷ số hòa, và Ogi không thể có chiến lược chiến thắng Cuối cùng, Xgi có thể buộc một trận hòa, trong khi Ogi chỉ có thể ngăn chặn Xgi có chiến lược chiến thắng Kết quả của trò chơi được xác định dựa trên việc Xgi có chiến lược chiến thắng hay không; nếu có, Xgi được coi là người chiến thắng, ngược lại, cả hai sẽ có chiến lược hòa.
Biến thể trên Tic-Tac-Toe
Trong khi cờ đam và cờ vua là những trò chơi định vị tiêu biểu, hầu hết nghiên cứu trong lĩnh vực này tập trung vào các biến thể của Tic-Tac-Toe do tính phức tạp cao của các trò chơi khác Tic-Tac-Toe được xem là một trò chơi tĩnh, mang lại những đặc điểm thú vị cho việc phân tích và nghiên cứu.
Cờ đam và cờ vua là những trò chơi năng động với khả năng di chuyển hoặc gỡ bỏ quân cờ Tic-Tac-Toe, với sự đơn giản của nó, là một ứng cử viên lý tưởng cho các nghiên cứu toán học Trong phần này, chúng ta sẽ khám phá một số biến thể của Tic-Tac-Toe trước khi đi sâu vào các biến thể cụ thể hơn Trong tất cả các biến thể, hai người chơi lần lượt đặt quân cờ ở các vị trí mở, nhằm mục tiêu chiếm được bộ chiến thắng đầu tiên, được gọi là chiến thắng mạnh mẽ Tuy nhiên, việc xác định cách tạo ra một chiến thắng mạnh mẽ là khá phức tạp, như trong trường hợp của Tic-Tac-Toe 4 × 4 × 4, nơi người chơi đầu tiên có chiến lược thắng nhưng cần sự hỗ trợ của máy tính để chứng minh Biến thể Maker-Breaker là một trong những trò chơi phổ biến, trong đó người chơi đầu tiên cố gắng hoàn thành bộ thắng, trong khi người thứ hai ngăn chặn Trong Maker-Breaker, nhiệm vụ của hai người chơi là riêng biệt, giúp cho việc phân tích dễ dàng hơn Tuy nhiên, trong một số trò chơi như Hex, chiến lược vẫn là giành chiến thắng, ngay cả khi áp dụng quy tắc Maker-Breaker Việc áp dụng quy tắc Maker-Breaker trong Tic-Tac-Toe có thể cho phép người chơi thứ nhất giành chiến thắng mà không cần chặn đối thủ.
17 | P a g e chiến thắng trò chơi Maker-Breaker nhưng không phải trò chơi gốc là một lý do khiến Maker-Breaker thắng còn được gọi là chiến thắng yếu
Trò chơi Shannon Switching là một ví dụ điển hình về trò chơi Maker-Breaker, diễn ra trên các cạnh của đồ thị với mục tiêu chính của Maker là tạo ra một đường dẫn kết nối hai đỉnh khác nhau Trong khi đó, Breaker có khả năng ngăn chặn chiến thắng bằng cách hoàn thành một vết cắt tách biệt các đỉnh Theo nghiên cứu của Lehman [11] về Trò chơi Giải pháp của Trò chơi Chuyển đổi Shannon, ông đã chứng minh rằng Maker có chiến lược thắng lợi khi thi đấu trên các cạnh của đồ thị hoàn chỉnh nhằm hoàn thành một cây bao trùm, từ đó tạo ra một đường nối giữa hai đỉnh bất kỳ Ông cũng đã chỉ ra các điều kiện cần thiết trên đồ thị tổng quát để Breaker có thể phát triển chiến lược chiến thắng trong Trò chơi chuyển đổi Shannon.
Sau khi chuyển sang các trò chơi Maker-Breaker, các tác giả đã đạt được tiến bộ trong việc xác định kết quả trò chơi trên các bảng khác nhau bằng phương pháp xác suất sửa đổi Cụ thể, trong trò chơi Tic-Tac-Toe trên mạng số nguyên d chiều, một bộ chiến thắng được định nghĩa là tập hợp m điểm liên tiếp trên một dòng Bài viết "Chiến lược dựa trên tiềm năng của Tic-Tac-Toe trên Mạng số nguyên" của Kruczek và Sundberg đã xác định giới hạn kích thước bộ chiến thắng mà Breaker cần để giành chiến thắng khi các hướng chiến thắng bị giới hạn Các lập luận trong bài viết dựa trên phương pháp xác suất sửa đổi, được phát triển bởi Erdo¨s và Selfridge, sau đó được Beck điều chỉnh.
Các biến thể của Tic-Tac-Toe trên biểu đồ liên quan đến việc thay đổi cấu trúc bộ chiến thắng Trong nghiên cứu "Một ngưỡng sắc nét cho trò chơi Hamilton", tác giả Hefetz và cộng sự khám phá trò chơi Maker-Breaker trên các đồ thị ngẫu nhiên Họ xem xét đồ thị ngẫu nhiên G(n, p) với n đỉnh, trong đó mỗi cạnh được chọn độc lập với xác suất p Trong trò chơi này, người chơi Maker cố gắng hoàn thành Chu kỳ Hamilton Các kết quả cho thấy rằng với p lớn tương đối so với n, đồ thị ngẫu nhiên G(n, p) gần như chắc chắn sẽ có Chu kỳ Hamilton Kết quả chính của bài báo này là rất đáng chú ý.
Định lý 1.2.1 khẳng định rằng tồn tại một hằng số l > 0, trong đó trò chơi chu trình Hamilton trên đồ thị G với kích thước n, log n + (log log n) l gần như chắc chắn dẫn đến chiến thắng của Maker.
Các chiến lược phát triển từ phương pháp xác suất là điều quan trọng cần lưu ý Bản chất của xác suất liên quan đến sự tồn tại của hội đồng quản trị, không phải là chiến lược Khi một bảng đã được thiết lập, chính chiến lược sẽ quyết định kết quả của trò chơi.
Các biến thể trò chơi thiên vị cho phép hai người chơi đặt số lượng quân cờ khác nhau trên bảng, ví dụ như Maker đặt 1 mảnh và Breaker đặt q mảnh Mục tiêu là xác định giá trị ngưỡng của q, tại đó trò chơi chuyển từ Maker thắng sang Breaker thắng Trong bài viết "Các trò chơi vị trí thiên vị trên giấy" của Bednarska và Pikhurko, họ phân tích một trò chơi mà Makers cần yêu cầu một mạch của matroid và chứng minh các giá trị ngưỡng cho q dựa trên cấu trúc xếp hạng của matroid Cụ thể, nếu người chơi trên matroid chu kỳ của đồ thị hoàn chỉnh Kn, thì Maker sẽ thắng cho tất cả q < ⌈n / 2⌉ - 1 Họ cũng chỉ ra rằng ràng buộc này giữ cho trò chơi Maker-Breaker hoặc Breaker-Maker, trong đó Maker đặt 1 và Breaker đặt q miếng.
Một biến thể thú vị trong trò chơi là Chooser-Picker, hoạt động tương tự như thỏa hiệp cổ điển giữa người cắt và người chọn Trong trò chơi này, Bộ chọn sẽ xác định hai vị trí và sau đó quyết định vị trí nào sẽ được giữ lại Khác với phiên bản Picker-Chooser, trong Chooser-Picker, người chơi đóng vai trò Maker, trong khi người chọn lại giữ vai trò phá vỡ Những trò chơi này được phân tích chi tiết trong tài liệu nghiên cứu.
Trên nền tảng On Chooser Picker, các trò chơi định vị như Csernenszky, Ma bùndity và Pluha chứng minh rằng người chơi Maker có thể hoàn thành một cơ sở của matroid Trò chơi Picker-Chooser sẽ được thắng nếu và chỉ nếu có hai căn cứ rời rạc tồn tại (Định lý 2) Để tìm hiểu thêm về các biến thể của Tic-Tac-Toe, chúng tôi khuyên bạn nên tham khảo cuốn sách của Beck về chủ đề này.
Biến thể mà chúng tôi giới thiệu trong Phần 1.4 sẽ khác biệt so với các biến thể khác, nơi trò chơi được thực hiện theo các quy tắc cụ thể, tương tự như trong các trò chơi chiến thuật năng động như cờ đam hay cờ vua.
Chúng tôi sẽ xem xét phiên bản mạnh mẽ của trò chơi, trong đó cả hai người chơi đều nỗ lực để giành chiến thắng Mặc dù không nên thay đổi trò chơi thành trò chơi Maker-Breaker, nhưng luận án này không bao gồm bất kỳ phân tích nào liên quan đến vấn đề đó.
CƠ SỞ LÝ THUYẾT
Tic-Tac-Toe
Trong bài viết này, chúng ta sẽ khám phá trò chơi Hop-Tic-Tac-Toe, nơi Xgi và Ogi thi đấu trên lưới chín ô vuông của bảng Tic-Tac-Toe, áp dụng phương pháp đánh mới thay vì cách đặt miếng truyền thống Chúng tôi chứng minh rằng Xgi có thể giành chiến thắng ngay từ ba vị trí xuất phát khác nhau: giữa, góc hoặc cạnh Bảng Tic-Tac-Toe có chín điểm và tám bộ thắng, với điểm giữa nằm trên bốn đường thẳng, các góc nằm trên ba đường thẳng và các cạnh chỉ nằm trên hai đường thẳng Chúng tôi sẽ trình bày nước cờ chiến thắng đầu tiên của Xgi cho từng vị trí và phân tích các cây trò chơi tương ứng, cho thấy Ogi không thể đạt được kết quả hòa Cuối cùng, chúng tôi khẳng định rằng Xgi có thể chiến thắng mà không cần tạo ra một sự ràng buộc, đồng thời chỉ ra các vị trí cụ thể trên bảng như được đánh số trong hình 2.1.
Bảng Tic-Tac-Toe truyền thống được thể hiện với các vị trí đánh số như trong Hình 2.1 Theo Định lý 2.1.1, người chơi X có thể áp dụng chiến lược chiến thắng từ bất kỳ vị trí xuất phát nào trên bảng Tic-Tac-Toe.
Bằng chứng của chúng tôi được phân loại thành ba trường hợp dựa trên ba vị trí bắt đầu khác nhau: vị trí giữa {5}, góc {1,3,7,9} và cạnh {2,4,6,8}.
Bắt đầu với chữ X ở giữa bảng, Xgi có thể giành chiến thắng bằng cách đánh vào một góc trong lượt đầu tiên Giả sử Xgi đánh từ vị trí 5 đến vị trí 1, Ogi có bốn lựa chọn khác nhau, như mô tả trong Hình (2.2) Dù Ogi chọn động thái nào, Xgi luôn có thể giữ X ở vị trí 1 và 5.
Bài viết mô tả bốn cấu hình có thể xảy ra trong trò chơi, bắt đầu với X ở vị trí chính giữa và Xgi thực hiện một bước đánh vào bất kỳ góc nào Các trạng thái này được chỉ định là A, B, C hoặc D.
Bây giờ chúng tôi giải quyết lần lượt thứ hai của Xgi Xgi cần xem xét các sự kiện sau:
• Lượt thứ hai của Ogi sẽ thay đổi một trong hai chữ O của cô ấy thành chữ X
Sau lượt thứ hai, Ogi sẽ sở hữu ba mảnh thành, giúp anh có đủ miếng trên bảng để giành chiến thắng trong lượt thứ ba.
Trong trò chơi Tic-Tac-Toe, cần chú ý đến sự tồn tại của các đường song song Người chơi nên cẩn thận để không chọn vào một cột trong lượt thứ ba của mình, nhằm tránh bị đối thủ chặn đường thắng.
Chiến thắng của Xgi chanh phụ thuộc vào việc sắp xếp hai quân cờ của anh ta trên một đường thẳng và hai mảnh ghép của anh ta cũng phải nằm trên một đường thẳng với hai mảnh ghép của Ogi Để đảm bảo điều này, Xgi không nên chọn vị trí khác ngoài vị trí 5, vì vị trí này nằm trên một đường thẳng với mọi vị trí khác trên bảng Bằng cách giữ X ở vị trí 5, anh ta có thể chắc chắn rằng hai quân X của mình sẽ chia sẻ một dòng, đồng thời vị trí này cũng sẽ nằm trên một đường thẳng với hai quân O sau lượt của anh ta.
Để di chuyển quân cờ từ vị trí 1, người chơi cần xác định đích đến theo điều kiện cụ thể Trước hết, anh ta nên chọn một vị trí nằm trên đường thẳng với vị trí 1, điều này giúp đảm bảo rằng quân cờ thứ hai sẽ nằm trên đường thẳng với vị trí O mới sau lượt di chuyển Hơn nữa, anh ta cũng cần chọn một vị trí nằm trên đường thẳng với O hiện tại của Ogi Tóm lại, anh ta nên di chuyển dọc theo một trong hai đường chứa vị trí 1 cho đến khi nó giao nhau với đường có chứa mảnh ghép hiện tại của Ogi.
Sau khi Ogi chuyển sang trạng thái A, O hiện đang ở vị trí 2, nằm trên hai dòng {1, 2, 3} và {2, 5, 8} Do đó, Xgi cần lựa chọn một trong các vị trí mở.
{3, 8}, trong khi vẫn ở trên một dòng với 1 X ở vị trí 1 nằm trên ba dòng, {1, 2, 3}, {1, 4, 7} và {1, 5, 9}
Theo chiến lược của mình, Xgi phải chọn từ 1 dọc theo dòng {1, 2, 3} đến vị trí mở 3 An
Di chuyển tối ưu của Xgi cho từng tùy chọn Ogi được thể hiện rõ trong Hình 2.3 Chúng tôi nhấn mạnh rằng, trong mọi trường hợp, Xgi luôn lựa chọn từ vị trí 1 để đảm bảo mỗi tác phẩm của anh ta nằm trên một đường thẳng với từng Ogi.
Bước chọn tối ưu thứ hai cho Xgi từ các tùy chọn của Ogi được thể hiện trong Hình 2.3, trong đó lượt của Xgi bắt đầu từ các mảnh ở vị trí 1 và 5 Anh ta lựa chọn các vị trí sao cho mỗi mảnh của mình nằm trên một đường thẳng với từng mảnh của Ogi.
Bằng cách sắp xếp các quân cờ thẳng hàng với từng Ogi, Xgi đảm bảo rằng sau mỗi Ogi, ba mảnh của mình sẽ nằm trên cùng một đường thẳng Khi Ogi được thực hiện, Xgi có thể tạo ra ba điểm trên một đường hoặc ba mảnh của mình sẽ xác định ba đường khác nhau Với chỉ hai mảnh của Ogi trên bảng, Xgi có thể chắc chắn rằng ít nhất một trong ba đường sẽ không bị chặn.
O Đó là một trong ba dòng được Ogi bỏ chặn Vì vậy, anh ta có thể yêu cầu một dòng chiến thắng trong lượt tiếp theo của mình Câu hỏi bây giờ là: anh ta có thể yêu cầu một dòng chiến thắng mà không cho Ogi một dòng chiến thắng không? Đó là, anh ta có thể
Hội đồng quản trị thừa nhận rằng có những trạng thái bị ràng buộc, do đó, chúng tôi cần xác minh rằng Xgi đã không chuyển sang một trong các trạng thái đó để tránh tạo ra một cột.
Chiến lược game Tic-Tac-Toe
Người chơi có thể đạt được kết quả tốt nhất trong trò chơi tic-tac-toe bằng cách luôn chọn nước đi đầu tiên từ danh sách đã được xác định trong chương trình tic-tac-toe của Newell và Simon năm 1972, giúp họ giành chiến thắng hoặc ít nhất là hòa.
1 Thắng : Nếu người chơi có hai liên tiếp, họ có thể đặt một phần ba để có được ba liên tiếp
2 Chặn : Nếu đối thủ có hai liên tiếp, người chơi phải tự chơi thứ ba để chặn đối thủ
3 Fork : Tạo cơ hội trong đó người chơi có hai cách để giành chiến thắng (hai dòng không bị chặn là 2)
4 Chặn ngã ba của đối thủ : Nếu chỉ có một ngã ba có thể có cho đối thủ, người chơi nên chặn nó Nếu không, người chơi nên chặn tất cả các nhánh theo bất kỳ cách nào đồng thời cho phép họ tạo hai liên tiếp Mặt khác, người chơi nên tạo một hai liên tiếp để buộc đối thủ phòng thủ, miễn là điều đó không dẫn đến việc họ tạo ra một ngã ba Ví dụ: nếu "X" có hai góc đối diện và "O" có tâm, "O" không được chơi di chuyển góc để giành chiến thắng (Chơi di chuyển góc trong kịch bản này sẽ tạo ra một ngã ba để "X" giành chiến thắng.)
5 Center : Một người chơi đánh dấu trung tâm (Nếu đó là nước đi đầu tiên của trò chơi, chơi di chuyển góc sẽ cho người chơi thứ hai nhiều cơ hội hơn để mắc lỗi và do đó có thể là lựa chọn tốt hơn; tuy nhiên, điều đó không tạo ra sự khác biệt giữa những người chơi hoàn hảo.)
6 Góc đối diện : Nếu đối thủ ở góc, người chơi sẽ chơi góc đối diện
7 Góc trống : Người chơi chơi trong một góc vuông
8 Mặt trống : Người chơi chơi ở một hình vuông ở giữa trong bất kỳ 4 mặt nào
Người chơi đầu tiên, được chỉ định là "X", có ba vị trí chiến lược để đánh dấu trong lượt đầu tiên: góc, cạnh hoặc trung tâm Mặc dù có vẻ như có 9 vị trí khả dụng trong lưới, nhưng việc xoay bảng cho thấy rằng mọi dấu góc và dấu cạnh đều tương đương về mặt chiến lược Do đó, từ góc độ chiến lược, chỉ có ba lựa chọn ban đầu cho người chơi X.
Chơi từ góc có thể giúp người chơi rút một trận hòa, nhưng điều này cũng cho phép đối thủ chọn hình vuông nhỏ nhất để tránh thua Điều này cho thấy rằng việc bắt đầu từ góc là một bước mở tốt nhất cho X Nếu người chơi không hoàn hảo, thì một động thái mở ở trung tâm sẽ là lựa chọn tốt nhất cho X.
Người chơi thứ hai, được gọi là "O", cần phải phản hồi điểm mở của "X" một cách chiến lược để ngăn chặn chiến thắng O phải luôn đáp lại các điểm mở ở góc bằng dấu trung tâm và các điểm mở trung tâm bằng dấu góc Đối với các điểm mở ở cạnh, O cần dùng dấu trung tâm, dấu góc bên cạnh X hoặc dấu cạnh đối diện với X Nếu O không tuân theo quy tắc này, X sẽ có cơ hội thắng Sau khi hoàn thành các nước đi, nhiệm vụ của O là theo dõi danh sách ưu tiên để buộc hòa hoặc giành chiến thắng nếu X chơi yếu.
Chi tiết hơn, để đảm bảo rút thăm, O nên áp dụng các chiến lược sau:
Khi X chọn di chuyển mở góc, O sẽ lấy tâm và sau đó là một cạnh, buộc X phải chặn trong lượt tiếp theo để ngăn chặn dĩa Nếu cả hai người chơi đều hoàn hảo, X bắt đầu bằng góc, O sẽ chọn tâm, và X sẽ lấy góc đối diện O có thể tự do chọn bất kỳ cạnh nào cho lượt di chuyển thứ hai Tuy nhiên, nếu X không hoàn hảo và đã chơi một góc rồi đến một cạnh, O không nên chọn cạnh đối diện cho lượt thứ hai, vì điều này cho phép X không phải chặn và có thể tạo ra nhiều nhánh khác.
Nếu X chơi di chuyển mở cạnh, O nên lấy tâm hoặc một trong các góc liền kề với
X, sau đó làm theo danh sách ưu tiên ở trên, chủ yếu chú ý đến các dĩa chặn
Nếu X chơi di chuyển mở trung tâm, O nên lấy góc, và sau đó làm theo danh sách ưu tiên ở trên, chủ yếu chú ý đến các dĩa chặn
Khi X chơi góc đầu tiên và O không phải là người chơi hoàn hảo, điều sau đây có thể xảy ra:
Nếu O phản hồi bằng dấu trung tâm, người chơi X hoàn hảo sẽ chọn góc đối diện với bản gốc Trong trường hợp này, O nên chơi ở một cạnh để tối ưu hóa chiến lược của mình.
Trong trò chơi, khi một người chơi X hoàn hảo thực hiện bước di chuyển thứ hai, họ sẽ đánh dấu góc còn lại để ngăn chặn O tạo thành ba liên tiếp Đồng thời, bước đi này cũng tạo ra một ngã ba cho chính họ.
Nếu O trả lời bằng một dấu góc, X sẽ chắc chắn giành chiến thắng bằng cách chiếm hai góc còn lại và cuối cùng là một ngã ba Khi X có được góc thứ ba, O chỉ có thể chiếm vị trí giữa hai X, và sau đó X sẽ lấy góc còn lại duy nhất để chiến thắng.
Nếu O phản ứng bằng cách đánh dấu cạnh, X sẽ chắc chắn giành chiến thắng bằng cách chiếm trung tâm Trong trường hợp này, O chỉ có thể chiếm góc đối diện với góc mà X đã chọn trước đó Cuối cùng, X có thể chiếm một góc để tạo ra một ngã ba, từ đó giành chiến thắng trong lượt đi tiếp theo.
Hãy xem xét một bảng với chín vị trí được đánh số như sau:
Khi X đóng 1 làm bước mở đầu của họ, thì O sẽ lấy 5 Sau đó X lấy 9 (trong tình huống này, O không nên lấy 3 hoặc 7, O nên lấy 2, 4, 6 hoặc 8):
Trong trò chơi này, nếu các nước đi là X1 → O5 → X9 → O2 → X8 → O7 → X3 → O6 → X4, kết quả sẽ là một trận hòa Tuy nhiên, trong trường hợp O không nên mất 4 hoặc 7, mà nên chọn 2, 3, 8 hoặc 9 Thực tế, việc chọn 9 là lựa chọn tốt nhất, vì nếu người chơi X không hoàn hảo, họ có thể mất 4, và sau đó O có cơ hội giành chiến thắng bằng cách lấy 7.
X1 → O5 → X6 → O2 → X8, sau đó O không nên lấy 3 hoặc X có thể lấy 7 để thắng và
O không nên lấy 4, hoặc X có thể lấy 9 để thắng, O nên lấy 7 hoặc 9
X1 → O5 → X6 → O2 → X8 → O7 → X3 → O9 → X4, trò chơi này sẽ là một trận hòa
X1 → O5 → X6 → O2 → X8 → O9 → X4 (7) → O7 (4) → X3, trò chơi này sẽ là một trận hòa
X1 → O5 → X6 → O3 → X7 → O4 → X8 (9) → O9 (8) → X2, trò chơi này sẽ là một trận hòa
X1 → O5 → X6 → O8 → X2 → O3 → X7 → O4 → X9, trò chơi này sẽ là một trận hòa
X1 → O5 → X6 → O9, sau đó X không nên lấy 4 hoặc O có thể lấy 7 để giành chiến thắng,
X1 → O5 → X6 → O9 → X2 → O3 → X7 → O4 → X8, trò chơi này sẽ là một trận hòa
X1 → O5 → X6 → O9 → X3 → O2 → X8 → O4 (7) → X7 (4), trò chơi này sẽ là một trận hòa
X1 → O5 → X6 → O9 → X7 → O4 → X2 (3) → O3 (2) → X8, trò chơi này sẽ là một trận hòa
3 / 2) → X3 (2, 7, 4), trò chơi này sẽ là một trận hòa
Trong cả hai tình huống này (X mất 9 hoặc 6 lần di chuyển thứ hai), X có một 1/3 tài sản để giành chiến thắng
Nếu X không phải là người chơi hoàn hảo, X có thể mất 2 hoặc 3 lần di chuyển thứ hai Sau đó, trò chơi này sẽ là một trận hòa, X không thể thắng
X1 → O5 → X2 → O3 → X7 → O4 → X6 → O8 (9) → X9 (8), trò chơi này sẽ là một trận hòa
X1 → O5 → X3 → O2 → X8 → O4 (6) → X6 (4) → O9 (7) → X7 (9), trò chơi này sẽ là một trận hòa
Nếu X chơi 1 lượt mở và O không phải là người chơi hoàn hảo, điều sau đây có thể xảy ra:
Mặc dù O có vị trí tốt duy nhất (5) là nước đi đầu tiên, nhưng O có vị trí xấu là nước đi thứ hai:
X1 → O5 → X9 → O3 → X7, sau đó X có thể mất 4 hoặc 8 để giành chiến thắng
X1 → O5 → X6 → O4 → X3, sau đó X có thể mất 2 hoặc 9 để giành chiến thắng
X1 → O5 → X6 → O7 → X3, sau đó X có thể mất 2 hoặc 9 để giành chiến thắng
Mặc dù O có vị trí tốt là hai nước đi đầu tiên, nhưng O có vị trí xấu là nước đi thứ ba:
X1 → O5 → X6 → O2 → X8 → O3 → X7, sau đó X có thể mất 4 hoặc 9 để giành chiến thắng
X1 → O5 → X6 → O2 → X8 → O4 → X9, sau đó X có thể mất 3 hoặc 7 để giành chiến thắng
O có vị trí xấu khi di chuyển đầu tiên (ngoại trừ 5, tất cả các vị trí khác đều xấu):
X1 → O3 → X7 → O4 → X9, sau đó X có thể mất 5 hoặc 8 để giành chiến thắng
X1 → O9 → X3 → O2 → X7, sau đó X có thể mất 4 hoặc 5 để giành chiến thắng
X1 → O2 → X5 → O9 → X7, sau đó X có thể mất 3 hoặc 4 để giành chiến thắng
X1 → O6 → X5 → O9 → X3, sau đó X có thể mất 2 hoặc 7 để giành chiến thắng
NGUYÊN CỨU, TÍNH TOÁN, THIẾT KẾ TIC-TAC-TOE
Bản chất mạch vi điều khiển – tự động hóa
- Là một máy tính được tích hợp trên một chíp, nó thường được sử dụng để điều khiển các thiết bị điện tử
Hình 4.1: Bộ vi điều khiển
Vi điều khiển là một hệ thống tích hợp bao gồm vi xử lý chuyên dụng, khác với các bộ vi xử lý đa năng trong máy tính, kết hợp với các thiết bị ngoại vi như bộ nhớ, mô đun vào/ra, và các mô đun chuyển đổi tín hiệu giữa dạng số và dạng tương tự.
Vi điều khiển là thành phần quan trọng trong việc phát triển các hệ thống nhúng, được ứng dụng rộng rãi trong các thiết bị điện tử và điện như máy giặt, điện thoại di động và dây chuyền tự động.
- Thiết bị điện tử là các công cụ điện tử được tạo từ các vật Dẫn điện và Bán dẫn điện o Dẫn điện
Điện trở: Thiết bị điện có khả năng làm giảm dòng điện
Tụ điện: Thiết bị điện có khả năng lưu trữ điện dưới dạng điện trường
Cuộn cảm: Thiết bị điện có khả năng lưu trữ điện dưới dạng từ trường
Công Tắc: Thiết bị điện có khả năng đóng/mở mạch điện
Cầu Chì: Thiết bị điện có khả năng hở (ngắt) mạch điện khi dòng điện đi qua cầu chì vượt quá mức dẫn điện của cầu chì
Biến điện: Thiết bị điện có khả năng tăng, giảm, dẫn điện
Cấu trúc cơ bản của một vi điều khiển bao gồm:
CPU là bộ não trung tâm của vi điều khiển, chịu trách nhiệm quản lý mọi hoạt động của hệ thống Nó thực hiện các thao tác quan trọng trên dữ liệu như nạp, giải mã và thực thi lệnh Ngoài ra, CPU còn kết nối tất cả các thành phần của vi điều khiển thành một hệ thống thống nhất.
Bộ nhớ trong vi điều khiển đóng vai trò quan trọng tương tự như bộ vi xử lý, vì nó lưu trữ tất cả các chương trình và dữ liệu cần thiết Bộ nhớ của vi điều khiển thường bao gồm bộ nhớ ROM (như EPROM, EEPROM) và bộ nhớ RAM với dung lượng nhất định Hiện nay, bộ nhớ flash cũng được sử dụng để lưu trữ mã nguồn chương trình, mang lại sự linh hoạt và hiệu quả cao hơn trong việc quản lý dữ liệu.
Cổng Input/Output (I/O) là giao diện quan trọng để kết nối và giao tiếp với các thiết bị bên ngoài Chúng được sử dụng để điều khiển và tương tác với nhiều thiết bị khác nhau, bao gồm máy in, màn hình LCD và LED.
- Serial Ports: Những cổng này cung cấp giao tiếp nối tiếp giữa vi điều khiển và thiết bị ngoại vi khác nhau
Vi điều khiển được trang bị một hoặc nhiều Timer, đóng vai trò quan trọng trong việc kiểm soát các bộ đếm và thời gian hoạt động bên trong Các Timer và bộ định thời này giúp quản lý và điều chỉnh các chức năng hoạt động của vi điều khiển một cách hiệu quả.
34 | P a g e khiển Timer được sử dụng đếm xung bên ngoài Các hoạt động chính được thực hiện bởi timers “tạo xung, đo tần số điều chế, tạo dao động,v.v “
- ADC (Analog to digital converter): ADC là bộ chuyển đổi tín hiệu tương tự sang tín hiệu số
- DAC (Digital to analog converter): Có chức năng ngược lại với ADC DAC thường được sử dụng để giám sát các thiết bị tương tự
Điều khiển ngắt là một cơ chế cho phép bộ vi điều khiển tạm dừng chương trình hiện tại để xử lý các sự kiện khẩn cấp xảy ra bên trong hoặc bên ngoài Khi một ngắt xảy ra, vi điều khiển sẽ chuyển sang thực hiện nhiệm vụ của trình phục vụ ngắt (ISR: Interrupt Service Routine) để đáp ứng ngay lập tức yêu cầu của ngắt.
- Viết tắt là àP hay uP đụi khi cũn được gọi là bộ vi xử lý
- Là một linh kiện điện tử máy tính được chế tạo từ các tranzito thu nhỏ tích hợp lên trên một vi mạch tích hợp đơn
Khối xử lý trung tâm (CPU - Central Processing Unit) là bộ vi xử lý chính trong máy tính, chịu trách nhiệm thực hiện các phép toán và xử lý dữ liệu Ngoài CPU, nhiều thành phần khác trong máy tính cũng sở hữu bộ vi xử lý riêng, chẳng hạn như các màn hình, giúp nâng cao hiệu suất và khả năng xử lý thông tin.
Bộ nhớ máy tính là các phương thức và hình thức lưu trữ dữ liệu, bao gồm lưu trữ lâu dài để bảo toàn thông tin sau khi kết thúc phiên làm việc, và lưu trữ tạm thời trong quá trình làm việc, khi dữ liệu sẽ bị xóa sau khi phiên làm việc kết thúc.
- Các thiết bị lưu trữ dữ liệu cho bộ nhớ lâu dài bao gồm: Đĩa cứng, Đĩa mềm, Đĩa quang, Băng từ, ROM, các loại bút nhớ
- Các thiết bị lưu trữ dữ liệu tạm thời trong quá trình làm việc: RAM máy tính, Cache
Vi điều khiển Vi xử lý
Vi điều khiển sử dụng cấu trúc RISC và Harvard Nhưng cũng có một số vi điều khiển sử dụng cấu trúc CISC như
Hầu hết các bộ vi xử lý sử dụng cấu trúc CISC và Von-Neumann Tuy
8051 và SHARC Bộ vi xử lý có ROM,
RAM, bộ nhớ lưu trữ thứ cấp, thiết bị ngoại vi I/O và timer bộ đếm được tích hợp trên một board mạch và kết nối qua bus, tạo thành vi điều khiển Trong đó, bộ vi xử lý phổ biến thường áp dụng cấu trúc CISC.
Bộ vi điều khiển thường chậm hơn so với bộ vi xử lý, nhưng tốc độ thực thi phụ thuộc vào tần số đồng hồ Khi so sánh hiệu suất tổng thể và ứng dụng, vi điều khiển thực hiện nhanh chóng nhờ vào sự hỗ trợ của các thiết bị ngoại vi sẵn có.
Bộ vi xử lý hoạt động với tốc độ nhanh hơn so với các bộ điều khiển nhờ vào tần số xung nhịp cao Điều này giúp nâng cao hiệu suất xử lý và khả năng thực hiện các tác vụ phức tạp một cách hiệu quả hơn.
Thiết kế một vi điều khiển sẽ mất ít thời gian hơn khi thiết kế bộ vi xử lý
Việc giao tiếp giữa các thiết bị ngoại vi và chương trình dễ dàng hơn khi so sánh với bộ vi xử lý
Vi điều khiển được thiết kế để thực hiện các chức năng cụ thể, trong đó mối quan hệ giữa đầu vào và đầu ra được xác định rõ ràng.
Tùy thuộc vào đầu vào, cần thực hiện một số xử lý và thiết lập từ đầu ra cho các thiết bị như bàn phím, chuột, máy giặt, máy ảnh kỹ thuật số, USB, điều khiển từ xa, lò vi sóng, xe hơi, xe đạp, điện thoại, điện thoại di động và đồng hồ Khi ứng dụng được cụ thể hóa, tài nguyên yêu cầu như RAM, ROM và cổng I/O thường nhỏ, cho phép chúng có thể được nhúng vào một chip duy nhất.
36 | P a g e nhất Điều này sẽ làm giảm kích thước và chi phí Ứng dụng
Vi điều khiển được sử dụng chủ yếu trong các ứng dụng nhúng như đồng hồ, điện thoại di động, máy nghe nhạc mp3
Bộ vi xử lý chủ yếu được sử dụng trong các hệ thống máy tính, hệ thống quốc phòng, mạng thông tin liên lạc
So sánh chi phí giữa vi điều khiển và vi xử lý là không hợp lý, vì vi điều khiển thường rẻ hơn vi xử lý Tuy nhiên, vi điều khiển không thể thay thế cho vi xử lý và ngược lại, do mỗi loại có vai trò quan trọng riêng trong việc phát triển các ứng dụng.
Bảng 4.1: So sánh giữa vi điều khiển và vi xử lý
Mạch điều khiển trung tâm
Hình 4.2: Chân kết nối board adruino mega 2560
Vi điều khiển chính: ATmega2560
IC nạp và giao tiếp UART: ATmega16U2
Nguồn nuôi mạch nên sử dụng 5VDC từ cổng USB hoặc nguồn ngoài qua giắc tròn DC, với khuyến cáo sử dụng 7-9VDC để đảm bảo mạch hoạt động ổn định Việc sử dụng nguồn 12V có thể làm IC ổn áp dễ hỏng và gây ra sự cố cho mạch.
Số chân Digital: 54 (15 chân PWM)
Giao tiếp UART : 4 bộ UART
Giao tiếp SPI : 1 bộ ( chân 50 -> 53 ) dùng với thư viện SPI của Arduino
Bộ nhớ Flash: 256 KB, 8KB sử dụng cho Bootloader
Yêu cầu cấu hình máy tính điều khiển tối thiểu:
Tốc độ xử lý 1 GHz hoặc nhanh hơn
Không gian ổ đĩa cài đặt còn trống 500MB
Hỗ trợ đồ họa OpenGL
Kết nối NET Framework 3.5 SP1 Đề nghị cấu hình máy tính điều khiển tối thiểu:
Tốc độ xử lý 2 GHz hoặc nhanh hơn
Không gian ổ đĩa cài đặt còn trống 500MB
Hỗ trợ đồ họa OpenGL
Kết nối NET Framework 3.5 SP1
Cơ cấu servo
Trong kỹ thuật điều khiển, servo là thiết bị tự động sử dụng phản hồi âm từ cảm biến để điều chỉnh hành động Nó thường bao gồm bộ mã hóa bên trong hoặc cơ cấu phản hồi vị trí khác nhằm đảm bảo đầu ra đạt hiệu quả mong muốn.
Thuật ngữ "servo" chỉ áp dụng cho các hệ thống có thông tin phản hồi hoặc tín hiệu điều chỉnh sai số để kiểm soát vị trí, tốc độ và các thông số khác Ví dụ, điều khiển cửa sổ điện của ô tô không phải là cơ cấu servo vì không có phản hồi tự động; người vận hành phải quan sát để điều chỉnh Ngược lại, hệ thống điều khiển hành trình của xe ô tô sử dụng phản hồi vòng kín và do đó được coi là cơ cấu servo.
4.3.1 Lịch sử cơ cấu servo
Thiết bị điều tốc động cơ hơi nước của James Watt được xem là hệ thống phản hồi đầu tiên, đánh dấu bước tiến quan trọng trong công nghệ điều khiển Mặc dù các đuôi quạt cối xay gió là một ví dụ sớm về điều khiển tự động, nhưng do thiếu bộ khuếch đại hoặc độ lợi, chúng thường không được công nhận là cơ cấu servo.
Động cơ lái tàu là thiết bị điều khiển vị trí phản hồi đầu tiên, giúp xác định vị trí bánh lái của tàu lớn dựa trên vị trí vô lăng John McFarlane Grey là người tiên phong trong lĩnh vực này, với thiết kế được cấp bằng sáng chế sử dụng trên tàu SS Great Eastern vào năm 1866 Joseph Farcot cũng đóng góp quan trọng với nhiều bằng sáng chế về khái niệm phản hồi từ năm 1862 đến 1868 Vào khoảng năm 1872, Andrew Betts Brown phát minh ra động cơ tổ hợp (telemotor), đơn giản hóa cơ cấu giữa phòng điều khiển và động cơ Động cơ lái hơi nước có tính năng tương tự như một cơ cấu servo hiện đại, với đầu vào, đầu ra, tín hiệu sai số và phương tiện khuếch đại tín hiệu sai số để điều chỉnh tiến tới giá trị zero Cơ cấu công suất ngược Ragonnet, được cấp bằng sáng chế vào năm 1909, là bộ khuếch đại servo đa mục đích chạy bằng khí hoặc hơi nước cho chuyển động thẳng.
Các cơ cấu servo điện được sử dụng sớm nhất vào năm 1888 trong máy truyền điện bằng chữ viết của Elisha Gray
Các cơ cấu servo điện cần một bộ khuếch đại công suất, với sự phát triển đáng chú ý trong Thế chiến II khi amplidyne được sử dụng làm bộ khuếch đại cho các hệ thống điều khiển hỏa lực điện Bộ khuếch đại ống chân không cũng đã được ứng dụng trong truyền động ổ băng UNISERVO cho máy tính UNIVAC I Vào năm 1928, Hải quân Hoàng gia Anh đã thử nghiệm điều khiển công suất từ xa (RPC) trên HMS Champion, và đến đầu thập niên 1930, RPC đã được sử dụng để điều khiển đèn pha rọi máy bay địch Trong Thế chiến II, RPC tiếp tục được ứng dụng để điều khiển giá pháo và thiết bị chỉ thị mục tiêu cho pháo.
Cơ cấu servo hiện đại sử dụng bộ khuếch đại công suất trạng thái rắn, chủ yếu là MOSFET hoặc thyristor, trong khi các servo nhỏ có thể áp dụng transistor công suất.
Từ "servomotor" có nguồn gốc từ tiếng Pháp "Le Servomoteur" hoặc từ "slavemotor", lần đầu tiên được JJL Farcot sử dụng vào năm 1868 Thuật ngữ này dùng để mô tả động cơ thủy lực và hơi nước trong hệ thống lái của tàu thủy.
Servo cơ bản nhất hoạt động dựa trên điều khiển bang-bang, trong khi các hệ thống điều khiển phức tạp hơn áp dụng các phương pháp như điều khiển tỷ lệ, điều khiển PID và điều khiển không gian trạng thái, được nghiên cứu trong lý thuyết điều khiển hiện đại.
Cơ cấu servo là một loại động cơ đặc biệt kết hợp với bộ mã hóa quay hoặc chiết áp, tạo thành một hệ thống điều khiển chính xác Chiết áp cung cấp tín hiệu analog đơn giản để xác định vị trí, trong khi bộ mã hóa cung cấp thông tin về vị trí và tốc độ phản hồi Sử dụng bộ điều khiển PID giúp cải thiện độ chính xác và tốc độ ổn định của vị trí động cơ Mặc dù chiết áp có thể bị ảnh hưởng bởi sự thay đổi nhiệt độ, bộ mã hóa lại mang lại độ ổn định và chính xác cao hơn.
Cơ cấu servo được phân loại thành hai loại chính: cao cấp và thấp cấp Các linh kiện cao cấp là những thiết bị công nghiệp chính xác với bộ mã hóa quay, trong khi các servo thấp cấp, như servo điều khiển vô tuyến (RC servo), là những sản phẩm giá rẻ dùng trong mô hình điều khiển bằng radio, sử dụng động cơ chuyển động tự do và cảm biến vị trí chiết áp đơn giản Thuật ngữ "động cơ servo" thường chỉ các thành phần công nghiệp cao cấp, trong khi "servo" thường ám chỉ các thiết bị rẻ hơn Mặc dù động cơ bước không được coi là động cơ servo, chúng vẫn đóng vai trò quan trọng trong việc tạo ra các cơ cấu servo lớn hơn, với khả năng định vị theo góc cố hữu và thường được sử dụng trong các ứng dụng có độ chính xác vừa phải mà không cần tín hiệu phản hồi.
Các servo RC là thành phần quan trọng trong các hệ thống cơ khí như hệ thống lái ô tô, bề mặt điều khiển máy bay và bánh lái thuyền, nhờ vào giá thành hợp lý và độ tin cậy cao Chúng thường được sử dụng trong các ứng dụng robot quy mô nhỏ vì dễ dàng điều khiển bằng bộ vi xử lý Bộ nhận RC tiêu chuẩn gửi tín hiệu điều chế độ rộng xung (PWM) đến servo, và thiết bị điện tử bên trong servo chuyển đổi tín hiệu này thành vị trí Khi nhận lệnh xoay, động cơ servo sẽ hoạt động cho đến khi đạt được vị trí mong muốn tương ứng với giá trị chiết áp.
Servo là một loại cơ cấu phổ biến hỗ trợ điều khiển vị trí, có thể hoạt động bằng điện, thủy lực hoặc khí nén Chúng dựa trên nguyên lý phản hồi âm, trong đó đầu vào điều khiển được so sánh với vị trí thực tế của hệ thống cơ khí thông qua cảm biến Khoảng chênh lệch giữa giá trị thực tế và giá trị mong muốn, hay còn gọi là "tín hiệu sai số", sẽ được khuếch đại và chuyển đổi để điều chỉnh hệ thống nhằm giảm thiểu sai số Quá trình này thể hiện ứng dụng rộng rãi của lý thuyết điều khiển, với các servo điển hình có thể cung cấp chuyển động tròn hoặc chuyển động thẳng.
4.3.4 Điều khiển động cơ servo Điều khiển servo được thực hiện bằng cách gửi đi một servo tín hiệu PWM (điều chế độ rộng xung), một loạt các xung lặp lại có chiều rộng thay đổi, trong đó chiều rộng của xung (servo hiện đại phổ biến nhất) hoặc chu kỳ làm việc của một mạch xung (ngày nay ít phổ biến hơn) để xác định vị trí đạt được bởi servo Tín hiệu PWM có thể đến từ một bộ thu điều khiển vô tuyến tới servo hoặc từ các bộ vi-điều-khiển thông thường như Arduino
Hình 4.5 Xung PWM cho động cơ servo
Các servo nhỏ, hay còn gọi là servo RC, thường được kết nối qua một dây nối ba tiêu chuẩn, trong đó hai dây cung cấp nguồn DC và một dây điều khiển mang các xung điều khiển.
Các thông số quan trọng cho xung servo bao gồm chiều rộng xung nhỏ nhất, chiều rộng xung lớn nhất và tốc độ lặp lại Điểm trung tính của servo được xác định là vị trí mà servo có số vòng quay cơ học tiềm năng bằng nhau theo cả hai hướng quay Mặc dù các servo khác nhau có giới hạn vòng quay khác nhau, tất cả đều có một vị trí trung tính, thường nằm trong khoảng 1,5 miligiây (ms).
Giải thuật cắt tỉa Alpha-beta
Cắt tỉa Alpha-beta sẽ giúp loại bỏ những không gian trạng thái không cần thiết và hỗ trợ tối ưu hóa thuật toán tìm kiếm Minimax
Giải thuật cắt tỉa Alpha-beta đã được nhiều nhà khoa học máy tính phát triển và cải tiến liên tục Thuật toán này thường được kết hợp với thuật toán tìm kiếm Minimax, nhằm giảm thiểu không gian trạng thái trong cây trò chơi, giúp Minimax thực hiện tìm kiếm sâu và nhanh hơn Nguyên tắc cơ bản của giải thuật cắt tỉa Alpha-beta là "Nếu biết là trường hợp xấu thì không cần phải xét thêm".
Giải thuật Minimax là một phương pháp đệ quy để chọn nước đi tiếp theo trong các trò chơi hai người như tic-tac-toe, cờ vua, cờ tướng, cờ caro và cờ vây Trong các trò chơi này, người chơi lần lượt thực hiện các nước đi, và để đưa ra quyết định tốt nhất, bạn cần dự đoán phản ứng của đối thủ Giải thuật Minimax giả định rằng đối thủ cũng sẽ sử dụng chiến lược tối ưu tương tự, từ đó tìm kiếm không gian trạng thái của trò chơi để xác định nước đi tối ưu.
Trong trò chơi, hai đối thủ MIN và MAX lần lượt thay phiên nhau hành động MAX đại diện cho người chơi quyết tâm chiến thắng và nỗ lực tối đa hóa lợi thế của mình, trong khi MIN cố gắng giảm điểm số của MAX và làm cho điểm số của mình càng thấp càng tốt Cả hai đối thủ đều có kiến thức tương đương về không gian trạng thái của trò chơi và đều nỗ lực như nhau để đạt được mục tiêu.
Mỗi Node biểu diễn cho một trạng thái trên cây trò chơi Node lá là Node chứa trạng thái kết thúc của trò chơi
Giải thuật Minimax thể hiện bằng cách định trị các Node trên cây trò chơi:
Node thuộc lớp MAX thì gán cho nó giá trị lớn nhất của con Node đó
Node thuộc lớp MIN thì gán cho nó giá trị nhỏ nhất của con Node đó
Từ các giá trị này người chơi sẽ lựa chọn cho mình nước đi tiếp theo hợp lý nhất
4.4.2 Các bước giải thuật MinMax:
Nếu như đạt đến giới hạn tìm kiếm (đến tầng dưới cùng của cây tìm kiếm tức là trạng thái kết thúc của trò chơi)
Tính giá trị của thế cờ hiện tại ứng với người chơi ở đó Ghi nhớ kết quả
Khi xem xét mức của người chơi cực tiểu (nút MIN), hãy áp dụng quy trình Minimax cho các nhánh con của nó và ghi lại kết quả nhỏ nhất.
Khi áp dụng thủ tục Minimax cho người chơi cực đại (nút MAX), cần xem xét các con của nó và ghi nhớ kết quả lớn nhất từ các lựa chọn này.
Nếu như đạt đến giới hạn tìm kiếm (đến tầng dưới cùng của cây tìm kiếm tức là trạng thái kết thúc của trò chơi)
Tính giá trị của thế cờ hiện tại ứng với người chơi ở đó Ghi nhớ kết quả
Khi xem xét mức của người chơi cực tiểu (nút MIN), hãy áp dụng thủ tục Minimax cho các nhánh con của nó và ghi nhớ kết quả nhỏ nhất.
Khi xem xét mức độ của người chơi cực đại (nút MAX), hãy áp dụng thủ tục Minimax cho các nhánh con của nó và ghi nhớ kết quả lớn nhất.
4.4.3 Ưu điểm và khuyết điểm của giải thuật MinMax: a Ưu điểm
Giải thuật Minimax cho phép tìm kiếm mọi nước đi tiếp theo và lựa chọn nước đi tốt nhất, nhờ vào tính chất vét cạn giúp không bỏ sót trạng thái Tuy nhiên, đối với các trò chơi có không gian trạng thái lớn như caro hay cờ tướng, việc chỉ áp dụng giải thuật này trở nên kém hiệu quả do sự bùng nổ tổ hợp quá lớn.
Giải thuật dựa trên nguyên lý vét cạn không tận dụng thông tin từ trạng thái hiện tại để quyết định nước đi, dẫn đến việc phải duyệt qua tất cả các trạng thái, gây tốn thời gian.
4.4.4 Giải thuật cắt tỉa Alpha-beta
Nút Max có giá trị alpha (tăng dần), trong khi nút Min có giá trị beta (giảm dần) Khi alpha và beta chưa được xác định, cần thực hiện tìm kiếm sâu (depth-first) để xác định các giá trị này và truyền ngược lên các nút cha.
Trong bài viết này, tôi sẽ thảo luận về khái niệm cắt tỉa alpha và cắt tỉa beta, đồng thời áp dụng một cách tiếp cận mới bằng cách sử dụng các khoảng trong toán học.
Hãy khảo sát cây trò chơi phía dưới để hình dung cách để cắt tỉa
Khi phân tích cây trò chơi từ trái sang phải, chúng ta nhận thấy rằng nút S có giá trị lớn nhất, tức là Max Theo chiến lược đã đề ra, giá trị alpha tại nút S sẽ lớn hơn hoặc bằng 10, cho phép chúng ta loại bỏ toàn bộ các nút con của C.
Tại nút C, được xác định là nút Min (trạng thái trò chơi dành cho Max), giá trị cần lấy là beta ≤ 3 Khi đã xác định được alpha và beta, chúng ta có thể dễ dàng quyết định việc cắt tỉa Tại nút S (Max), giá trị alpha luôn ≥ 10 (tăng dần), trong khi tại nút C (Min), giá trị luôn ≤ 3 (giảm dần), do đó không cần xem xét các nút con còn lại ở C.
Nếu theo khoảng thì hiện tại chúng ta chỉ nhận khoảng ≥ 10 tại nút gốc S, vậy thì đâu cần bận tâm đến việc khoảng ≤ 3 tại nút C
Hình 5.2 minh họa ví dụ về cắt tỉa alpha cho cây trung bình Trong quá trình này, chúng ta sẽ xét từ trái sang phải, bắt đầu từ nút gốc, ưu tiên duyệt nút con bên trái trước Duyệt toàn bộ cây có thể khá phức tạp, nhưng tôi sẽ trình bày các bước cần thiết để bạn dễ hiểu.
Xét duyệt từ trên gốc xuống sâu (vì ban đầu chưa hề tồn tại giá trị alpha hay beta của các nút)
Khi bắt đầu duyệt nút E, giá trị alpha đầu tiên là 2 (alpha ≥ 2) Do chưa có giá trị beta để so sánh, chúng ta sẽ tiếp tục duyệt con tiếp theo của nút E và chọn alpha = 3 (Max).
