Trò chơi ngẫu nhiên - Lịch sử thay đổi

Tttrung vào lúc 06:53, ngày 19 tháng 4 năm 2021

2021-04-19T06:53:01Z

Minhpc: Tạo trang mới với nội dung “{{#switch: {{NAMESPACENUMBER}} | 0 =
Thể loại:Mục từ cần bình duyệt
File:UnderCon icon.svg|fram…”

2020-11-24T10:10:20Z

Tạo trang mới với nội dung “{{#switch: {{NAMESPACENUMBER}} | 0 = <div style="height:10px;">Thể loại:Mục từ cần bình duyệt</div> <center>File:UnderCon icon.svg|fram…”

Trang mới

{{#switch: {{NAMESPACENUMBER}} | 0 = <div style="height:10px;">[[Thể loại:Mục từ cần bình duyệt]]</div>
<center>[[File:UnderCon icon.svg|frameless|30px|link=]] ''Mục từ này chưa được [[BKTT:Tiêu chuẩn mục từ|bình duyệt]] và có thể cần sự [[Trợ giúp:Hướng dẫn|giúp đỡ của bạn]] để hoàn thiện.''</center> |}}


== Trò chơi ngẫu nhiên ==
Trò chơi ngẫu nhiên là một trò chơi động có tính Markov được chơi theo một chuỗi các giai đoạn. Vào đầu mỗi giai đoạn, trò chơi ở trong một trạng thái nào đó, đấu thủ chọn một hành động và được một phần thưởng phụ thuộc vào trạng thái hiện tại và hành động đã chọn. Tiếp theo, trò chơi chuyển sang trạng thái ngẫu nhiên mới có phân bố phụ thuộc vào trạng thái trước đó và hành động đã được đấu thủ chọn. Thủ tục được lặp lại ở trạng thái mới và tiếp tục lặp lại qua một số hữu hạn hoặc vô hạn các giai đoạn. Tính Markov thể hiện hàm phân phối xác suất chuyển không phụ thuộc vào lịch sử của trò chơi, nghĩa là

<div class="center" style="width:auto; margin-left:auto; margin-right:auto;"><math>F(x_k\ |\ x_1, s^{(x_1)};\ ...;x_{k - 1}, s^{(x_{k - 1})}) = F(x_k\ |\ x_{k - 1}, s^{(x_{k - 1})}),</math></div>

trong đó <math>F(x_k\ |\ x_1, s^{x_1};...;x_{k - 1}, s^{(x_{k - 1})})</math> là hàm phân phối xác suất của trò chơi tại thời điểm tương lai <math>x_k</math> với điều kiện trước đó, ở các thời điểm quá khứ <math>(x_1, ..., x_{k - 1})</math> trò chơi đã có các trạng thái <math>(s^{(x_1)},\ ...,s^{(x_{k - 1})})</math> tương ứng, còn <math>F(x_k\ |\ x_{k - 1}, s^{(x_{k - 1})})</math> là hàm phân phối xác suất của trò chơi tại thời điểm <math>x_k</math> với điều kiện ở thời điểm hiện tại <math>x_{k - 1}</math> trò chơi có trạng thái <math>s^{(x_{k - 1})}</math>.

L.S. Shapley là người đầu tiên đưa ra định nghĩa khái niệm trò chơi ngẫu nhiên vào đầu những năm 1950, khi nghiên cứu trò chơi ngẫu nhiên với tổng bằng 0 của hai người chơi với luật chơi chi trả ngay (được gọi là ''trò chơi Shapley''). Trong trò chơi Shapley, tập các trạng thái của trò chơi và các bộ chiến lược cơ bản của các đấu thủ đều là hữu hạn, đồng thời ở bất kỳ bước nào và đối với bất kỳ lựa chọn nào của các đấu thủ, trò chơi đều có thể chấm dứt với một xác suất dương. Với điều kiện này, trò chơi kết thúc với xác suất 1 sau một số lượng hữu hạn các bước, đồng thời kỳ vọng toán của lượng tiền được chi trả của mỗi người chơi là hữu hạn. Trong một trò chơi như vậy, cả hai đấu thủ đều có chiến lược tối ưu dừng, tức là các chiến lược mà ở mọi giai đoạn của trò chơi, đấu thủ lựa chọn chiến lược cơ bản chỉ phụ thuộc vào tình hình tại thời điểm hiện tại. Shapley cũng phát hiện ra một thủ tục để có thể tìm ra chiến lược tối ưu của trò chơi.

Người ta còn nghiên cứu các trò chơi ngẫu nhiên khác với trò chơi Shapley có thể có vô hạn các trạng thái, là các trò chơi ngẫu nhiên với mức chi trả trung bình có giới hạn, nghĩa là trò chơi ngẫu nhiên hai đấu thủ với tổng bằng 0 mà các chi trả <math>h_1</math> và <math>h_2</math> của hai đấu thủ thỏa mãn đẳng thức

<div class="center" style="width:auto; margin-left:auto; margin-right:auto;"><math>h_1(P) = h_2(P) = \limsup_{n \to \infty} \sum_{k=1}^N {\frac{1}{n}h_i(x_k,s^{x_k})}.</math></div>

Dưới điều kiện tính ergodic của xích Markov, sự tồn tại của chiến lược tối ưu dừng của một trò chơi như thế đã được chứng minh. Những kết quả này cũng được tổng quát hoá cho những trường hợp hạn chế số lượng các trạng thái và chiến lược cơ bản, và đối với các dạng luật chi trả khác.

== Trò chơi thống kê ==
Bên cạnh khái niệm trò chơi ngẫu nhiên còn có khái niệm ''trò chơi thống kê'' là trò chơi hai đấu thủ với tổng bằng 0, trong đó người chơi thứ nhất được hiểu là tự nhiên, có chiến lược là một quá trình ngẫu nhiên, còn người chơi thứ hai được coi như một nhà thống kê, có chiến lược là một quy tắc quyết định (hàm quyết định), đồng thời hàm chi trả cho người chơi thứ nhất là hàm tổn thất của nhà thống kê. Chiến lược hỗn hợp của người chơi thứ nhất sẽ là một độ đo xác suất áp lên tập các quá trình ngẫu nhiên nêu trên, chiến lược hỗn hợp của người chơi thứ hai sẽ là một quy tắc quyết định ngẫu nhiên, đồng thời hàm chi trả cho người chơi thứ nhất được định nghĩa bằng kỳ vọng toán của hàm tổn thất của nhà thống kê.

Các trò chơi thống kê phát sinh từ các bài toán thống kê toán học (ví dụ, các bài toán ước lượng tham số, kiểm định giả thuyết, v.v.), trong đó có sử dụng phép kiểm định minimax. Việc mô tả một cách hệ thống về các bài toán thống kê toán học như các trò chơi thống kê được A. Wald giới thiệu lần đầu tiên, ông đã chứng minh định lý minimax cho một lớp rộng các trò chơi thống kê. Định lý này cung cấp một phương pháp giải quyết các vấn đề thống kê toán học, vì trong một số trường hợp có thể dễ dàng hơn và thuận tiện hơn để tìm ra maximin so với minimax, điều này làm cho việc tìm ra một quy tắc ngẫu nhiên hóa tối ưu trở nên dễ dàng hơn.

== Mô hình tổng quát ==
Một trò chơi ngẫu nhiên bao gồm: tập hợp hữu hạn đấu thủ <math>I</math>; không gian trạng thái <math>M</math>; tập hành động <math>S^i</math> cho từng đấu thủ <math>i \in I</math>; xác suất chuyển trạng thái <math>\mathbb{P}</math> từ <math>M \times S</math> sang <math>M</math>, trong đó <math>S = \times _{i \in I}S^i</math>, với <math>\mathbb{P}(A|m, s)</math> là xác suất mà trạng thái tiếp theo nằm trong <math>A</math> với điều kiện trạng thái hiện tại là <math>m</math> và hành động hiện tại là <math>s</math>; và hàm chi trả <math>g : M \times S \to \mathbb{R}^I</math>, trong đó hàm véc tơ <math>g</math> có tọa độ thứ <math>i</math> là <math>g^i</math> , cho biết số tiền thưởng đấu thủ thứ <math>i</math> sẽ nhận được nếu đang ở trạng thái <math>m</math> mà chọn hành động <math>s</math>.

Trò chơi bắt đầu ở trạng thái ban đầu <math>m_1</math> nào đó. Ở giai đoạn <math>t</math>, trước tiên các đấu thủ quan sát trạng thái <math>m_t</math>, rồi cùng một lúc chọn các hành động <math>s^i_t</math> trong <math>S^i</math> của mình, sau đó quan sát danh mục hành động <math>s_t = s^i_t : i \in I</math> của tất cả các đấu thủ cùng chơi, tiếp đó cơ chế của trò chơi sẽ tự động chọn ra <math>m_{t + 1}</math> theo xác suất <math>\mathbb{P}(\cdot | m_t, s_t)</math>. Việc tiến hành trò chơi ngẫu nhiên, <math>(m_1, s_1),...,(m_t, s_t)...,</math> sẽ xác định luồng véc tơ tiền thưởng được thanh toán <math>g_1, g_2,\ ...,</math> trong đó <math>g_t = g(m_t, s_t)</math>.

Trò chơi có khấu trừ <math>\Gamma _\lambda</math>Γλ với hệ số khấu trừ <math>\lambda \in (0;1]</math> là trò chơi mà người chơi thứ <math>i</math> được nhận số tiền thưởng bằng <math>\lambda \textstyle \sum_{t=1}^{\infty}(1 - \lambda)^{t - 1}g^i_t</math>. ''Trò chơi n - giai đoạn'' là trò chơi mà tiền thưởng cho người chơi thứ <math>i</math> bằng <math>g^{-i}_n := \frac{1}{n}\textstyle\sum_{t=1}^{n}g^i_t</math>.

Trò chơi ngẫu nhiên có nhiều ứng dụng trong kinh tế, sinh học và nghiên cứu mạng máy tính.

== Tài liệu tham khảo ==

# L. S. Shapley, Stochastic games, Proc. Nat. Acad. Sci. 39 (1953), 1095 - 1100.
# K. Vrieze, Zero-sum stochastic games. Surveys in Game Theory and Related Topics, Tracts 39 (1987), CWI, 103 - 132.
# A. Condon, The complexity of stochastic games, Information and Computation 96 (1992), 203–224.
# J. Filar and K. Vrieze, Competitive Markov Decision Processes, SpringerVerlag, 1997.
# J. F. Mertens and A. Neyman, Stochastic Games, International Journal of Game Theory 10 (1981), No. 2, 53 - 66.
# A. Neyman and S. Sorin, Stochastic Games and Applications, Dordrecht: Kluwer Academic Press, 2003.
# N. Vieille, Stochastic games: Recent results, Handbook of Game Theory, Amsterdam: Elsevier Science, 2002, 1833 - 1850.

@@ Dòng 1: / Dòng 1: @@
-{{#switch: {{NAMESPACENUMBER}} | 0 = <div style="height:10px;">[[Thể loại:Mục từ cần bình duyệt]]</div>
+{{mới}}
-<center>[[File:UnderCon icon.svg|frameless|30px|link=]] ''Mục từ này chưa được [[BKTT:Tiêu chuẩn mục từ|bình duyệt]] và có thể cần sự [[Trợ giúp:Hướng dẫn|giúp đỡ của bạn]] để hoàn thiện.''</center> |}}
+'''Trò chơi ngẫu nhiên''' là một trò chơi động có tính Markov được chơi theo một chuỗi các giai đoạn. Vào đầu mỗi giai đoạn, trò chơi ở trong một trạng thái nào đó, đấu thủ chọn một hành động và được một phần thưởng phụ thuộc vào trạng thái hiện tại và hành động đã chọn. Tiếp theo, trò chơi chuyển sang trạng thái ngẫu nhiên mới có phân bố phụ thuộc vào trạng thái trước đó và hành động đã được đấu thủ chọn. Thủ tục được lặp lại ở trạng thái mới và tiếp tục lặp lại qua một số hữu hạn hoặc vô hạn các giai đoạn. Tính Markov thể hiện hàm phân phối xác suất chuyển không phụ thuộc vào lịch sử của trò chơi, nghĩa là
-<!-- BẮT ĐẦU NỘI DUNG MỤC TỪ Ở DƯỚI ĐÂY. XIN ĐỪNG SỬA ĐỔI GÌ TỪ DÒNG NÀY TRỞ LÊN TRÊN, TRƯỚC KHI MỤC TỪ ĐƯỢC BÌNH DUYỆT -->
+:<math>F(x_k\ |\ x_1, s^{(x_1)};\ ...;x_{k - 1}, s^{(x_{k - 1})}) = F(x_k\ |\ x_{k - 1}, s^{(x_{k - 1})}),</math>
 trong đó <math>F(x_k\ |\ x_1, s^{x_1};...;x_{k - 1}, s^{(x_{k - 1})})</math> là hàm phân phối xác suất của trò chơi tại thời điểm tương lai <math>x_k</math> với điều kiện trước đó, ở các thời điểm quá khứ <math>(x_1, ..., x_{k - 1})</math> trò chơi đã có các trạng thái <math>(s^{(x_1)},\ ...,s^{(x_{k - 1})})</math> tương ứng, còn <math>F(x_k\ |\ x_{k - 1}, s^{(x_{k - 1})})</math> là hàm phân phối xác suất của trò chơi tại thời điểm <math>x_k</math> với điều kiện ở thời điểm hiện tại <math>x_{k - 1}</math> trò chơi có trạng thái <math>s^{(x_{k - 1})}</math>.
@@ Dòng 12: / Dòng 7: @@
 L.S. Shapley là người đầu tiên đưa ra định nghĩa khái niệm trò chơi ngẫu nhiên vào đầu những năm 1950, khi nghiên cứu trò chơi ngẫu nhiên với tổng bằng 0 của hai người chơi với luật chơi chi trả ngay (được gọi là ''trò chơi Shapley''). Trong trò chơi Shapley, tập các trạng thái của trò chơi và các bộ chiến lược cơ bản của các đấu thủ đều là hữu hạn, đồng thời ở bất kỳ bước nào và đối với bất kỳ lựa chọn nào của các đấu thủ, trò chơi đều có thể chấm dứt với một xác suất dương. Với điều kiện này, trò chơi kết thúc với xác suất 1 sau một số lượng hữu hạn các bước, đồng thời kỳ vọng toán của lượng tiền được chi trả của mỗi người chơi là hữu hạn. Trong một trò chơi như vậy, cả hai đấu thủ đều có chiến lược tối ưu dừng, tức là các chiến lược mà ở mọi giai đoạn của trò chơi, đấu thủ lựa chọn chiến lược cơ bản chỉ phụ thuộc vào tình hình tại thời điểm hiện tại. Shapley cũng phát hiện ra một thủ tục để có thể tìm ra chiến lược tối ưu của trò chơi.
-Người ta còn nghiên cứu các trò chơi ngẫu nhiên khác với trò chơi Shapley có thể có vô hạn các trạng thái, là các trò chơi ngẫu nhiên với mức chi trả trung bình có giới hạn, nghĩa là trò chơi ngẫu nhiên hai đấu thủ với tổng bằng 0 mà các chi trả <math>h_1</math> và <math>h_2</math> của hai đấu thủ thỏa mãn đẳng thức
+Người ta còn nghiên cứu các trò chơi ngẫu nhiên khác với trò chơi Shapley có thể có vô hạn các trạng thái, là các trò chơi ngẫu nhiên với mức chi trả trung bình có giới hạn, nghĩa là trò chơi ngẫu nhiên hai đấu thủ với tổng bằng 0 mà các chi trả <math>h_1</math> và <math>h_2</math> của hai đấu thủ thỏa mãn đẳng thức:
 :<math>h_1(P) = h_2(P) = \limsup_{n \to \infty} \sum_{k=1}^N {\frac{1}{n}h_i(x_k,s^{x_k})}.</math>
 Dưới điều kiện tính ergodic của xích Markov, sự tồn tại của chiến lược tối ưu dừng của một trò chơi như thế đã được chứng minh. Những kết quả này cũng được tổng quát hoá cho những trường hợp hạn chế số lượng các trạng thái và chiến lược cơ bản, và đối với các dạng luật chi trả khác.
@@ Dòng 34: / Dòng 27: @@
 == Tài liệu tham khảo ==
 # L. S. Shapley, Stochastic games, Proc. Nat. Acad. Sci. 39 (1953), 1095 - 1100.
 # K. Vrieze, Zero-sum stochastic games. Surveys in Game Theory and Related Topics, Tracts 39 (1987), CWI, 103 - 132.

Trò chơi ngẫu nhiên - Lịch sử thay đổi

Tttrung vào lúc 06:53, ngày 19 tháng 4 năm 2021

Minhpc: Tạo trang mới với nội dung “{{#switch: {{NAMESPACENUMBER}} | 0 = Thể loại:Mục từ cần bình duyệt File:UnderCon icon.svg|fram…”

Minhpc: Tạo trang mới với nội dung “{{#switch: {{NAMESPACENUMBER}} | 0 =
Thể loại:Mục từ cần bình duyệt
File:UnderCon icon.svg|fram…”