Đề tài nghiên cứu khoa học: Nghiên cứu, thiết kế và chế tạo máy chơi game caro tự động dựa trên nền tảng trí tuệ nhân tạo

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:77

Thêm vào BST

Báo xấu

16
lượt xem 10
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Mục đích của đề tài là để chế tạo thành công máy chơi game caro tự động dựa trên nền tảng trí tuệ nhân tạo. Ngoài ra, người thực hiện đề tài này còn mong muốn tích lũy thêm kinh nghiệm thông qua việc sử dụng những kiến thức đã học để thiết kế và chế tạo một sản phẩm thực tế có tính ứng dụng cao.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Đề tài nghiên cứu khoa học: Nghiên cứu, thiết kế và chế tạo máy chơi game caro tự động dựa trên nền tảng trí tuệ nhân tạo

BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC SƯ PHẠM KỸ THUẬT THÀNH PHỐ HỒ CHÍ MINH CÔNG TRÌNH NGHIÊN CỨU KHOA HỌC CỦA SINH VIÊN NGHIÊN CỨU, THIẾT KẾ VÀ CHẾ TẠO MÁY CHƠI GAME CARO TỰ ĐỘNG DỰA TRÊN NỀN TẢNG TRÍ TUỆ NHÂN TẠO MÃ SỐ: SV2020-44 SKC 0 0 7 3 8 9 Tp. Hồ Chí Minh, tháng 08/2020
BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐH SƯ PHẠM KỸ THUẬT TPHCM BÁO CÁO TỔNG KẾT ĐỀ TÀI NGHIÊN CỨU KHOA HỌC CỦA SINH VIÊN NGHIÊN CỨU, THIẾT KẾ VÀ CHẾ TẠO MÁY CHƠI GAME CARO TỰ ĐỘNG DỰA TRÊN NỀN TẢNG TRÍ TUỆ NHÂN TẠO SV2020 - 44 Chủ nhiệm đề tài: Đỗ Phước Bảo Long TP Hồ Chí Minh, tháng 8 năm 2020 1|Page
BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐH SƯ PHẠM KỸ THUẬT TPHCM BÁO CÁO TỔNG KẾT ĐỀ TÀI NGHIÊN CỨU KHOA HỌC CỦA SINH VIÊN NGHIÊN CỨU, THIẾT KẾ VÀ CHẾ TẠO MÁY CHƠI GAME CARO TỰ ĐỘNG DỰA TRÊN NỀN TẢNG TRÍ TUỆ NHÂN TẠO SV2020 - 44 Thuộc nhóm ngành khoa học: SV thực hiện: Đỗ Phước Bảo Long Nam, Nữ: Nam Dân tộc: Kinh Lớp, khoa: 18461CL2B Năm thứ: 02 /Số năm đào tạo: 04 Ngành học: Công nghệ Kỹ Thuật Cơ Điện tử Người hướng dẫn: ThS. Nguyễn Văn Sơn TP Hồ Chí Minh, tháng 8 năm 2020 2|Page
MỤC LỤC MỤC LỤC ........................................................................................................................... 3 DANH MỤC BẢNG BIỂU ................................................................................................ 5 DANH MỤC NHỮNG TỪ VIẾT TẮT ............................................................................. 6 THÔNG TIN KẾT QUẢ NGHIÊN CỨU CỦA ĐỀ TÀI ................................................ 7 CHƯƠNG 1: GIỚI THIỆU ............................................................................................. 10 1.1. Tính cấp thiết của đề tài ........................................................................................ 10 1.2. Ý nghĩa khoa học và thực tiễn của đề tài .............................................................. 10 1.3. Mục tiêu nghiên cứu của đề tài ............................................................................. 10 1.4. Đối tượng và phạm vi nghiên cứu ........................................................................ 10 1.5. Phương pháp nghiên cứu ...................................................................................... 10 CHƯƠNG 2: TỔNG QUAN NGHIÊN CỨU ĐỀ TÀI .................................................. 12 2.1. Lịch sử ra đời game Tic-Tac-Toe ............................................................................ 12 2.2. Giới thiệu Tic-Tac-Toe ............................................................................................ 12 2.3 Biến thể trên Tic-Tac-Toe ......................................................................................... 15 CHƯƠNG 3: CƠ SỞ LÝ THUYẾT ................................................................................ 20 3.1. Tic-Tac-Toe............................................................................................................. 20 3.2. Chiến lược game Tic-Tac-Toe ................................................................................. 26 CHƯƠNG 4: NGUYÊN CỨU, TÍNH TOÁN, THIẾT KẾ TIC-TAC-TOE ............... 32 4.1 Bản chất mạch vi điều khiển – tự động hóa .............................................................. 32 4.2 Mạch điều khiển trung tâm ....................................................................................... 37 4.3 Cơ cấu servo .............................................................................................................. 39 4.4. Giải thuật cắt tỉa Alpha-beta .................................................................................... 44 3|Page
CHƯƠNG 5: CHẾ TẠO THỬ NGHIỆM – KẾT QUẢ - ĐÁNH GIÁ ........................ 50 5.1. Lưu đồ giải thuật ...................................................................................................... 50 5.2. Quy trình thực hiện .................................................................................................. 50 5.3. Phần điều khiển hoạt động ...................................................................................... 51 5.4. Mô hình máy thử nghiệm ......................................................................................... 51 KẾT LUẬN - ĐỀ NGHỊ ................................................................................................... 53 TÀI LIỆU THAM KHẢO................................................................................................ 54 PHỤ LỤC .......................................................................................................................... 55 4|Page
DANH MỤC BẢNG BIỂU 5|Page
DANH MỤC NHỮNG TỪ VIẾT TẮT (E, W) Bảng có điểm E và bộ thắng W AG(2, q) Mặt phẳng thứ tự q PG(2, q) Mặt phẳng chiếu của thứ tự q 6|Page
BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐH SƯ PHẠM KỸ THUẬT TPHCM THÔNG TIN KẾT QUẢ NGHIÊN CỨU CỦA ĐỀ TÀI 1. Thông tin chung: - Tên đề tài: Nghiên cứu, thiết kế và chế tạo máy chơi game caro tự động dựa trên nền tảng trí tuệ nhân tạo - Chủ nhiệm đề tài: Đỗ Phước Bảo Long Mã số SV: 18146158 - Lớp: 18146CL2B Khoa: Đào tạo chất lượng cao - Thành viên đề tài: Stt Họ và tên MSSV Lớp Khoa 1 Đỗ Phước Bảo Long 18146158 18146CL2B Đào tạo chất lượng cao 2 - Người hướng dẫn: ThS. Nguyễn Văn Sơn 2. Mục tiêu đề tài: Mục đích của đề tài này trước tiên là để chế tạo thành công máy chơi game caro tự động dựa trên nền tảng trí tuệ nhân tạo. Ngoài ra, người thực hiện đề tài này còn mong muốn tích lũy thêm kinh nghiệm thông qua việc sử dụng những kiến thức đã học để thiết kế và chế tạo một sản phẩm thực tế có tính ứng dụng cao. 3. Tính mới và sáng tạo: Thay vì phải ngồi trước các thiết bị thông minh để chơi tic-tac-toe ta có thể chơi với trạm tic-tac-toe này. Với cơ cấu đơn giản, người chơi có thể chọn từng nước đi chỉ với thao tác chạm vào ô mình muốn đi, động cơ sẽ hoạt động làm xoay khối cờ và xuất hiện nước mình đã chọn. Không chỉ là một trò chơi giải trí mà đây là một trò chơi giúp người chơi tư duy, tăng hoạt động của não bộ và cơ thể. 7|Page
4. Kết quả nghiên cứu: Cơ sở lý thuyết: tìm hiểu và nghiên cứu tính chất vật liệu để làm nền tảng cơ sở ứng dụng tạo ra sản phẩm Tính toán thiết kế khuôn: tính toán thiết kế khuôn dập Tính toán thiết kế máy ép: tính toán chọn xilanh ép thủy lực, tính thiết kế khung máy chịu lực, thiết kế hệ thống tự động hóa cho máy 5. Đóng góp về mặt giáo dục và đào tạo, kinh tế - xã hội, an ninh, quốc phòng và khả năng áp dụng của đề tài: Nghiên cứu thành công, thử nghiệm chạy ổn định, tương tác với người dùng tốt. Làm phong phú thêm kho tàng về tương tác trí tuệ nhân tạo, tìm hiểu những thông số, thuộc tính từ đó có thể làm tài liệu cho các nghiên cứu liên quan. 6. Công bố khoa học của SV từ kết quả nghiên cứu của đề tài (ghi rõ tên tạp chí nếu có) hoặc nhận xét, đánh giá của cơ sở đã áp dụng các kết quả nghiên cứu (nếu có): Ngày 20 tháng 08 năm 2020 SV chịu trách nhiệm chính thực hiện đề tài (kí, họ và tên) 8|Page
Nhận xét của người hướng dẫn về những đóng góp khoa học của SV thực hiện đề tài (phần này do người hướng dẫn ghi): Ngày 27 tháng 07 năm 2020 Người hướng dẫn (kí, họ và tên) 9|Page
CHƯƠNG 1: GIỚI THIỆU 1.1. Tính cấp thiết của đề tài Cùng với sự phát triển theo hướng công nghiệp hóa hiện đại hóa, cùng với sự phát triển của xu hướng công nghệ. Ngành kỹ thuật công nghệ trong nước đòi hỏi phải phát triển. Game Tic Tac Toe là một game trí tuệ không yêu cầu tốc độ, nên mỗi bước đi bạn hãy cân nhắc kỹ lưỡng để đi đúng vị trí không chỉ thuận lợi cho lượt chơi đó mà còn thuận lợi cho các bước đi sau đó. Thậm chí bước đi ở lượt này không có đem lại kết quả tức thì nhưng nó lại giúp ích rất nhiều cho bước đi sau đó của bạn, tạo tiền đề cho thắng lợi cuối cùng. Nhằm đáp ứng nhu cầu giải trí trong cuộc sống hằng ngày, trạm Tic Tac Toe sẽ nhanh chóng thấy thoải mái đầu óc. 1.2. Ý nghĩa khoa học và thực tiễn của đề tài Đáp ứng mục tiêu phát triển công nghệ hiện đại của đất nước. Đáp ứng nhu cầu trong cuộc sống hằng ngày của con người, cùng với dự án Smarthome. Trạm Tic Tac Toe sẽ đáp ứng đầy đủ những yêu cầu này. 1.3. 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. 1.4. Đối tượng và phạm vi nghiên cứu 1.4.1. Đối tượng nghiên cứu Trạm Tic Tac Toe. Tập trung chủ yếu vào việc tương tác giữa máy và người. 1.4.2. Phạm vi nghiên cứu Phát triển sản phẩm phục phục cho cuộc sống hằng ngày. Do thời gian làm đồ án có hạn, nên kết quả hoàn thành đồ án ở mức độ mô hình. 1.5. 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. 10 | P a g e
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. 11 | P a g e
CHƯƠNG 2: TỔNG QUAN NGHIÊN CỨU ĐỀ TÀI 2.1. Lịch sử ra đời game Tic-Tac-Toe Các trò chơi được chơi trên các bảng ba liên tiếp có thể được bắt nguồn từ Ai Cập cổ đại , nơi các bảng trò chơi như vậy đã được tìm thấy trên các tấm lợp có niên đại khoảng năm 1300 trước Công nguyên. Một biến thể ban đầu của Tic-Tac-Toe đã được chơi ở Đế chế La Mã , vào khoảng thế kỷ thứ nhất trước Công nguyên. Nó được gọi là terni lapilli ( ba viên sỏi cùng một lúc ) và thay vì có bất kỳ số mảnh nào, mỗi người chơi chỉ có ba, do đó họ phải di chuyển chúng đến những khoảng trống để tiếp tục chơi. Các dấu hiệu lưới của trò chơi đã được tìm thấy trên khắp Rome. Một trò chơi cổ xưa khác có liên quan chặt chẽ là ba morris của đàn ông cũng được chơi trên một lưới đơn giản và 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ác tên khác nhau của trò chơi là gần đây hơn. Tài liệu tham khảo đầu tiên về "noughts and cross" ( không phải là một từ thay thế cho số 0), tên tiếng Anh, xuất hiện vào năm 1858, trong một vấn đề về Ghi chú và Truy vấn . Tài liệu tham khảo in đầu tiên về một trò chơi gọi là "tick-tack-toe" xảy ra vào năm 1884, nhưng đề cập đến "một trò chơi của trẻ em chơi trên một phiến đá, bao gồm việc cố gắng nhắm mắt để đặt bút chì xuống một trong những số của một bộ, số trúng được ghi ". "Tic-Tac-Toe" cũng có thể bắt nguồn từ "tick-tack", tên của một phiên bản cũ của backgammon được mô tả lần đầu tiên vào năm 1558. Việc đổi tên của Hoa Kỳ thành "noughts and Cross" là "Tic-Tac-Toe" xảy ra trong Thế kỷ 20. Năm 1952, OXO (hay Noughts and Crosses ), được phát triển bởi nhà khoa học máy tính người Anh Sandy Douglas 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 được biết đến . Người chơi máy tính có thể chơi các trò chơi Tic-Tac-Toe hoàn hảo chống lại một đối thủ người. Năm 1975, Tic-Tac-Toe cũng được sử dụng bởi các sinh viên MIT để chứng minh sức mạnh tính toán của các yếu tố Tinkertoy . Máy tính Tinkertoy, được tạo ra (gần như) chỉ Tinkertoys, có thể chơi Tic-Tac-Toe một cách hoàn hảo. Nó hiện đang được trưng bày tại Bảo tàng Khoa học, Boston . 2.2. Giới thiệu Tic-Tac-Toe 12 | P a g e
Tic-Tac-Toe là trò chơi kết hợp không thể chia thành các trò chơi nhỏ hơn trong suốt quá trình chơi. Trò chơi này không nhất thiết phải kết thúc vì ai đó không thể chơi, mà là vì đã đạt được một cấu hình hoặc vị trí nhất định. Ví dụ: trò chơi Tic-Tac-Toe kết thúc do ai đó yêu cầu ba vị trí liên tiếp (một cấu hình chiến thắng cho người chơi đó) hoặc do bảng đầy và không có người chơi nào thắng (cấu hình được hòa). Các trò chơi giống như Tic- Tac-Toe cũng được gọi là các trò chơi theo vị trí và được xử lý chuyên sâu trong cuốn sách Trò chơi kết hợp: Lý thuyết Tic-Tac-Toe của Beck. Tic-Tac-Toe, cờ đam và cờ vua đều là những trò chơi kết hợp rơi vào các trò chơi vị trí phân loại phụ. Chính thức, một trò chơi vị trí yêu cầu như sau: một tập hợp hữu hạn E, các điểm hoặc vị trí của bảng và một số gia đình tùy ý W của các tập con của E được gọi là các bộ chiến thắng, được xác định trước khi bắt đầu trò chơi. Bảng trò chơi là tập hợp các điểm E cùng với bộ sưu tập W; nó sẽ được ký hiệu (E, W). Hai người chơi, người chơi thứ nhất và thứ hai, thay phiên nhau chiếm các điểm chưa được sử dụng hoặc mở của bảng. Để rõ ràng về ngôn ngữ, chúng tôi sẽ cho rằng trò chơi được chơi bởi hai người chơi Xgi và Ogi. Xgi sẽ luôn chơi đầu tiên; anh sẽ thay phiên nhau với Ogi. Bảng, cùng với các vị trí X và O bị chiếm bởi Xgi và Ogi tương ứng tại bất kỳ thời điểm nào trong trò chơi được gọi là trạng thái trò chơi. Trong bất kỳ hình nào, trừ khi có chỉ định khác, các vị trí chiếm giữ bởi Xgi sẽ được đánh dấu bởi X và những vị trí bị chiếm bởi Ogi bởi O. Người chơi đầu tiên chiếm được bộ chiến thắng A W sẽ thắng. Nếu bảng đầy (tất cả các vị trí đều bị chiếm dụng) và không người chơi nào chiếm được một bộ chiến thắng, thì trò chơi kết thúc với tỷ số hòa. Chúng tôi đề cập đến một trạng thái trò chơi như là một trạng thái rút ra. Một bảng (E, W) được cho là thừa nhận trạng thái rút ra nếu tồn tại phân vùng E thành X và O để mọi bộ thắng A ∈ W có ít nhất một điểm trong X và ít nhất một điểm trong O. Nếu a Hội đồng quản trị thừa nhận trạng thái rút thăm, điều đó không có nghĩa là một trò chơi trên bảng đó sẽ luôn kết thúc với tỷ số hòa, thay vào đó nó cho phép khả năng bốc thăm. Mặt khác, nếu một bảng không thừa nhận trạng thái rút ra, thì trò chơi phải kết thúc bằng một số người chơi chiến thắng. Trong lý thuyết trò chơi kết hợp, chiến lược là một thuật toán chọn bước di chuyển tiếp theo của người chơi dựa trên trạng thái hiện tại của trò chơi. Một chiến lược tối ưu cho người chơi là một chiến lược tạo ra một động thái cho mọi trạng thái trò chơi được đảm bảo để mang lại kết quả tốt nhất có thể cho người chơi đó. Trong một số trường hợp, một chiến lược tối ưu là một chiến lược 13 | P a g e
chiến thắng. Chiến lược giành chiến thắng cho Xgi là chiến lược mang lại chiến thắng cho anh ta khi đưa ra bất kỳ chuỗi di chuyển nào của Ogi. Một chiến lược không đặt ra trước mọi di chuyển trong trò chơi, thay vào đó, nó chọn bước di chuyển tiếp theo dựa trên chuỗi các bước di chuyển dẫn đến trạng thái trò chơi hiện tại. Trong lý thuyết trò chơi kết hợp, một câu hỏi ban đầu được đặt ra khi nghiên cứu một trò chơi cụ thể là: người chơi nào, nếu có, có lợi thế? Khi trả lời câu hỏi này, chúng tôi xác định cái được gọi là lớp kết quả của trò chơi. Về chiến lược trò chơi, chúng tôi muốn xác định chiến lược tối ưu nào tồn tại. Chúng tôi nói rằng một người chơi chơi tối ưu nếu anh ấy / cô ấy sử dụng chiến lược tối ưu của mình mà không có lỗi. Chúng ta nên lưu ý rằng sự tồn tại của một số chiến lược tối ưu ngăn chặn sự tồn tại của những chiến lược khác. Ví dụ: nếu Xgi có chiến lược chiến thắng, thì chơi tối ưu, anh ta được đảm bảo một chiến thắng. Điều này có nghĩa là Ogi có thể không có chiến lược hòa hay chiến lược hòa. Tương tự như vậy nếu Ogi có chiến lược chiến thắng và chơi tối ưu, thì Xgi không thể thắng, cũng không ép buộc. Mặt khác, nếu không có người chơi nào có chiến lược chiến thắng, thì cả hai người chơi đều phải có chiến lược hòa. Chúng ta cũng nên lưu ý rằng chỉ vì Xgi có chiến lược chiến thắng không có nghĩa là người chơi đầu tiên sẽ luôn giành chiến thắng. Nếu người chơi thứ nhất mắc lỗi hoặc không thực hiện chiến lược chiến thắng, thì trò chơi có thể kết thúc với tỷ số hòa hoặc với người chơi thứ hai chiến thắng, tuy nhiên trong trường hợp này, người chơi thứ nhất sẽ không chơi tối ưu. Chúng tôi sử dụng biểu thức người chơi đầu tiên giành chiến thắng để mô tả một trò chơi trong đó người chơi đầu tiên có chiến lược chiến thắng mà theo cách chơi tối ưu sẽ dẫn đến người chơi đầu tiên giành chiến thắng. Với một trò chơi vị trí được chơi tối ưu bởi cả hai người chơi, có ba kết quả có thể hiểu được của trò chơi: 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 người chơi có một chiến lược hòa. Tuy nhiên, hóa ra người chơi thứ hai thực sự không thể có chiến lược chiến thắng. Đó là, mặc dù người chơi thứ hai thỉnh thoảng chiến thắng tại Tic- Tac-Toe, không có chiến lược nào tồn tại mà có thể đảm bảo một kết quả như vậy chống lại một người chơi đầu tiên hoàn hảo. Điều này được chính thức hóa trong định lý sau, được chứng minh bằng cách sử dụng đối số đánh cắp chiến lược (xem ví dụ: [2]). Định lý 1.1.1. Trong một trò chơi định vị, Xgi luôn có thể ép ít nhất một trận hòa; nghĩa là, hoặc Xgi có chiến lược chiến thắng hoặc cả hai người chơi đều có chiến lược hòa. Bằng chứng. Giả sử 14 | P a g e
rằng Ogi có chiến lược chiến thắng S. Chúng tôi sẽ có được một mâu thuẫn bằng cách chứng minh làm thế nào Xgi có thể giành chiến thắng bằng cách ăn cắp S S. Trước tiên hãy để Xgi thực hiện một động thái tùy ý. Bỏ qua phần trò chơi này, Xgi sẽ giả vờ là người chơi thứ hai trong phần còn lại của trò chơi bằng cách thực hiện chiến lược S của Ogi. Nếu đến lượt mình, Xgi được S yêu cầu thực hiện một động thái vẫn khả dụng, thì anh ta nên làm như vậy. Nếu di chuyển được anh ta thực hiện như là động thái đầu tiên tùy ý của anh ta, thì anh ta nên thực hiện một động thái tùy ý khác. Vì bất kỳ động thái tùy ý nào của Xgi đều dẫn đến một vị trí nữa với X, nên một động thái như vậy chỉ có thể có lợi cho Xgi và do đó không làm thay đổi hiệu quả của chiến lược S. Theo sau đó, Xgi có thể giành chiến thắng bằng cách thực hiện chiến lược S bị đánh cắp. Điều này mâu thuẫn rằng S là một chiến lược chiến thắng cho Ogi chơi thứ hai vì cả hai người chơi đều không thể thắng. Do đó, những người làm Ogi không có chiến lược chiến thắng và ít nhất Xgi có thể buộc một trận hòa. Chúng ta nên lưu ý rằng, trong một trò chơi định vị, Xgi sẽ luôn có một nước đi đầu tiên có sẵn trừ khi bảng không có vị trí mở. Tuy nhiên, trong trường hợp hội đồng quản trị không có vị trí mở, Ogi không thể có chiến lược chiến thắng S, và chúng tôi sẽ nói rằng trò chơi kết thúc với tỷ số hòa. Đây là tình huống duy nhất mà Xgi sẽ không thể thực hiện một động thái mở đầu, vì các trò chơi vị trí của chúng tôi có cùng quy tắc chơi cho cả Xgi và Ogi. Đó là, không có bảng cho các trò chơi vị trí trong đó Xgi không có động thái mở đầu, nhưng Ogi thì có. Do người chơi thứ hai không thể có chiến lược chiến thắng, Ogi giỏi nhất có thể làm là có chiến lược hòa để ngăn Xgi có chiến lược chiến thắng. Do đó, việc xác định lớp kết quả của một trò chơi định vị được giảm xuống để trả lời câu hỏi của Xgi có chiến lược chiến thắng không? Một lần nữa, nếu anh ta làm, chúng tôi đề cập đến trò chơi như một người chơi đầu tiên giành chiến thắng trò chơi. Nếu Xgi không có chiến lược chiến thắng, thì cả hai người chơi đều có chiến lược hòa. Vì đây là kết quả tốt nhất có thể có cho Ogi, chúng tôi đề cập đến những trò chơi như trò chơi hòa người chơi thứ hai. 2.3 Biến thể trên Tic-Tac-Toe Trong khi các trò chơi như cờ đam và cờ vua là ví dụ mẫu của các trò chơi định vị, phần lớn nghiên cứu về lĩnh vực này thực sự liên quan đến các biến thể trên Tic-Tac-Toe do sự phức tạp của các trò chơi khác này. Tic-Tac-Toe là ví dụ về trò chơi tĩnh. Mặt khác, 15 | P a g e
cờ đam và cờ vua, là những ví dụ về các trò chơi năng động, trong đó các quân cờ có thể được di dời hoặc gỡ bỏ khỏi bàn cờ. Sự đơn giản tương đối của Tic-Tac-Toe làm cho nó trở thành một ứng cử viên lý tưởng cho yêu cầu toán học. Trong phần này, chúng tôi tìm hiểu ngắn gọn về một số biến thể trên Tic-Tac-Toe trước khi chúng tôi chuyển sang các biến thể cụ thể là trọng tâm của luận án này. Trong tất cả các biến thể được thảo luận trong phần này, hai người chơi thay phiên nhau đặt các mảnh ở các vị trí mở, đó là chơi trò chơi định vị tĩnh hoặc truyền thống của Tic-Tac-Toe. Như đã nói ở trên, mục tiêu trong một trò chơi giống như Tic-Tac-Toe là chiếm một bộ chiến thắng trước tiên. Một chiến thắng theo các quy tắc này cũng được gọi là một chiến thắng mạnh mẽ. Nói chung xác định làm thế nào để tạo ra một chiến thắng mạnh mẽ là khó. Ví dụ, trò chơi Tic-Tac-Toe 4 × 4 × 4 được biết đến là người chơi đầu tiên giành chiến thắng, nhưng chiến lược chiến thắng là vô cùng phức tạp, đòi hỏi phải có bằng chứng hỗ trợ của máy tính. Trò chơi 5 × 5 × 5 dự kiến sẽ là một trận hòa, nhưng thuật toán quay lại bước 3125 cần thiết để chứng minh rằng nó có thể tính toán được để thử. Biến thể đầu tiên và phổ biến nhất cần xem xét là trò chơi Maker- Breaker, loại bỏ yêu cầu phải giành chiến thắng trước. Thay vào đó, trong phiên bản này, người chơi đầu tiên, Maker, cố gắng hoàn thành một bộ chiến thắng trong khi người chơi thứ hai, Breaker, cố gắng ngăn chặn nó. Trong trò chơi giành chiến thắng mạnh, cả hai người chơi phải ‘xây dựng và chặn block cùng lúc. Trong trò chơi Maker-Breaker, hai công việc là riêng biệt, giúp cho việc phân tích có phần dễ dàng hơn. Trong các trò chơi Maker- Breaker không giống như các trò chơi mạnh, ai đó luôn chiến thắng: nhà sản xuất nếu anh ta hoàn thành bộ thắng và bộ ngắt nếu không. Đối với một số trò chơi, việc thay đổi thành phiên bản Maker-Breaker hoàn toàn không giúp ích gì. Ví dụ, trong trò chơi Hex, mỗi người chơi đang cố gắng tạo một đường dẫn được kết nối từ một phía của bảng sang phía đối diện. Cách duy nhất để ngăn chặn đối thủ của bạn giành chiến thắng là chiến thắng chính mình vì không có bảng Hex nào thừa nhận một trận hòa. Do đó, chiến lược cho mỗi người chơi vẫn là giành chiến thắng, ngay cả trong trường hợp Maker-Breaker. Tuy nhiên, có một số trường hợp chơi theo quy tắc Maker-Breaker sẽ hỗ trợ phân tích. Ví dụ, người ta có thể kiểm tra xem khi chơi Tic-Tac-Toe theo quy tắc Maker-Breaker, bằng cách không phải chặn người chơi thứ hai, người chơi thứ nhất thực sự có thể giành chiến thắng. Khả năng 16 | 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ụ về trò chơi Maker-Breaker. Trò chơi được chơi trên các cạnh của đồ thị với mục tiêu Maker Maker là tạo ra một đường dẫn kết nối hai đỉnh khác biệt của đồ thị. Breaker có thể ngăn chặn một chiến thắng bằng cách hoàn thành một vết cắt tách các đỉnh. Trong Trò chơi Giải pháp của Trò chơi Chuyển đổi Shannon, Lehman [11] đã chứng minh rằng Maker có chiến lược chiến thắng khi chơi trên các cạnh của đồ thị hoàn chỉnh khi cố gắng hoàn thành một cây bao trùm (do đó tạo ra một đường giữa hai đỉnh bất kỳ). Anh ta cũng chứng minh các điều kiện cần thiết trên biểu đồ chung để Breaker có 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ả có thể đạ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 được sửa đổi. Ví dụ, hãy xem xét một trò chơi Tic-Tac-Toe được chơi trên mạng số nguyên d chiều trong đó một bộ chiến thắng là tập hợp m điểm liên tiếp trên một dòng. Trong 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 với nhiều hướng dẫn Kruczek và Sundberg [10] đã xác định một giới hạn về kích thước của một bộ chiến thắng để Breaker giành chiến thắng nếu các hướng chiến thắng được cho phép có giới hạn. Các đối số trong bài viết dựa trên sự sửa đổi của phương pháp xác suất được phát triển đầu tiên bởi Erdo¨s và Selfridge [9] và sau đó được sửa đổi bởi Beck [2]. Các biến thể khác của Tic-Tac-Toe được chơi trên biểu đồ liên quan đến việc thay đổi cấu trúc bộ chiến thắng. Ví dụ: trong tờ giấy Một ngưỡng sắc nét cho trò chơi Hamilton Chu kỳ MakerBreaker, xông Hefetz et. al. khám phá một trò chơi Maker-Breaker được chơi trên các biểu đồ ngẫu nhiên. Ý tưởng là đưa ra một biểu đồ ngẫu nhiên G (n, p) với n đỉnh trong đó mỗi cạnh được bao gồm độc lập với xác suất p, hai người chơi chơi trên các cạnh của biểu đồ với Maker đang cố gắng hoàn thành Chu kỳ Hamilton. Các kết quả của bài viết này dựa trên các kết quả trước đó cho thấy rằng đối với p su lớn tương đối với n, một đồ thị ngẫu nhiên G (n, p) gần như chắc chắn là Hamilton. Kết quả chính từ bài báo này là như sau. 17 | P a g e
Định lý 1.2.1 ( Định lý 1). Tồn tại một hằng số l> 0 sao cho trò chơi chu trình Hamilton trên G (n, log n + (log log n) l) gần như chắc chắn là một chiến thắng của Maker. Chúng ta nên lưu ý rằng các chiến lược được phát triển khi sử dụng phương pháp xác suất là xác định. Bản chất xác suất là sự tồn tại của hội đồng quản trị, không phải chiến lược. Một khi một bảng như vậy tồn tại, chiến lược sẽ quyết định kết quả của trò chơi. Các biến thể khác bao gồm trò chơi thiên vị trong đó hai người chơi được phép đặt số lượng quân cờ khác nhau trên bảng. Ví dụ: một trò chơi có thể được chơi trong đó Maker được phép đặt 1 mảnh và Breaker q mảnh. Mục tiêu của loại phân tích này là xác định giá trị ngưỡng của q tại đó trò chơi chuyển từ Maker win sang Breaker win. Ví dụ, trong bài viết Các trò chơi vị trí thiên vị trên giấy trên Matroids leo Bednarska và Pikhurko chơi một trò chơi như vậy trong đó mục tiêu của Makers là yêu cầu một mạch của matroid. Trong bài báo, họ 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 đã cho. Ví dụ: nếu một người chơi trên matroid chu kỳ của đồ thị hoàn chỉnh Kn, thì Maker thắng trò chơi cho tất cả q
Chúng tôi sẽ kiểm tra phiên bản thắng mạnh của trò chơi nơi cả hai người chơi cố gắng giành chiến thắng trước. Chúng ta không nên sửa đổi trò chơi thành trò chơi Maker-Breaker, nhưng không có phân tích nào như vậy được đưa vào luận án này. 19 | P a g e