Đồ án nghiên cứu về lý thuyết trò chơi và ứng dụng trong trò chơi caro

  • 37 trang
  • file .pdf
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ TP.HCM
KHOA CÔNG NGHỆ THÔNG TIN
ĐỒ ÁN HỌC PHẦN
TRÍ TUỆ NHÂN TẠO
NGHIÊN CỨU VỀ LÝ THUYẾT TRÒ CHƠI
VÀ ỨNG DỤNG TRONG TRÒ CHƠI CARO
Nghành: CÔNG NGHỆ THÔNG TIN
Giảng viên hướng dẫn: Nguyễn Văn Cẩn
Sinh viên thực hiện:
1. Cao Minh Thắng MSSV: 1811060714 Lớp: 18DTHE3
2. Nguyễn Duy Kha MSSV: 1811061922 Lớp: 18DTHE3
3. Mai Tùng Long MSSV: 1811061512 Lớp: 18DTHE3
4. Phạm Thái Tài MSSV: 1811061542 Lớp: 18DTHE3
Thành phố Hồ Chí Minh
LỜI NHẬN XÉT CỦA GIẢNG VIÊN
...………………………………………………………………………………………………...
...………………………………………………………………………………………………...
...………………………………………………………………………………………………...
...………………………………………………………………………………………………...
...………………………………………………………………………………………………...
...………………………………………………………………………………………………...
...………………………………………………………………………………………………...
...………………………………………………………………………………………………...
...………………………………………………………………………………………………...
...………………………………………………………………………………………………...
...………………………………………………………………………………………………...
...………………………………………………………………………………………………...
...………………………………………………………………………………………………...
...………………………………………………………………………………………………...
...………………………………………………………………………………………………...
...………………………………………………………………………………………………...
...………………………………………………………………………………………………...
...………………………………………………………………………………………………...
...………………………………………………………………………………………………...
...………………………………………………………………………………………………...
Trang 1/37
MỤC LỤC
LỜI NHẬN XÉT CỦA GIẢNG VIÊN ............................................................... 1
LỜI MỞ ĐẦU .................................................................................................... 4
1. Đề tài nghiên cứu: ...................................................................................... 4
2. Mục tiêu nghiên cứu: .................................................................................. 4
3. Đối tượng nghiên cứu: ................................................................................ 4
4. Nhiệm vụ nghiên cứu: ................................................................................ 4
5. Phạm vi nghiên cứu: ................................................................................... 5
6. Phương pháp nghiên cứu: ........................................................................... 5
7. Nội dung nghiên cứu: ................................................................................. 5
CHƯƠNG 1: TÌM HIỂU CƠ BẢN VỀ LÝ THUYẾT TRÒ CHƠI .................... 6
1. Lý thuyết trò chơi là gì?.............................................................................. 6
2. Lịch sử của ngành Lý thuyết trò chơi: ........................................................ 7
3. Biểu diễn trò chơi: ...................................................................................... 8
3.1 Dạng chuẩn tắc: .................................................................................... 8
3.2 Dạng mở rộng:...................................................................................... 9
4. Các loại trò chơi: ........................................................................................ 9
4.1 Trò chơi đối xứng: ................................................................................ 9
4.2 Trò chơi tổng bằng không và tổng khác không: .................................. 10
4.3 Trò chơi đồng thời và trò chơi tuần tự: ............................................... 10
4.4 Trò chơi thông tin hoàn hảo và không hoàn hảo: ................................ 11
4.5 Các trò chơi dài vô tận: ....................................................................... 11
5. Ứng dụng của lý thuyết trò chơi: .............................................................. 12
5.1 Kinh tế và kinh doanh: ........................................................................ 12
5.2 Sinh học: ............................................................................................ 14
5.3 Khoa học máy tính và logic: ............................................................... 15
5.4 Chính trị học: ...................................................................................... 15
5.5 Triết học: ............................................................................................ 15
CHƯƠNG 2: ỨNG DỤNG TRONG TRÒ CHƠI CARO ................................. 17
1. Giới thiệu về trí tuệ nhân tạo: ................................................................... 17
2. Giải quyết vấn đề bằng tìm kiếm: ............................................................. 18
3. Giải quyết bài toán: .................................................................................. 19
3.1 Giới thiệu trò chơi: ............................................................................. 19
3.2 Phân tích bài toán: .............................................................................. 21
3.3 Biểu diễn bài toán dưới dạng cây trò chơi (Game Tree): ..................... 21
3.4 Chiến lược tìm kiếm: .......................................................................... 23
Trang 2/37
3.5 Sử dụng thuật toán vén cạn: ................................................................ 23
3.6 Không gian tìm kiếm nước đi và chiến lược tìm kiếm: ....................... 24
4. Thuật toán: ............................................................................................... 24
4.1 Thuật toán MinMax: ........................................................................... 24
4.2 Thuật toán cắt tỉa Alpha-Beta: ............................................................ 28
5. Giao diện sản phẩm: ................................................................................. 31
CHƯƠNG 3: KẾT LUẬN ................................................................................ 35
CHƯƠNG 4: TÀI LIỆU THAM KHẢO .......................................................... 36
Trang 3/37
LỜI MỞ ĐẦU
1. Đề tài nghiên cứu:
Lý thuyết trò chơi là một lĩnh vực có nhiều ứng dụng trong thực tiễn. Ngành
này nghiên cứu các tình huống chiến thuật trong đó các đối thủ lựa chọn các hành
động khác nhau để cố gắng làm tối đa kết quả nhận được. Ban đầu được phát triển
như là một công cụ để nghiên cứu hành vi kinh tế học, ngày nay Lý thuyết trò
chơi được sử dụng trong nhiều ngành khoa học, từ Sinh học tới Triết học. Đặc
biệt, Lý thuyết trò chơi được phát triển mạnh mẽ cùng với sự phát triển của trí tuệ
nhân tạo và ứng dụng của trí tuệ nhân tạo trong việc chế tạo robots. Từ những ứng
dụng tiềm năng của lý thuyết trò chơi và sự đam mê tìm hiểu kiến thức cũng như
nhằm nâng cao kiến thức và kỹ năng lập trình, nhóm sinh viên chúng em đã chọn
đề tài tìm hiểu về lý thuyết trò chơi và ứng dụng trong trò chơi caro.
2. Mục tiêu nghiên cứu:
- Làm quen với phương pháp nghiên cứu khoa học, làm việc nhóm.
- Nâng cao hiểu biết và mở rộng kiến thức.
- Rèn luyện kỹ năng lập trình và khả năng áp dụng kiến thức vào giải quyết bài
toán thực tế.
3. Đối tượng nghiên cứu:
- Cơbản về lý thuyết trò chơi.
- Một số giải thuật tìm kiếm trong trí tuệ nhân tạo.
- Ngôn ngữ lập trình C-sharp.
4. Nhiệm vụ nghiên cứu:
- Tìm hiểu Cơbản về lý thuyết trò chơi.
- Tìm hiểu một số giải thuật tìm kiếm trong trí tuệ nhân tạo.
- Tìm hiểu ngôn ngữ lập trình C-sharp.
- Cài đặt chương trình thử nghiệm.
Trang 4/37
5. Phạm vi nghiên cứu:
- Tìm hiểu Cơbản về lý thuyết trò chơi: Lịch sử của lý thuyết trò chơi, cách
biểu diễn, phân loại trò chơi, các ứng dụng của lý thuyết trò chơi.
- Tìm hiểu một số giải thuật tìm kiếm trong trí tuệ nhân tạo: Tìm kiếm có đối
thủ, tìm kiếm tối ưu.
- Ngôn ngữ lập trình C-sharp.
- Cài đặt chương trình cờ caro giữa người và máy tính sử dụng giải thuật Mini-
Max và giải thuật tìm kiếm AlphaBeta.
6. Phương pháp nghiên cứu:
- Tham khảo tài liệu của thầy cô, trên mạng.
- Tham khảo ý kiến bạn bè, thầy cô.
- Cài đặt chương trình thử nghiệm.
7. Nội dung nghiên cứu:
- Lý thuyết cơbản về trò chơi.
- Ứng dụng trong trò chơi Caro.
Trang 5/37
CHƯƠNG 1: TÌM HIỂU CƠ BẢN VỀ LÝ THUYẾT TRÒ CHƠI
1. Lý thuyết trò chơi là gì?
Lý thuyết trò chơi là một nhánh của Toán học ứng dụng. Ngành này nghiên
cứu các tình huống chiến thuật trong đó các đối thủ lựa chọn các hành động khác
nhau để cố gắng làm tối đa kết quả nhận được. Ban đầu được phát triển như là
một công cụ để nghiên cứu hành vi kinh tế học, ngày nay Lý thuyết trò chơi được
sử dụng trong nhiều ngành khoa học, từ Sinh học tới Triết học. Lý thuyết trò chơi
đã có sự phát triển lớn từ khi John von Neumann là người đầu tiên hình thức hóa
nó trong thời kỳ trước và trong Chiến tranh Lạnh, chủ yếu do áp dụng của nó trong
chiến lược quân sự, nổi tiếng nhất là khái niệm đảm bảo phá hủy lẫn nhau (mutual
assured destruction). Bắt đầu từ những năm 1970, Lý thuyết trò chơi bắt đầu được
áp dụng cho nghiên cứu về hành vi động vật, trong đó có sự phát triển của các loài
qua chọn lọc tự nhiên. Do các trò chơi hay như Song đề tù nhân (prisoner's
dilemma), trong đó lợi ích cá nhân làm hại cho tất cả mọi người, Lý thuyết trò
chơi đã bắt đầu được dùng trong Chính trị học, Đạo đức học và triết học. Cuối
cùng, Lý thuyết trò chơi gần đây đã thu hút được sự chú ý của các nhà Khoa học
máy tính do ứng dụng của nó trong Trí tuệ nhân tạo và Điều khiển học.
Bên cạnh các mối quan tâm có tính chất hàm lâm, lý thuyết trò chơi đã nhận
được sự chú ý trong văn hóa đại chúng. John Nash, một nhà lý thuyết trò chơi,
người đã nhận được giải thưởng Nobel, đã là chủ đề trong cuốn hồi ký năm 1998
của tác giả Sylvia Nasar và trong bộ phim Một tâm hồn đẹp (A Beautiful Mind)
năm 2001. Một số trò chơi truyền hình (game show) đã sử dụng các tính huống
của lý thuyết trò chơi, trong đó có Friend or Foe? và Survivor.
Tuy tương tự với Lý thuyết quyết định, nhưng Lý thuyết trò chơi nghiên cứu
các quyết định được đưa ra trong một môi trường trong đó các đối thủ tương tác
với nhau. Nói cách khác, Lý thuyết trò chơi nghiên cứu cách lựa chọn hành vi tối
ưu khi chi phí và lợi ích của mỗi lựa chọn là không cố định mà phụ thuộc vào lựa
chọn của các cá nhân khác.
Trang 6/37
2. Lịch sử củangành Lý thuyết trò chơi:
Những thảo luận đầu tiên được biết đến về lý thuyết trò chơi xuất hiện trong
một lá thư viết bởi James Waldegrave vào năm 1713. Trong lá thư này,
Waldegrave đưa ra lời giải chiến thuật hỗn hợp minimax cho một trò đánh bài hai
người chơi Le Her. Chỉ đến khi sự xuất bản Nghiên cứu về những Định luật toán
học của lý thuyết Tài sản của Antoine Augustin Cournot vào năm 1838 thì những
phân tích chung về lý thuyết trò chơi mới được theo đuổi. Trong tác phẩm này
Cournot xem xét duopoly và đưa một một phiên bản giới hạn của cân bằng Nash.
Mặc dù những phân tích của Cournot là tổng quát hơn là của Waldegrave, lý
thuyết trò chơi chưa thật sự tồn tại như là một ngành duy nhất cho đến khi John
von Neumann xuất bản một loạt các bài báo vào năm 1928. Những kết quả này
sau này được mở rộng thêm ra trong cuốn sách xuất bản năm 1944 Lý thuyết trò
chơi và các hành vi kinh tế bởi von Neumann và Oskar Morgenstern. Tác phẩm
uyên thâm này chứa đựng phương pháp tìm những lời giải tối ưu cho những trò
chơi tổng bằng không với hai người chơi. Trong suốt khoảng thời gian này, những
tác phẩm về lý thuyết trò chơi chủ yếu tập trung vào lý thuyết các trò chơi hợp
tác, phân tích về những chiến thuật tối ưu cho một nhóm các cá nhân, giả sử rằng
họ có thể bảo đảm những thỏa thuận giữ họ với những chiến thuật thích hợp.
Vào năm 1950, thảo luận đầu tiên của Prisoner's dilemma xuất hiện, và một thí
nghiệm được làm về trò chơi này tại công ty RAND. Vào khoảng cùng thời gian
đó, John Nash phát triển một định nghĩa về một chiến thuật "tối ưu" cho các trò
chơi với nhiều người chơi, và chưa một tối ưu nào được định nghĩa trước đó, được
biết đến như là cân bằng Nash. Cân bằng này là đủ tổng quát, cho phép sự phân
tích về trò chơi không hợp tác thêm vào những trò chơi có hợp tác.
Lý thuyết trò chơi trải qua một thời gian sôi động trong những năm 1950, trong
những năm đó những khái niệm về cốt lõi, dạng trò chơi bao quát, trò chơi giả,
trò chơi lặp, và giá trị Shapley được phát triển. Thêm vào đó, những ứng dụng đầu
Trang 7/37
tiên của lý thuyết trò chơi vào triết học và khoa học chính trị diễn ra trong thời
gian này.
Vào năm 1965, Reinhard Selten giới thiệu khái niệm lời giải của các cân bằng
lý tưởng của các trò chơi con, làm chính xác thêm cân bằng Nash equilibrium (sau
đó cũng ông giới thiệu sự hoàn thiện rung tay). Vào năm 1967, John Harsanyi
phát triển các khái niệm thông tin hoàn toàn và trò chơi Bayesian. Ông ta, cùng
với John Nash và Reinhard Selten, đoạt giải thưởng Nobel về kinh tế vào năm
1994.
Trong những năm 1970, lý thuyết trò chơi được áp dụng rộng rãi vào sinh học,
chủ yếu là do kết quả của các công trình của John Maynard Smith và chiến lược
tiến hóa bền vững của ông. Thêm vào đó, những khái niệm về cân bằng liên quan,
sự hoàn toàn rung tay, và kiến thức chung được giới thiệu và phân tích.
Vào năm 2005, những lý thuyết gia trò chơi Thomas Schelling và Robert
Aumann đoạt giải thưởng Nobel về kinh tế. Schelling là về các mô hình động, các
ví dụ ban đầu của lý thuyết tiến hóa trò chơi. Aumann đóng góp thêm vào trường
cân bằng (equilibrium school), phát triển một cân bằng làm thô đi những cân bằng
liên quan nhau và phát triển các phân tích chi tiết về giả sử của kiến thức chung.
3. Biểu diễn trò chơi:
3.1 Dạng chuẩn tắc:
Trò chơi chuẩn tắc (hoặc dạng chiến lược (strategic form)) là một ma trận cho
biết thông tin về các đấu thủ, chiến lược, và cơchế thưởng phạt. Trong ví dụ, có
hai đấu thủ, một người chọn hàng, người kia chọn cột. Mỗi đấu thủ có hai chiến
lược, mỗi chiến lược được biểu diễn bởi một ô được xác định bởi số hiệu hàng và
số hiệu cột của nó. Mức thưởng phạt được ghi trong ô đó. Giá trị thứ nhất là mức
thưởng phạt cho đấu thủ chơi theo hàng (trong ví dụ là Đấu thủ 1); giá trị thứ hai
là mức thưởng phạt cho đấu thủ chơi theo cột (trong ví dụ là Đấu thủ 2). Giả sử
Trang 8/37
Đấu thủ 1 chơi hàng trên và Đấu thủ 2 chơi cột trái. Khi đó, Đấu thủ 1 nhận 4
điểm và Đấu thủ 2 nhận 3 điểm.
Khi một trò chơi được biểu diễn bằng dạng chuẩn tắc, người ta coi rằng mỗi
đấu thủ hành động một cách đồng thời, hoặc ít nhất không biết về hành động của
người kia. Nếu các đấu thủ có thông tin về lựa chọn của các đấu thủ khác, trò chơi
thường được biểu diễn bằng dạng mở rộng.
3.2 Dạng mở rộng:
Các trò chơi dạng mở rộng cố gắng mô tả các trò chơi có thứ tự quan trọng. Ở
đây, các trò chơi được biểu diễn bằng cây. Mỗi đỉnh (hoặc nút) biểu diễn một
điểm mà người chơi có thể lựa chọn. Người chơi được chỉ rõ bằng một số ghi cạnh
đỉnh. Các đoạn thẳng đi ra từ đỉnh đó biểu diễn các hành động có thể cho người
chơi đó. Mức thưởng phạt được ghi rõ tại đáy cây.
Các trò chơi mở rộng còn có thể mô tả các trò chơi đi đồng thời. Hoặc có một
đường chấm chấm hoặc một đường tròn vẽ quanh hai đỉnh khác nhau để biểu diễn
rằng chúng đều thuộc cùng một tập hợp thông tin (nghĩa là, người chơi không biết
họ đang ở điểm nào).
4. Các loại trò chơi:
4.1 Trò chơi đối xứng:
Một trò chơi đối xứng là một trò chơi mà phần lợi cho việc chơi một chiến
thuật nào đó chỉ phụ thuộc vào các chiến thuật được sử dụng, chứ không phụ thuộc
vào người nào đang chơi. Nếu như danh tính của những người chơi có thể thay
đổi mà không làm thay đổi phần lợi đối với chiến thuật chơi, thì một trò chơi là
đối xứng. Nhiều trò chơi 2×2 thường được nghiên cứu là đối xứng. Những biểu
diễn chuẩn của trò chơi con gà, song đề tù nhân, đi săn nai là những trò chơi đối
xứng.
Trang 9/37
Đa số những trò chơi bất đối xứng được nghiên cứu là những trò chơi mà các
tập hợp chiến thuật khác nhau được sử dụng bởi hai người chơi. Chẳng hạn, trò
chơi tối hậu thư và tương tự như vậy trò nhà độc tài có chiến thuật khác nhau cho
mỗi người chơi. Tuy vậy, có thể xảy ra trường hợp một trò chơi có những chiến
thuật giống nhau cho cả hai người chơi, nhưng vẫn bất đối xứng. Chẳng hạn, trò
chơi được minh họa bên phải là bất đối xứng mặc dù cho có cùng tập các chiến
thuật cho cả 2 người chơi.
4.2 Trò chơi tổng bằng không và tổng khác không:
Trong trò chơi tổng bằng không, với mọi tổ hợp của các chiến lược chơi, tổng
điểm của tất cả các người chơi trong ván chơi luôn bằng 0. Nói một cách không
chính thức, đấu thủ này hưởng lợi trên thiệt hại của các đấu thủ khác. Một ví dụ
là trò Poker, trong đó người này thắng số điểm bằng đúng số điểm mà người kia
thua. Các loại cờ cổ điển như cờ vây, cờ vua và cờ tướng cũng là các trò chơi tổng
bằng không. Nhiều trò chơi mà các nhà lý thuyết trò chơi nghiên cứu, trong đó có
song đề tù nhân nổi tiếng, là các trò chơi tổng khác không, do có một số kết cục
có tổng kết quả lớn hơn hoặc nhỏ hơn không. Nói một cách không chính thức,
trong các trò chơi tổng khác không, một thu hoạch của đấu thủ này không nhất
thiết tương ứng với một thiệt hại của một đấu thủ khác. Có thể biến đổi một trò
chơi bất kỳ thành một trò chơi tổng bằng không bằng cách bổ sung một đấu thủ
"bù nhìn" sao cho các thiệt hại của đấu thủ này bù lại tổng thu hoạch của các đấu
thủ khác.
4.3 Trò chơi đồng thời và trò chơi tuần tự:
Trong các trò chơi đồng thời (simultaneous game), cả hai đấu thủ thực hiện
các nước đi một cách đồng thời, hoặc nếu không thì đấu thủ này sẽ không biết về
các hành động trước đó của các đối thủ khác (và như vậy cũng tạo "hiệu ứng"
đồng thời). Trong các trò chơi tuần tự (sequential game), người đi sau có biết một
số (nhưng không nhất thiết toàn bộ) thông tin về các nước đi trước.
Trang 10/37
Biểu diễn dạng chuẩn tắc được dùng để biểu diễn các trò chơi đồng thời, còn
Biểu diễn dạng mở rộng được dùng cho các trò chơi tuần tự.
4.4 Trò chơi thông tin hoàn hảovà không hoàn hảo:
Các trò chơi thông tin hoàn hảo (games of perfect information) lập thành một
tập con quan trọng của các trò chơi tuần tự. Một trò chơi được gọi là có thông tin
hoàn hảo nếu mọi đấu thủ biết tất cả các nước đi mà tất cả các đấu thủ khác đã
thực hiện. Do vậy chỉ có các trò chơi tuần tự mới có thể là các trò chơi thông tin
hoàn hảo. Hầu hết các trò chơi được nghiên cứu trong lý thuyết trò chơi là các trò
chơi thông tin không hoàn hảo, tuy một số trò chơi hay như cờ vây, cờ vua lại là
trò chơi thông tin hoàn hảo.
Tính chất thông tin hoàn hảo thường bị nhầm lẫn với khái niệm thông tin đầy
đủ. Tính chất thông tin đầy đủ đòi hỏi rằng mỗi người chơi biết về các chiến lược
và thành quả thu được của các người chơi khác, nhưng không nhất thiết biết về
các hành động của họ.
4.5 Các trò chơi dài vô tận:
Bởi các lý do hiển nhiên, các trò chơi được nghiên cứu bởi các kinh tế gia và
những người chơi trong thế giới thực nhìn chung là kết thúc trò chơi trong hữu
hạn các bước đi. Các nhà toán học lý thuyết không bị cản trở bởi điều đó, và lý
thuyết gia về tập hợp đặc biệt nghiên cứu về các trò chơi kết thúc sau vô hạn các
bước đi, bới người thắng (hay là phần lợi) là không biết được cho đến sau khi các
bước đi đó đã hoàn thành.
Sự chú ý thường không phải là quá nhiều về cách nào tốt nhất để chơi trò chơi,
mà đơn giản là chỉ phụ thuộc vào người chơi hay người kia có hay không một
chiến thuật chiến thắng. (Có thể chứng minh rằng, sử dụng tiên đề chọn lựa, là có
những trò chơi với ngay cả là đầy đủ thông tin hoàn toàn, và chỉ có kết quả là
"thắng" hay "thua" và không người chơi nào có chiến thuật để chiến thắng). Sự
Trang 11/37
tồn tại của những chiến thuật như vậy, cho những trò chơi được thiết kế một cách
thông minh, có những kết quả quan trọng trong lý thuyết miêu tả tập hợp.
5. Ứng dụng củalý thuyết trò chơi:
Các trò chơi trong dạng này hay dạng khác được sử dụng rộng rãi trong nhiều
ngành nghiên cứu khác nhau.
5.1 Kinh tế và kinh doanh:
Các nhà kinh tế học đã sử dụng lý thuyết trò chơi để phân tích một diện rộng
các hiện tượng kinh tế, trong đó có đấu giá, mặc cả, duopoly và oligopoly, các tổ
chức mạng lưới xã hội và các hệ thống bầu cử. Nghiên cứu này thường tập trung
vào một tập cụ thể các chiến lược được biết với tên các trạng thái cân bằng trong
trò chơi. Nổi tiếng nhất là cân bằng Nash của nhà toán học John Nash, người đã
được giải thưởng Nobel cho công trình nghiên cứu của ông về lý thuyết trò chơi.
Công dụng đầu tiên là để cung cấp thông tin cho chúng ta về việc là toàn bộ
dân số sẽ thực sự hành xử như thế nào. Một số học giả tin rằng bằng cách tìm ra
những điểm cân bằng của những trò chơi họ có thể dự đoán được dân số sẽ hành
xử như thế nào khi đối phó với những tình huống giống như trò chơi đang được
nghiên cứu. Quan điểm đặc biệt này về lý thuyết trò chơi đã bị chỉ trích gần đây.
Thứ nhất, nó bị chỉ trích bởi vì những giả sử được ra bởi các lý thuyết gia trò chơi
thường bị vi phạm. Một số lý thuyết gia trò chơi có thể giả sử rằng những người
chơi luôn hành xử hợp lý để làm tối ưu hóa phần thắng của anh ta (mô hình Homo
economicus), nhưng người thật thường hành động hoặc là không hợp lý, hoặc là
hành động hợp lý để là tối ưu phần thắng của một nhóm người lớn hơn (hành động
vị tha). Những lý thuyết gia trò chơi trả lời bằng cách so sánh những giả sử của
họ với những giả sử được sử dụng trong vật lý. Do vậy trong khi những giả sử của
họ không phải luôn luôn đúng, họ có thể xem lý thuyết trò chơi như là một lý
tưởng khoa học hợp lý giống như là các mô hình được sử dụng bởi các nhà vật lý.
Tuy nhiên, những chỉ trích thêm của việc sử dụng này của lý thuyết trò chơi đã
Trang 12/37
được giảm đi bởi vì một số thí nghiêm cho thấy rằng các cá nhân không chơi
những chiến lược cân bằng. Ví dụ, trong trò chơi Centipede, Đoán 2/3 trung bình,
và trò Nhà độc tài, người ta thường không chơi với cân bằng Nash. Sự tranh cãi
vẫn tiếp diễn liên quan đến sự quan trọng của những thí nghiệm này.
Thay vào đó, một số tác giả cho rằng cân bằng Nash không đưa ra những dự
đoán cho toàn dân số con người, nhưng thiên về cung cấp một lời giải thích tại
sao những dân số chơi theo cân bằng Nash vẫn duy trì ở trong trạng thái đó. Tuy
nhiên, câu hỏi tại sao dân số đạt đến những điểm đó vẫn là bài toán mở.
Một số lý thuyết gia trò chơi đã xoay qua lý thuyết tiến hóa trò chơi để lý giải
những lo lắng này. Những mô hình này giả sử hoặc là không có sự hợp lý nào
hoặc là hợp lý bị chặn trên phần của các người chơi. Mặc cho tên gọi, lý thuyết
tiến hóa trò chơi không cần thiết giả sử chọn lọc tự nhiên theo nghĩa của sinh học.
Lý thuyết tiến hóa trò chơi bao gồm cả sinh học cũng như là tiến hóa văn hóa và
cũng như các mô hình học tập cá nhân (ví dụ, biến động của trò chơi giả).
Theo ý kiến khác, một số học giả cho rằng lý Hợp tác Phản bội
thuyết trò chơi không phải là một công cụ dự
Hợp tác 2, 2 0, 3
đoán cho hành vi của con người, mà như là một
đề nghị để người ta nên phải hành xử như thế Phản bội 3, 0 1, 1
nào. Bởi vì một cân bằng Nash của một trò chơi Song đề tù nhân
bao gồm những đáp lại tốt nhất cho những hành
động của các người chơi khác, chơi một chiến thuật là một phần của một cân bằng
Nash trông có vẻ là hợp lý. Tuy nhiên, việc sử dụng này của lý thuyết trò chơi
cũng đã bị chỉ trích. Đầu tiên, trong một số trường hợp là hợp lý để chơi một chiến
lược không cân bằng nếu như một người mong đợi những người khác cũng chơi
những chiến lược không cân bằng. Ví dụ, xem Đoán 2/3 giá trị trung bình.
Thứ hai là, Song đề tù nhân đưa ra một phản ví dụ nổi bật khác. Trong Song
đề tù nhân, mỗi người chơi đi theo sở thích riêng của anh ta dẫn đến cả hai người
Trang 13/37
chơi đều bị thiệt thòi thêm nếu như họ không theo đuổi những sở thích riêng của
họ. Một số học giả tin rằng điều này biểu diễn sự thất bại của lý thuyết trò chơi
như là một khuyến cáo cho hành xử.
5.2 Sinh học:
Không giống như trong kinh tế, phần Diều hâu Bồ câu
lợi cho những trò chơi trong sinh học
Diều hâu (V-C)/2, (V-C)/2 V, 0
thường được diễn dịch như là tương ứng
Bồ câu 0, V V/2, V/2
với sự thích nghi. Thêm vào đó, chú ý
đã ít hơn về các cân bằng có liên quan Diều hâu - Bồ câu
đến khái niệm của sự hợp lý, nhưng là
thiên về những thứ có thể duy trì được bởi các lực tiến hóa. Cân bằng được biết
đến nhiều nhất trong sinh học được biết đến như là chiến lược tiến hóa bền vững
(viết tắt ESS cho Evolutionary Stable Strategy), là được giới thiệu lần đầu bởi
John Maynard Smith (mô tả trong cuốn sách năm 1982 của ông). Mặc đu động
lực ban đầu của nó không liên quan đến bất cứ yêu cầu về tinh thần nào của cân
bằng Nash, mỗi ESS là một cân bằng Nash.
Trong sinh học, lý thuyết trò chơi đã được sử dụng để hiểu được nhiều hiện
tượng khác nhau. Nó được sử dụng lần đầu để giải thích sự tiến hóa (và bền vững)
của tỷ lệ giới tính khoảng 1:1.Ronald Fisher (1930) đề nghị rằng tỉ lệ giới tính 1:1
là kết quả của những lực tiến hóa tác động lên những cá nhân là những người có
thể được xem như là cố gắng làm tối đa số cháu chắt của mình.
Thêm vào đó, những nhà sinh vật đã sử dụng lý thuyết trò chơi tiến hóa và ESS
để giải thích sự nổi lên của liên lạc giữa muông thú (Maynard Smith& Harper,
2003). Sự phân tích của các trò chơi tín hiệu và các trò chơi liên lạc khác đã cung
cấp một số trực giác vào trong sự tiến hóa của việc liên lạc giữa muôn thú.
Trang 14/37
Cuối cùng, các nhà sinh vật đã sử dụng trò chơi diều hâu-bồ câu (cũng được
biết đến như là con gà) để phân tích những hành vi đánh nhau và tranh giành lãnh
thổ.
5.3 Khoahọc máy tính và logic:
Lý thuyết trò chơi đã đóng một vai trò ngày càng quan trọng trong logic và
trong khoa học máy tính. Một số lý thuyết logic có cơsở trong ngữ nghĩa trò chơi.
Thêm vào đó, những khoa học gia máy tính đã sử dụng trò chơi để mô phỏng
những tính toán tương tác với nhau.
5.4 Chính trị học:
Các nghiên cứu trong khoa học chính trị cũng có sử dụng lý thuyết trò chơi.
Một thuyết trò chơi giải thích cho lý thuyết dân chủ hòa bình rằng tính công khai
và tranh luận cởi mở trong các nền dân chủ sẽ gởi một thông điệp rõ ràng và khả
tín về các mục tiêu đến những chế độ khác. Ngược lại, khó mà biết được những
chủ đích của của các lãnh đạo phi dân chủ (độc tài), rằng sẽ có sự nhượng bộ
chung hiệu quả nào, và các lời hứa hẹn có được tôn trọng hay không. Do đó, sẽ
tồn tại sự việc không tin tưởng và không mong muốn nhằm tạo ra sự nhượng bộ
chung nếu ít nhất một trong các thành phần của sự bàn cãi này là thành phần phi
dân chủ.
5.5 Triết học:
Lý thuyết trò chơi đã được đưa vào một vài sử dụng trong triết học. Hai bài
báo bởi W.V.O. Quine (1960, 1967), David Lewis (1969) sử dụng lý thuyết trò
chơi để phát triển một triết lý của hội nghị. Khi làm việc đó, ông đã cung cấp
những phân tích đầu tiên của kiến thức chung và sử dụng nó trong việc phân tích
những cách chơi trong những trò chơi được quản lý. Thêm vào đó, ông lần đầu
tiên đề nghị rằng người ta có thể hiểu được ý nghĩa dưới các điều kiện của trò chơi
Trang 15/37
đánh tín hiệu. Đề nghị sau đã được theo đuổi bởi một vài triết gia tính từ Lewis
(Skyrms 1996, Grim et al. 2004).
Trong đạo đức, một số tác giả đã cố gắng theo đuổi dự án
này, bắt đầu bởi Thomas Hobbes, bằng cách suy diễn ra đạo Nai Thỏ
đức từ những lợi ích cá nhân. Bởi vì những trò chơi giống như
Prisoner's Dilemma đưa ra những mâu thuẫn rõ ràng giữa đạo
Nai 3, 3 0, 2
đức và lợi ích cá nhân, giải thích tại sao hợp tác là cần thiết
bởi lợi ích cá nhân là một phần quan trọng của dự án này.
Thỏ 2, 0 2, 2
Chiến lược chung này là một phần của quan điểm hợp đồng
xã hội tổng quát trong triết học chính trị Trò săn nai
Cuối cùng, một số tác giả khác đã cố gắng sử dụng lý thuyết
tiến hóa trò chơi để giải thích sự phát triển trong quan điểm con người về đạo đức
và những hành xử tương ứng của muông thú. Những tác giả này đã xem xét một
số trò chơi bao gồm Song đề tù nhân, săn nai, và trò mặc cả của Nash như để cung
cấp một lời giải thích về sự phát triển của các quan điểm về đạo đức.
Trang 16/37
CHƯƠNG 2: ỨNG DỤNG TRONG TRÒ CHƠI CARO
1. Giới thiệu về trí tuệ nhân tạo:
Trí tuệ nhân tạo (hay AI: Artificial Intelligence), là nỗ lực tìm hiểu những yếu
tố trí tuệ. Lý do khác để nghiên cứu lĩnh vực này là cách để ta tự tìm hiểu bản thân
chúng ta. Không giống triết học và tâm lý học, hai khoa học liên quan đến trí tuệ,
còn AI cố gắng thiết lập các các yếu tố trí tuệ cũng như tìm biết về chúng. Lý do
khác để nghiên cứu AI là để tạo ra các thực thể thông minh giúp ích cho chúng ta.
AI có nhiều sản phẩm quan trọng và đáng lưu ý, thậm chí ngay từ lúc sản phẩm
mới được hình thành. Mặc dù không dự báo được tương lai, nhưng rõ ràng máy
tính điện tử với độ thông minh nhất định đã có ảnh hưởng lớn tới cuộc sống ngày
nay và tương lai phát triển.
Khi máy móc ngày càng tăng khả năng, các nhiệm vụ được coi là cần "trí thông
minh" thường bị loại bỏ khỏi định nghĩa về AI, một hiện tượng được gọi là hiệu
ứng AI. Một câu châm ngôn trong Định lý của Tesler nói rằng "AI là bất cứ điều
gì chưa được thực hiện." Ví dụ, nhận dạng ký tự quang học thường bị loại trừ khỏi
những thứ được coi là AI, đã trở thành một công nghệ thông thường. khả năng
máy hiện đại thường được phân loại như AI bao gồm thành công hiểu lời nói của
con người, cạnh tranh ở mức cao nhất trong trò chơi chiến lược (chẳng hạn như
cờ vây, cờ vua, cờ caro), xe hoạt động độc lập, định tuyến thông minh trong mạng
phân phối nội dung, và mô phỏng quân sự.
Trí tuệ nhân tạo có thể được phân thành ba loại hệ thống khác nhau: trí tuệ
nhân tạo phân tích, lấy cảm hứng từ con người và nhân tạo. AI phân tích chỉ có
các đặc điểm phù hợp với trí tuệ nhận thức; tạo ra một đại diện nhận thức về thế
giới và sử dụng học tập dựa trên kinh nghiệm trong quá khứ để thông báo các
quyết định trong tương lai. AI lấy cảm hứng từ con người có các yếu tố từ trí tuệ
nhận thức và cảm xúc; hiểu cảm xúc của con người, ngoài các yếu tố nhận thức
và xem xét chúng trong việc ra quyết định. AI nhân cách hóa cho thấy các đặc
điểm của tất cả các loại năng lực (nghĩa là trí tuệ nhận thức, cảm xúc và xã hội),
có khả năng tự ý thức và tự nhận thức được trong các tương tác.
Trang 17/37
2. Giải quyết vấn đề bằng tìm kiếm:
Vấn đề tìm kiếm, một cách tổng quát, có thể hiểu là tìm một đối tượng thỏa
mãn một số đòi hỏi nào đó, trong một tập hợp rộng lớn các đối tượng . Chúng ta
có thể kể ra rất nhiều vấn đề ḿ việc giải quyết nó được quy về vấn đề tìm kiếm.
Các trò chơi, chẳng hạn cờ vua, cờ carô, cờ vây có thể xem những vấn đề tìm
kiếm. Trong số rấtnhiều nước đi được phép thực hiện, ta phải tìm ra các nước đi
dẫn tới tình thế kết cuộć ta là người thắng.
Chứng minh định lý cũng có thể xem những vấn đề tìm kiếm. Cho một tập các
tiên đề vàcác luật suy diễn, trong trường hợp này mục tiêu của ta là tìm ra một
chứng minh (một dãy các luật suy diễn được áp dụng) để được đưa đến công thức
mà ta cần chứng minh.
Trong các lĩnh vực nghiên cứu của Trí Tuệ Nhân Tạo, chúng ta thường xuyên
phải đối đầu với vấn đề tìm kiếm. Đặc biệt trong lập kế hoạch và học máy, tìm
kiếm đóng vai trò quan trọng. Các kỹ thuật tìm kiếm bao gồm:
Các kỹ thuật tìm kiếm kinh nghiệm (tìm kiếm heuristic) trong đó chúng ta dựa
vào kinh nghiệm và sự hiểu biết của chúng ta về vấn đề cần giải quyết để xây
dựng nên hàm đánh giá hướng dẫn sự tìm kiếm.
Các kỹ thuật tìm kiếm tối ưu.
Các phương pháp tìm kiếm có đối thủ, tức là các chiến lược tìm kiếm nước đi
trongcác trò chơi hai người, chẳng hạn cờ vua, cờ tướng, cờ carô.
Trang 18/37
3. Giải quyết bài toán:
3.1 Giới thiệu trò chơi:
Hình 1: Trờ chơi Gomoku
Cờ caro chính là môn cờ logic lâu đời và cổ xưa nhất. Cờ caro đã được sáng
tạo từ nhiều nền văn minh khác nhau một cách độc lập.
Nó bắt đầu xuất hiện từ năm 2000 trước CN ở sông Hoàng Hà, Trung Quốc.
Một số nhà khoa học đã tìm thấy bằng chứng chứng minh Caro đã được phát minh
ở Hy Lạp cổ đại và ở Châu Mỹ trước thời Colombo. Môn cờ cổ của Trung Quốc
là Wutzu. Cờ Caro du nhập từ Trung Quốc vào Nhật Bản từ khoảng năm 270
trước CN. Nó thường được gọi là Gomoku nhưng cũng có các tên gọi khác tùy
theo thời gian và địa phương như Kakugo, gomoku-narabe, Itsutsu-ishi… Người
ta đã tìm thấy một trò chơi cổ từ một di tích ở Nhật Bản năm 100 sau CN và thấy
nó là một biến thể của Caro. Nó đã lan truyền nhanh chóng với cái tên Kakugo
(trò 5 quân). Các nhà sử học nói rằng vào các thế kỷ 17 và 18, mọi người đều chơi
trò chơi này – người già cũng như người trẻ. Năm 1858, khi quyển sách đầu tiên
về trò chơi này được xuất bản, nó được gọi là Kakugo. Nó tiếp tục được chơi,
được gọi với nhiều tên khác nhau như Goren, Goseki, rồi Gomokunarabe,
Trang 19/37