›
›

Bài giảng Trí tuệ nhân tạo - Tìm kiếm đối kháng-trò chơi

pdf 29 trang hapham 1150
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Trí tuệ nhân tạo - Tìm kiếm đối kháng-trò chơi", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfbai_giang_tri_tue_nhan_tao_tim_kiem_doi_khang_tro_choi.pdf

Nội dung text: Bài giảng Trí tuệ nhân tạo - Tìm kiếm đối kháng-trò chơi

  1. TRÍ TU NHÂN TO Tìm kim đi kháng – Trị chơi
  2. Ni dung trình bày 2  Trị chơi  Trị chơi đi kháng và tìm kim  Thut tốn MINIMAX  Ta nhánh αβ  Hàm lưng giá, Tìm kim ct nhánh
  3. Trị chơi 3  Là mt trong nhng đc tính đưc xem là “thơng minh” ca con ngưi  “F1” ca AI  ðã dành đưc nhng thành tu đáng k  đây ta xem xét các dng trị chơi trí tu, đi kháng (board game)
  4. Trị chơi 4  C vua  1997, DeepBlue đánh bi Gary Kasparov trong mt trn đu 6 ván  Bí quyt:  Tìm kim vét cn vi đ sâu cao nht cĩ th  Tính đưc 200.000.000 nưc đi mi giây so vi 2 ca Kasparov  (99.99% nưc đi đưc xem là ngu ngc)  Hàm lưng giá cc kỳ phc tp
  5. Trị chơi (tt) 5  Mt s khác:  C vây (GO): vn chưa cĩ chương trình hiu qu (do đ phân nhánh quá ln, b> 300)
  6. Trị chơi đi kháng và tìm kim 6  Các thành phn:  Tp trng thái: tp “cu hình” hp l ca trị chơi  Trng thái ban đu (initial state)  Trng thái kt thúc (terminal state), trng thái đích  Hàm succs(s): các nưc đi hp l  Hàm li ích (utility function): đánh giá trng thái kt thúc  Hai ngưi chơi: MAX vs. MIN  Khơng tìm đưng đi, tìm nưc đi “tt nht”.  Nưc đi ca MAX ph thuc vào nưc đi ca MIN và ngưc li.
  7. Ví d cây tìm kim trị chơi TicTacToe 7 MAX(x) Các nưc đi X X X MIN(o) X X X X O X O MAX(x) Các trng thái X O X X O X X O X KT THÚC O X O O X X O X X O X O O Li ích 1 0 +1
  8. Thut tốn MINIMAX 8  Nhng ngưi chơi là ti ưu  MAX ti đa hĩa hàm li ích  MIN ti thiu hĩa hàm li ích  Chin lưc ca MAX ph thuc vào chin lưc ca MIN bưc sau  Giá tr MINIMAXVALUE: tin ích trng thái kt thúc tương ng ca đưng đi, gi s nhng ngưi chơi luơn ti ưu
  9. Giá tr MINIMAX 9  MINIMAXVALUE(n) =  Utility(n) nu n là trng thái kt thúc  max{MINIMAXVALUE(s) | s ∈succs(n)} nu n là mt nút MAX  min{MINIMAXVALUE(s) | s ∈succs(n)} nu n là mt nút MIN
  10. Giá tr MINIMAX (vd) 10 MAX A MIN B C D 3128 246 145 2 trng thái kt thúc, giá tr MINIMAX VALUE(n) = Utility(n)
  11. Giá tr MINIMAX (vd) 11 MAX A MIN B 3 C 2 D 2 3128 246 1452 Ti mi trng thái cĩ th, MIN luơn chn đưng đi ti thiu hĩa giá tr tin ích trng thái kt thúc
  12. Giá tr MINIMAX (vd) 12 ðn lưt mình, MAX tìm 3 cách ti đa hĩa giá tr MAX A MINIMAX MIN B 3 C 2 D 2 3128 246 1452 Và MAX chn chin lưc đi đn B ng vi giá tr MINIMAX ti đa
  13. Thut tốn MINIMAX 13
  14. ðánh giá Thut gii MINIMAX 14  ðy đ? Cĩ (nu cây tìm kim hu hn)  Ti ưu? Cĩ (vi mt đi th ti ưu) m  ð phc tp thi gian? O(b ) m  ð phc tp khơng gian? O(b ) (tìm kim theo chiu sâu)  Vi c vua, b ≈ 35, m ≈100 vi mt ván thơng thưng  hồn tồn khơng th tìm đưc li gii ti ưu
  15. Ta nhánh αβ 15  Ta cĩ th làm gì đ gim s trng thái phi kim tra?  Mo: ta cĩ th tính đúng giá tr quyt đnh minimax mà khơng cn duyt mi đnh.  Hãy xem xét chi tit tng bưc quá trình tính giá tr minimax.  Ghi nh : thut tốn MINIMAX duyt theo chiu sâu.
  16. Ta nhánh αβ (vd) 16 Min tr giá tr [∞; +∞] MiniMax ca [∞; +∞] A MAX A [∞;3] B [∞;3] B 3 3 12 a) b) Min tr giá tr MiniMax ca MIN
  17. Ta nhánh αβ (vd) 17 [3; +∞] A [3;+ ∞] A [3;3] B [3;3] B [∞;2] C D 3 12 8 3 12 8 2 c) d)
  18. Ta nhánh αβ (vd) 18 [3; 14] A [3;3] A [3;3] B [∞;2]C [∞;14] D [3;3] B [∞;2] C [2;2] D 3 12 8 2 14 3 12 8 2 14 5 2 e) f)
  19. Ta nhánh αβ (vd) 19  Gi x, y là li ích ca các trng thái khơng xét. Ta cĩ: MINIMAXVALUE(gc) = max(min(3,12,8), min(2,x,y),min(14,5,2)) = max(3, min(2,x,y), 2) = max(3, z, 2) vi z <= 2 = 3  Giá tr MINIMAX ti gc khơng ph thuc vào x và y.
  20. ðánh giá αβ 20  Ta nhánh khơng nh hưng đn kt qu cui cùng  Th t các nưc đi tt cĩ th ci thin hiu qu ca ta nhánh (trong ví d, hãy xem xét nhánh D) m/2  Vi “th t hồn ho”, đ phc tp thi gian = O(b ) (cho phép tìm vi đ sâu gp đơi)
  21. Thut tốn αβ 21
  22. Thut tốn αβ (tt) 22
  23. Nghĩ trưc gii hn và hàm lưng giá 23  Các trị chơi thưng cĩ đ sâu ln (>35 đi vi c vua)  Trong thi gian thc, khơng th đi đn trng thái kt thúc đ đánh giá mt nưc đi > nghĩ trưc mt s bưc gii hn (ply)  Cn mt hàm lưng giá các trng thái khơng kt thúc thay cho hàm đánh giá li ích ca trng thái kt thúc.  Hàm lưng giá là mt heuristic.
  24. Nghĩ trưc gii hn và hàm lưng giá (tt) 24
  25. S bưc nghĩ trưc 25
  26. Hàm lưng giá 26  ðánh giá kh năng thành cơng ca mt nưc đi (thng, thua, hịa?)  ðánh giá tuyn tính tng các đc trưng cĩ đưc ca mt đi th Eval(s) = w 1 f1(s) + w 2 f2(s) + + w n fn(s) trong đĩ: w i: trng s gán cho quân th I (ví d: hu w=9, nga w= 3 ) fi: s quân cịn li  MiniMaxCutoff ging ht tìm kim MiniMaxValue tr:  Thay Terminal? bng Cutoff?  Thay Utility() bng Eval()
  27. Chương trình game 27
  28. ðiu cn nm 28  Các thành phn trị chơi, MIN, MAX  Thut tốn MINIMAX, thut tốn αβ  ðánh giá ca các thut tốn  Hàm lưng giá
  29. Thc mc 29