現(xiàn)代計(jì)算機(jī)圍棋的主要智能技術(shù)

《現(xiàn)代計(jì)算機(jī)圍棋的主要智能技術(shù)》由會(huì)員分享，可在線閱讀，更多相關(guān)《現(xiàn)代計(jì)算機(jī)圍棋的主要智能技術(shù)（48頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,北郵-九鼎計(jì)算機(jī)圍棋研究所,*,現(xiàn)代計(jì)算機(jī)圍棋的主要智能技術(shù),北京郵電大學(xué),北郵,-,九鼎計(jì)算機(jī)圍棋研究所,劉知青,2024/10/20,1,北郵-九鼎計(jì)算機(jī)圍棋研究所,簡(jiǎn)介,現(xiàn)代計(jì)算機(jī)圍棋博弈使用了大量的智能科學(xué)技術(shù),本次報(bào)告介紹現(xiàn)代計(jì)算機(jī)圍棋博弈中所使用智能科學(xué)技術(shù)基本概念和基本理論,本次報(bào)告假設(shè)觀眾具有以下背景和基礎(chǔ),高等數(shù)學(xué)和概率論,數(shù)據(jù)結(jié)構(gòu)和算法分析,

2、操作系統(tǒng),簡(jiǎn)單的圍棋規(guī)則與知識(shí),2024/10/20,2,北郵-九鼎計(jì)算機(jī)圍棋研究所,本次報(bào)告的主要智能技術(shù),多臂匪徒問題與,UCB,算法（,20,分鐘）,馬爾科夫決策優(yōu)化與,UCT,算法（,20,分鐘）,假設(shè)檢驗(yàn)與模式識(shí)別（,20,分鐘）,模式的哈希表示與匹配（,20,分鐘）,圍棋,Monte-Carlo,形勢(shì)評(píng)估（,20,分鐘）,共享內(nèi)存的多核并行計(jì)算,（,20,分鐘）,2024/10/20,3,北郵-九鼎計(jì)算機(jī)圍棋研究所,主要智能技術(shù)之間的關(guān)系,每次圍棋對(duì)弈中的落子計(jì)算是使用,UCT,算法在圍棋博弈樹上進(jìn)行馬爾科夫決策優(yōu)化的一個(gè)過程,圍棋博弈樹的每個(gè)內(nèi)部節(jié)點(diǎn)對(duì)應(yīng)于一個(gè)多臂匪徒問題，,UC

3、T,算法使用,UCB,算法進(jìn)行優(yōu)化搜索選點(diǎn),圍棋博弈樹的每個(gè)葉子節(jié)點(diǎn)上，,UCT,算法使用,Monte-Carlo,方法進(jìn)行形勢(shì)評(píng)估,Monte-Carlo,形勢(shì)評(píng)估大量使用通過假設(shè)檢驗(yàn)所識(shí)別的模式以提高評(píng)估準(zhǔn)確率,使用哈希編碼表示模式以提高其匹配效率,使用,共享內(nèi)存的多核并行計(jì)算以提高總的效率,2024/10/20,4,北郵-九鼎計(jì)算機(jī)圍棋研究所,專業(yè)詞匯,Markov Decision Process,：馬爾科夫決策過程,Multi-Armed Bandit Problem,：多臂匪徒問題,Upper Confidence Bound,：,UCB,算法,UCB Applied to Tre

4、e,：,UCT,算法,Hypothesis Testing,：假設(shè)檢驗(yàn),Pattern Recognition,：模式識(shí)別,Hashing Function,：哈希函數(shù),Zobrist,Hashing,：,Zobrist,哈希,Monte-Carlo Method,：蒙特卡洛方法,Shared Memory,：共享內(nèi)存,Multi-Thread Concurrent Computing,：多線程并發(fā)計(jì)算,Multi-Core Parallel Computing,：多核并行計(jì)算,2024/10/20,5,北郵-九鼎計(jì)算機(jī)圍棋研究所,1.,多臂匪徒問題與,UCB,算法,探索與利用之間的權(quán)衡,多臂

5、匪徒問題模型,UCB,算法,基于,UCB,算法的優(yōu)化選擇算法,2024/10/20,6,北郵-九鼎計(jì)算機(jī)圍棋研究所,探索與利用之間的權(quán)衡,機(jī)器學(xué)習(xí)中的探索,機(jī)器學(xué)習(xí)中的利用,探索與利用之間的矛盾與權(quán)衡,2024/10/20,7,北郵-九鼎計(jì)算機(jī)圍棋研究所,多臂匪徒問題模型,多臂匪徒問題是權(quán)衡機(jī)器學(xué)習(xí)中探索與利用的一個(gè)典型模型，在統(tǒng)計(jì)學(xué)中有過仔細(xì)的研究,多臂匪徒問題模型：,一個(gè)多臂匪徒可以被看作一個(gè)賭場(chǎng)里的多臂角子機(jī),每個(gè)臂由一個(gè)序列的隨機(jī)變量所定義,這些隨機(jī)變量的值代表了連續(xù)拉動(dòng)該臂（以下稱為“訪問該機(jī)器”）所獲得的回報(bào),這些回報(bào)是相互獨(dú)立的和,恒等分布,的，并符合某種未知的回報(bào)率,2024/

6、10/20,8,北郵-九鼎計(jì)算機(jī)圍棋研究所,多臂匪徒問題的策略與,遺憾,多臂匪徒問題的策略指的是一個(gè)算法，該算法根據(jù)過去所訪問機(jī)器及其回報(bào)的序列來(lái)決定下一次要拉動(dòng)的臂,理論上的最優(yōu)策略總是訪問回報(bào)最高的機(jī)器，但理論上的最優(yōu)策略需要預(yù)先的知識(shí)，不可能是機(jī)器學(xué)習(xí)的結(jié)果,由于一個(gè)策略不一定總是訪問回報(bào)最高的機(jī)器，因此它的總體回報(bào)要比最優(yōu)策略的總體回報(bào)要小，其差別的期望就被定義為該策略的,遺憾,很明顯，遺憾較小的策略較好；其中,理論上的,最優(yōu)策略的遺憾是零,2024/10/20,9,北郵-九鼎計(jì)算機(jī)圍棋研究所,多臂匪徒問題的,最優(yōu)機(jī)器學(xué)習(xí)策略,基于機(jī)器學(xué)習(xí)的,多臂匪徒問題的,最優(yōu)策略具有以下特點(diǎn)：,其

7、遺憾不超過,訪問次數(shù)的,對(duì)數(shù)函數(shù),最優(yōu),機(jī)器,訪問次數(shù)是次優(yōu),機(jī)器,訪問次數(shù)的指數(shù)倍,在每只,機(jī)器,上定義,上限信心索引,，作為該,機(jī)器,回報(bào)期望的估計(jì),每次訪問上限信心索引最大的,機(jī)器,2024/10/20,10,北郵-九鼎計(jì)算機(jī)圍棋研究所,最優(yōu)機(jī)器學(xué)習(xí)策略之一：,UCB1,算法,如果回報(bào)的范圍是,0,，,1,，,UCB1,算法就是,多臂匪徒問題的,一個(gè)最優(yōu)機(jī)器學(xué)習(xí)策略,UCB1,算法如下：,訪問每個(gè),機(jī)器各一次,循環(huán)：,訪問當(dāng)前,上限信心索引最大的機(jī)器,2024/10/20,11,北郵-九鼎計(jì)算機(jī)圍棋研究所,UCB1,算法中的上限信心索引,在,UCB1,算法中上限信心索引通過二項(xiàng)的和來(lái)計(jì)算

8、，第一項(xiàng)為當(dāng)前的平均回報(bào)，第二項(xiàng)為平均回報(bào)信心范圍一側(cè)的尺寸,2024/10/20,12,北郵-九鼎計(jì)算機(jī)圍棋研究所,基于,UCB1,算法的優(yōu)化選擇算法,優(yōu)化選擇算法，用于選擇最優(yōu)機(jī)器,基于,UCB1,算法的優(yōu)化選擇算法,while(,having_time,)loop,使用,UCB1,算法訪問某個(gè)機(jī)器,end loop,return,訪問次數(shù)最多的機(jī)器,2024/10/20,13,北郵-九鼎計(jì)算機(jī)圍棋研究所,存在類似的其它形式的,UCB,算法,UCB2,算法,UCB tuned,算法,UCB1 normal,算法,-,貪婪,算法,2024/10/20,14,北郵-九鼎計(jì)算機(jī)圍棋研究所,多臂匪

9、徒問題與,UCB,算法參考文獻(xiàn),H.Robbins.(1952).Some Aspects of the Sequential Design of Experiments.,Bulletin of the American Mathematical Society,(58):527535.,Berry,D.,and,Fristedt,B.(1985).,Bandit problems,.London:Chapman and Hall.,Lai,T.and Robbins,H.(1985).Asymptotically efficient adaptive allocation rules.,A

10、dvances in Applied Mathematics,(,6),422.,Agrawal,R.(1995).Sample mean based index policies with,O(,log,n),regret for the multi-armed bandit problem.,Advances in Applied Probability,(,27),10541078.,Auer,P.,Cesa,-Bianchi,N.and Fischer,P.(2002).Finite-time analysis of the,multiarmed,bandit problem.,Mac

11、hine Learning Journal,47(2-3):235256.,2024/10/20,15,北郵-九鼎計(jì)算機(jī)圍棋研究所,2.,馬爾科夫決策優(yōu)化與,UCT,算法,馬爾科夫決策過程,Monte-Carlo,規(guī)劃,UCT,算法,2024/10/20,16,北郵-九鼎計(jì)算機(jī)圍棋研究所,馬爾科夫決策過程,馬爾科夫決策過程是個(gè)數(shù)學(xué)框架，用于特定狀況下的決策，該狀況下的結(jié)果有部分隨機(jī)性，也部分取決于決策者的控制,馬爾科夫決策是個(gè)離散時(shí)間上隨即控制過程。在每一步時(shí)間上，進(jìn)程的狀態(tài)為,s,，決策者選擇行為,a,，進(jìn)程在下一步時(shí)間上會(huì)隨機(jī)地變到,s,，同時(shí)決策者得到回報(bào),R,(,s,s,).,馬爾科夫

12、決策過程適用于一大類優(yōu)化問題的研究，這些問題的解決方法通常包含動(dòng)態(tài)規(guī)劃和增強(qiáng)型學(xué)習(xí),2024/10/20,17,北郵-九鼎計(jì)算機(jī)圍棋研究所,Monte-Carlo,規(guī)劃與馬爾科夫決策過程,Monte-Carlo,規(guī)劃是解決大型狀態(tài)空間上的馬爾科夫決策過程的不多的有效方法之一：,采用以采樣為基礎(chǔ)向前搜索,在搜索過程中會(huì)建立一棵狀態(tài)樹或狀態(tài),-,行為樹,采樣的回報(bào)會(huì)相應(yīng)地反映在樹上,2024/10/20,18,北郵-九鼎計(jì)算機(jī)圍棋研究所,Monte-Carlo,規(guī)劃的偽代碼,function,MonteCarloPlanning(,state,),Repeat,search(,state,0),u

13、ntil Timeout,return bestAction(,state,0),function,search(,state,depth,),if,Terminal(,state,)then return 0,if,Leaf(,state,;d,)then return,Evaluate(,state,),action,:=,selectAction(,state,depth,),(,nextstate,;reward,):=,simulateAction(,state,action,),q,:=,reward,+,search(,nextstate,depth,+1),UpdateValu

14、e(,state,;action;q;depth,),return,q,2024/10/20,19,北郵-九鼎計(jì)算機(jī)圍棋研究所,Monte-Carlo,規(guī)劃與,UCT,算法,UCT,算法是把,UCB,算法應(yīng)用于樹,UCT,算法可以提高,Monte-Carlo,規(guī)劃算法的效率，并具有以下二大特點(diǎn)：,如果算法提前結(jié)束，其錯(cuò)誤概率較小,如果運(yùn)行的時(shí)間足夠長(zhǎng)，算法的結(jié)果會(huì)收斂到最優(yōu)解,UCT,算法也應(yīng)用于博弈樹的搜索,2024/10/20,20,北郵-九鼎計(jì)算機(jī)圍棋研究所,UCT,算法,UCT,算法是,Monte-Carlo,規(guī)劃算法的改進(jìn),其核心改進(jìn)在,selectAction,函數(shù)中：,每個(gè)樹的內(nèi)

15、部節(jié)點(diǎn)是一個(gè)獨(dú)立的,多臂匪徒問題，其中每一個(gè)臂對(duì)應(yīng)于一個(gè)行為及其回報(bào)，其中回報(bào)是以該節(jié)點(diǎn)為起點(diǎn)所模擬路徑段回報(bào)的集成,使用,UCB1,算法在樹的內(nèi)部節(jié)點(diǎn)上選擇模擬中的下一個(gè)行為,2024/10/20,21,北郵-九鼎計(jì)算機(jī)圍棋研究所,UCT,算法參考文獻(xiàn),Kearns,M.,Mansour,Y.and Ng,A.Y.(1999).A sparse sampling algorithm for near-optimal planning in large,Markovian,decision processes.In,Proceedings of IJ-CAI99,1324-1331.,Kocs

16、is,L.,and,Szepesvari,C.(2006).Bandit based,monte-carlo,planning.In ECML-06.,2024/10/20,22,北郵-九鼎計(jì)算機(jī)圍棋研究所,3.,假設(shè)檢驗(yàn)與模式識(shí)別,頻率方法,假設(shè)檢驗(yàn),模式識(shí)別,2024/10/20,23,北郵-九鼎計(jì)算機(jī)圍棋研究所,頻率方法,最簡(jiǎn)單的方法計(jì)算語(yǔ)料庫(kù)中搭配出現(xiàn)的次數(shù)，如果二個(gè)事物一起出現(xiàn)的次數(shù)很多，其關(guān)聯(lián)度可能就不一般,頻率方法在一定程度上是有效的，但其有效性有缺陷：,高頻率可能是偶然性的：如果二個(gè)字的出現(xiàn)頻率都很高，它們一起出現(xiàn)的頻率也會(huì)搞，但并不表明它們之間有較強(qiáng)的關(guān)聯(lián)度而成為一個(gè)詞，例如，“人的”,2024/10/20,24,北郵-九鼎計(jì)算機(jī)圍棋研究所,假設(shè)檢驗(yàn),關(guān)聯(lián)度實(shí)質(zhì)上表示二個(gè)字之間的關(guān)聯(lián)不是偶然的，這是統(tǒng)計(jì)學(xué)的一個(gè)經(jīng)典問題，叫做假設(shè)檢驗(yàn)。,我們做個(gè)空假設(shè),H0,：二個(gè)字之間沒有偶然機(jī)會(huì)之外的聯(lián)系，然后計(jì)算在,H0,為真的情況下二個(gè)字一期出現(xiàn)的條件概率,p,，如果,p,足夠?。ɡ?p,0.05,0.01,0.005,或,0.001,），我們就可以否定,H0,，從而證明二個(gè)