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

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

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

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

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

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

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

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

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

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

9、徒問題與,UCB,算法參考文獻,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,北郵-九鼎計算機圍棋研究所,2.,馬爾科夫決策優(yōu)化與,UCT,算法,馬爾科夫決策過程,Monte-Carlo,規(guī)劃,UCT,算法,2024/10/20,16,北郵-九鼎計算機圍棋研究所,馬爾科夫決策過程,馬爾科夫決策過程是個數(shù)學框架，用于特定狀況下的決策，該狀況下的結(jié)果有部分隨機性，也部分取決于決策者的控制,馬爾科夫決策是個離散時間上隨即控制過程。在每一步時間上，進程的狀態(tài)為,s,，決策者選擇行為,a,，進程在下一步時間上會隨機地變到,s,，同時決策者得到回報,R,(,s,s,).,馬爾科夫

12、決策過程適用于一大類優(yōu)化問題的研究，這些問題的解決方法通常包含動態(tài)規(guī)劃和增強型學習,2024/10/20,17,北郵-九鼎計算機圍棋研究所,Monte-Carlo,規(guī)劃與馬爾科夫決策過程,Monte-Carlo,規(guī)劃是解決大型狀態(tài)空間上的馬爾科夫決策過程的不多的有效方法之一：,采用以采樣為基礎(chǔ)向前搜索,在搜索過程中會建立一棵狀態(tài)樹或狀態(tài),-,行為樹,采樣的回報會相應地反映在樹上,2024/10/20,18,北郵-九鼎計算機圍棋研究所,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,北郵-九鼎計算機圍棋研究所,Monte-Carlo,規(guī)劃與,UCT,算法,UCT,算法是把,UCB,算法應用于樹,UCT,算法可以提高,Monte-Carlo,規(guī)劃算法的效率，并具有以下二大特點：,如果算法提前結(jié)束，其錯誤概率較小,如果運行的時間足夠長，算法的結(jié)果會收斂到最優(yōu)解,UCT,算法也應用于博弈樹的搜索,2024/10/20,20,北郵-九鼎計算機圍棋研究所,UCT,算法,UCT,算法是,Monte-Carlo,規(guī)劃算法的改進,其核心改進在,selectAction,函數(shù)中：,每個樹的內(nèi)

15、部節(jié)點是一個獨立的,多臂匪徒問題，其中每一個臂對應于一個行為及其回報，其中回報是以該節(jié)點為起點所模擬路徑段回報的集成,使用,UCB1,算法在樹的內(nèi)部節(jié)點上選擇模擬中的下一個行為,2024/10/20,21,北郵-九鼎計算機圍棋研究所,UCT,算法參考文獻,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,北郵-九鼎計算機圍棋研究所,3.,假設(shè)檢驗與模式識別,頻率方法,假設(shè)檢驗,模式識別,2024/10/20,23,北郵-九鼎計算機圍棋研究所,頻率方法,最簡單的方法計算語料庫中搭配出現(xiàn)的次數(shù)，如果二個事物一起出現(xiàn)的次數(shù)很多，其關(guān)聯(lián)度可能就不一般,頻率方法在一定程度上是有效的，但其有效性有缺陷：,高頻率可能是偶然性的：如果二個字的出現(xiàn)頻率都很高，它們一起出現(xiàn)的頻率也會搞，但并不表明它們之間有較強的關(guān)聯(lián)度而成為一個詞，例如，“人的”,2024/10/20,24,北郵-九鼎計算機圍棋研究所,假設(shè)檢驗,關(guān)聯(lián)度實質(zhì)上表示二個字之間的關(guān)聯(lián)不是偶然的，這是統(tǒng)計學的一個經(jīng)典問題，叫做假設(shè)檢驗。,我們做個空假設(shè),H0,：二個字之間沒有偶然機會之外的聯(lián)系，然后計算在,H0,為真的情況下二個字一期出現(xiàn)的條件概率,p,，如果,p,足夠?。ɡ?p,0.05,0.01,0.005,或,0.001,），我們就可以否定,H0,，從而證明二個