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.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 Luan van 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 Luan van 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. 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 Luan van Đị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 <⌈n / 2⌉ - 1. Trên thực tế, chúng cho thấy ràng buộc này giữ cho trò chơi Maker-Breaker hoặc Breaker-Maker trong đó trong mỗi trường hợp, Maker đặt 1 và Breaker q miếng. Một biến thể cuối cùng là trò chơi Chooser-Picker. Trò chơi này hoạt động theo cách tương tự như sự thỏa hiệp kinh điển của một người cắt và người kia chọn.
Bộ chọn sẽ chọn hai vị trí và sau đó Bộ chọn sẽ chọn vị trí nào sẽ giữ vị trí còn lại với Bộ chọn. Trong phiên bản Chooser-Picker, Chooser đang chơi với tư cách là Maker trong khi ở Picker-Chooser, Chooser đóng vai trò là người phá vỡ. Những trò chơi như vậy được xem xét trên tờ giấy On On Chooser Picker, những trò chơi định vị, trong đó Csernenszky, Ma bùndity và Pluha miếng chứng minh trong số những điều khác mà khi chơi để Maker cố gắng hoàn thành một cơ sở của matroid , Picker thắng trò chơi Picker-Chooser nếu và chỉ khi tồn tại hai căn cứ rời rạc. Để biết thêm các biến thể trên Tic-Tac-Toe, chúng tôi khuyên dùng cuốn sách Beck về chủ đề này.
Biến thể chúng tôi sẽ giới thiệu trong Phần 1.4 khác với các biến thể trong đó trò chơi được chơi sử dụng quy tắc là một ví dụ về một trò chơi năng động như cờ đam hoặc cờ vua. 18 | P a g e Luan van 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 Luan van CHƯƠNG 3: CƠ SỞ LÝ THUYẾT 3.
Tic-Tac-Toe Trong phần này, chúng ta khám phá trò chơi Hop-Tic-Tac-Toe trong đó Xgi và Ogi chơi trên lưới chín ô vuông truyền thống của bảng Tic-Tac-Toe bằng cách sử dụng bước đánh mới được xác định trong Mục 1.4 thay vì phương pháp truyền thống đặt miếng. Hội đồng truyền thống thừa nhận cả hai quốc gia rút ra và gắn liền; tuy nhiên, chúng tôi cho thấy Xgi có thể giành được Hop-Tic-Tac-Toe chơi đầu tiên từ bất kỳ vị trí bắt đầu nào trong ba vị trí xuất phát khác nhau. Đó là, chúng tôi chứng minh rằng Xgi có chiến lược chiến thắng trong trò chơi vị trí hop được chơi trên bảng Tic-Tac-Toe truyền thống, mà chúng tôi gọi là Hop-Tic-Tac-Toe. Hãy nhớ lại rằng bảng Tic-Tac-Toe truyền thống có chín điểm và tám bộ thắng (đường thẳng) mỗi điểm ba điểm.
Trong số chín điểm, một điểm nằm trên bốn đường thẳng (giữa), bốn điểm nằm trên ba đường thẳng (các góc) và bốn điểm chỉ nằm trên hai đường thẳng (các cạnh).