基于虛擬遺憾最小化算法的德州撲克機(jī)器博弈研究.pdf

1、德州撲克是風(fēng)靡全球的撲克游戲，是非完備信息機(jī)器博弈的典型代表。游戲中的隨機(jī)發(fā)牌導(dǎo)致了信息的不確定性，博弈者無法得到對(duì)手的手牌信息致使信息具有不完備性，四輪的押注決策使游戲具有重復(fù)性等。德州撲克的非確定性非完備性等特點(diǎn)決定了其博弈樹具有指數(shù)級(jí)的游戲狀態(tài)，如簡(jiǎn)單的兩人限注德州撲克玩法，游戲的整個(gè)博弈樹包括3.19×1017個(gè)游戲狀態(tài)。對(duì)于德州撲克這類博弈狀態(tài)呈指數(shù)級(jí)增長(zhǎng)的游戲，虛擬遺憾最小化算法(Counterfactual Regret

2、Minimization,CFR)是目前最先進(jìn)的能夠生成高效策略的技術(shù)之一。CFR算法通過多次迭代計(jì)算博弈樹中每個(gè)信息集的動(dòng)作遺憾值和平均策略值，預(yù)測(cè)下一時(shí)刻的決策動(dòng)作，使其是當(dāng)前最小遺憾動(dòng)作。如何存儲(chǔ)大量迭代計(jì)算產(chǎn)生的遺憾值、平均策略值和計(jì)算效率是CFR算法面臨的兩大挑戰(zhàn)。本課題針對(duì)以上問題展開研究，對(duì)CFR算法進(jìn)行了改進(jìn)，實(shí)現(xiàn)了具有較高智能水平的德州撲克機(jī)器博弈系統(tǒng)。
　　本課題實(shí)現(xiàn)的德州撲克智能體使用基于9-Bucketin

3、g策略的底牌抽取技術(shù)對(duì)德州撲克游戲進(jìn)行抽象，降低了德州撲克狀態(tài)空間復(fù)雜度?；诿商乜_CFR算法的抽樣思想和Pure CFR算法的整數(shù)運(yùn)算思想，本課題提出了兩種改進(jìn)的CFR算法，根據(jù)離線訓(xùn)練和在線博弈時(shí)處理對(duì)手策略的不同方式，課題將改進(jìn)的算法稱為離線學(xué)習(xí)對(duì)手策略的CFR算法和在線自適應(yīng)對(duì)手策略的CFR算法。這兩種改進(jìn)算法與原始的CFR算法相比，提高了計(jì)算效率和博弈的勝率，降低了存儲(chǔ)要求。本課題根據(jù)改進(jìn)的CFR算法產(chǎn)生的最優(yōu)化策略選取未來

4、的決策行為時(shí)，結(jié)合使用欺詐策略，避免了被對(duì)手建模。2014年，本課題使用CFR算法實(shí)現(xiàn)的3-Kuhn撲克機(jī)器博弈智能體在國(guó)際人工智能協(xié)會(huì)(AAAI)舉辦的世界年度計(jì)算機(jī)撲克機(jī)器博弈大賽(ACPC)的3-Kuhn撲克項(xiàng)目中獲得了銅獎(jiǎng)，隨后根據(jù)本課題改進(jìn)的兩種CFR算法實(shí)現(xiàn)的德州撲克機(jī)器博弈智能體在與往年ACPC大賽決賽階段的部分參賽智能體的機(jī)器博弈對(duì)比實(shí)驗(yàn)中也取得了勝利。
　　在日常生活中，經(jīng)常需要在信息不完善或不確定的情況下做決策