設萬維讀者為首頁 萬維讀者網 -- 全球華人的精神家園 廣告服務 聯繫我們 關於萬維
 
首  頁 新  聞 視  頻 博  客 論  壇 分類廣告 購  物
搜索>> 發表日誌 控制面板 個人相冊 給我留言
幫助 退出
gugeren的博客  
有則寫之,無則空之  
https://blog.creaders.net/u/5804/ > 複製 > 收藏本頁
我的名片
gugeren
註冊日期: 2012-01-06
訪問總量: 4,468,658 次
點擊查看我的個人資料
Calendar
我的公告欄
最新發布
· 【美國股市】又是遍地黃金了!
· 【黃仁勛】揭出來,誰受益?誰最
· 【RRN】川普任由民主黨人在中選
· 【黃仁勛事件】為何現在才爆出?
· 【黃仁勛辭職】對美國高科技產業
· 【美國中選後】兩黨的行動方向
· 【RRN】叛國者接受20年監禁的認
友好鏈接
分類目錄
【DIY】
· DIY-2:修理漏水的浴缸水龍頭
· DIY-1:更換煤氣熱水鍋爐的水
【數學】
· 【韋東奕】出的一道有趣的數學題
· 【圓周率π】與斐波那契數
· 趣味的數學-468
· 趣味的數學-467
· 趣味的數學-466
· 趣味的數學-465
· 趣味的數學-464
· 趣味的數學-463
· 趣味的數學-462
· 趣味的數學-461
【美國大學申請】
· 又是申請大學時:申請美國大學心
· 尋找學生人均錢最多的美國高校
· 尋找有錢的美國大學
· 藤校中亞裔學生的比例
· 歡迎B咖學生的美國大學
· 美國大學招生時着重察看申請學生
· 有關申請美國大學過程的書籍和網
· 美國勞工部對2010-2020年勞動力
【雜記】
· 從李密《陳情表》說開去
· 請萬維編輯注意博客中的安全問題
· 從《上甘嶺》到《黃河絕戀》
· 【轉】任正非:華為現在就像一架
· 錄魯迅詩以祭六四慘案卅周年
· 【摘錄】中國加入世界貿易組織的
· 如何看美中電視播音員辯論直播
· 【快訊】美中播音員辯論直播
· 當今世界的前10名人口大國
· 什麼是“貿易順差”?
【股票+金融】
· 【美國股市】又是遍地黃金了!
· 【川普】收取外國關稅的稅率
· 美FED於周日異常減1%利率
· 如今美國股市遍地黃金
· 淺談“長期護理”
· 再談中國政府拋售美國國債的後果
· 對西岸博的回應
· 中國拋售美國國債的後果
· S&P500中高利潤率的股票
· 【轉】對弈論闡述股市大戶贏錢策
【自己文章】
· 【黃仁勛】揭出來,誰受益?誰最
· 【2025和2026年】老人標準免稅額
· 【投資美國股市】就是投資美國經
· 【ChatGPT 5】幫助數學家查文獻
· 【稀土和關稅之我見】
· 【ChatGPT-5】真不錯!
· 【徵答】解決美國兩大經濟問題
· 【楊】安澤的落選表明每月千刀的
· 【網站】RRN是一個什麼網站?
· 【廚房】饅頭為何塌陷、萎縮?
【轉貼好文章】
· 【RRN】川普任由民主黨人在中選
· 【黃仁勛事件】為何現在才爆出?
· 【黃仁勛辭職】對美國高科技產業
· 【美國中選後】兩黨的行動方向
· 【RRN】叛國者接受20年監禁的認
· 【川普】經濟如此生猛!
· 【RRN】白帽搶時間揪出五角大樓
· 【中選結果】與美國股市
· 【川普政府各部門】聯合行動打擊
· 【中期選舉】有人就是想玩花樣
存檔目錄
11/01/2026 - 11/30/2026
10/01/2026 - 10/31/2026
09/01/2026 - 09/30/2026
08/01/2026 - 08/31/2026
07/01/2026 - 07/31/2026
06/01/2026 - 06/30/2026
05/01/2026 - 05/31/2026
04/01/2026 - 04/30/2026
03/01/2026 - 03/31/2026
02/01/2026 - 02/28/2026
01/01/2026 - 01/31/2026
12/01/2025 - 12/31/2025
11/01/2025 - 11/30/2025
10/01/2025 - 10/31/2025
09/01/2025 - 09/30/2025
08/01/2025 - 08/31/2025
07/01/2025 - 07/31/2025
06/01/2025 - 06/30/2025
05/01/2025 - 05/31/2025
04/01/2025 - 04/30/2025
03/01/2025 - 03/31/2025
02/01/2025 - 02/28/2025
01/01/2025 - 01/31/2025
12/01/2024 - 12/31/2024
11/01/2024 - 11/30/2024
10/01/2024 - 10/31/2024
09/01/2024 - 09/30/2024
08/01/2024 - 08/31/2024
07/01/2024 - 07/31/2024
06/01/2024 - 06/30/2024
05/01/2024 - 05/31/2024
04/01/2024 - 04/30/2024
03/01/2024 - 03/31/2024
02/01/2024 - 02/29/2024
01/01/2024 - 01/31/2024
12/01/2023 - 12/31/2023
11/01/2023 - 11/30/2023
10/01/2023 - 10/31/2023
09/01/2023 - 09/30/2023
08/01/2023 - 08/31/2023
07/01/2023 - 07/31/2023
06/01/2023 - 06/30/2023
05/01/2023 - 05/31/2023
04/01/2023 - 04/30/2023
03/01/2023 - 03/31/2023
02/01/2023 - 02/28/2023
01/01/2023 - 01/31/2023
12/01/2022 - 12/31/2022
11/01/2022 - 11/30/2022
10/01/2022 - 10/31/2022
09/01/2022 - 09/30/2022
08/01/2022 - 08/31/2022
07/01/2022 - 07/31/2022
06/01/2022 - 06/30/2022
05/01/2022 - 05/31/2022
04/01/2022 - 04/30/2022
03/01/2022 - 03/31/2022
02/01/2022 - 02/28/2022
01/01/2022 - 01/31/2022
12/01/2021 - 12/31/2021
11/01/2021 - 11/30/2021
10/01/2021 - 10/31/2021
09/01/2021 - 09/30/2021
08/01/2021 - 08/31/2021
07/01/2021 - 07/31/2021
06/01/2021 - 06/30/2021
05/01/2021 - 05/31/2021
04/01/2021 - 04/30/2021
03/01/2021 - 03/31/2021
02/01/2021 - 02/28/2021
01/01/2021 - 01/31/2021
12/01/2020 - 12/31/2020
11/01/2020 - 11/30/2020
10/01/2020 - 10/31/2020
09/01/2020 - 09/30/2020
08/01/2020 - 08/31/2020
07/01/2020 - 07/31/2020
06/01/2020 - 06/30/2020
05/01/2020 - 05/31/2020
04/01/2020 - 04/30/2020
03/01/2020 - 03/31/2020
02/01/2020 - 02/29/2020
01/01/2020 - 01/31/2020
12/01/2019 - 12/31/2019
11/01/2019 - 11/30/2019
10/01/2019 - 10/31/2019
09/01/2019 - 09/30/2019
08/01/2019 - 08/31/2019
07/01/2019 - 07/31/2019
06/01/2019 - 06/30/2019
05/01/2019 - 05/31/2019
04/01/2019 - 04/30/2019
03/01/2019 - 03/31/2019
02/01/2019 - 02/28/2019
01/01/2019 - 01/31/2019
11/01/2018 - 11/30/2018
08/01/2018 - 08/31/2018
07/01/2018 - 07/31/2018
06/01/2018 - 06/30/2018
05/01/2018 - 05/31/2018
04/01/2018 - 04/30/2018
03/01/2018 - 03/31/2018
02/01/2018 - 02/28/2018
01/01/2018 - 01/31/2018
12/01/2017 - 12/31/2017
11/01/2017 - 11/30/2017
10/01/2017 - 10/31/2017
07/01/2017 - 07/31/2017
06/01/2017 - 06/30/2017
05/01/2017 - 05/31/2017
04/01/2017 - 04/30/2017
03/01/2017 - 03/31/2017
02/01/2017 - 02/28/2017
01/01/2017 - 01/31/2017
12/01/2016 - 12/31/2016
11/01/2016 - 11/30/2016
10/01/2016 - 10/31/2016
09/01/2016 - 09/30/2016
08/01/2016 - 08/31/2016
06/01/2016 - 06/30/2016
05/01/2016 - 05/31/2016
04/01/2016 - 04/30/2016
03/01/2016 - 03/31/2016
02/01/2016 - 02/29/2016
01/01/2016 - 01/31/2016
12/01/2015 - 12/31/2015
11/01/2015 - 11/30/2015
10/01/2015 - 10/31/2015
09/01/2015 - 09/30/2015
08/01/2015 - 08/31/2015
07/01/2015 - 07/31/2015
06/01/2015 - 06/30/2015
05/01/2015 - 05/31/2015
03/01/2015 - 03/31/2015
12/01/2014 - 12/31/2014
06/01/2014 - 06/30/2014
05/01/2014 - 05/31/2014
03/01/2014 - 03/31/2014
02/01/2014 - 02/28/2014
12/01/2013 - 12/31/2013
11/01/2013 - 11/30/2013
10/01/2013 - 10/31/2013
08/01/2013 - 08/31/2013
07/01/2013 - 07/31/2013
06/01/2013 - 06/30/2013
04/01/2013 - 04/30/2013
03/01/2013 - 03/31/2013
02/01/2013 - 02/28/2013
01/01/2013 - 01/31/2013
12/01/2012 - 12/31/2012
10/01/2012 - 10/31/2012
09/01/2012 - 09/30/2012
07/01/2012 - 07/31/2012
06/01/2012 - 06/30/2012
05/01/2012 - 05/31/2012
04/01/2012 - 04/30/2012
03/01/2012 - 03/31/2012
02/01/2012 - 02/29/2012
01/01/2012 - 01/31/2012
發表評論
作者:
用戶名: 密碼: 您還不是博客/論壇用戶?現在就註冊!
     
評論:
淺談蒙特卡洛樹搜索(MCTS)
   


淺談蒙特卡洛樹搜索(MCTS)

1] 圍棋軟件AlphaGo的3個主要系統

最近打敗世界圍棋手李世石的圍棋軟件AlphaGo主要由以下3個系統組成:

1. 策略網絡(Policy Network):落子選擇機制,它着眼於每一步弈棋的下法。

2. 估值網絡(Value Network):局面評估機制,它注重於對全局形勢的判斷。

3. 蒙特卡洛樹搜索(Monte Carlo Tree Search,MCTS):實現圍棋這樣超高複雜博弈機制的一種隨機算法。

前兩個系統容易理解。蒙特卡洛樹搜索則有些讓人不好理解。本想看到內行的介紹文章,但這類文章一直沒有出現。故不揣冒昧,先寫一篇,以拋磚引玉。

2] 什麼是搜索樹和樹搜索?

由於棋類活動的每一步一般可以有好幾種走法,因此可以把這個思考過程描述成一棵“樹”的形狀,術語就稱為“搜索樹” [search tree],見圖:

而發現這棵“樹”中的每一步好棋,就稱為“樹搜索”(tree searching)。

簡單的棋類,如“井字棋”、“五子棋”,可以把所有能走的全部棋步都找出來,然後把對手的回應棋步也全都找出來,然後找出第3步、第4步、……,並對每步都進行評估,這樣就形成了比較正確的走法。這是人們下棋時思考的過程。想得越深、越廣,就越容易贏棋。

電腦軟件模仿人類下棋,也是採用這種方法;只是它把每個棋步都評分成數值,比較這些數值的大小。數值越大的棋步表明贏的希望越大,就成為軟件走棋的依據。

但是對於中國象棋、國際象棋和圍棋來說,這棵“樹”就太大,根也太深了,寫出這樣算法的軟件就比較難。

特別是圍棋,由於它的棋盤上有361個點之多,因此把這些棋步全部找出來,是不現實的。

由此就引入了蒙特卡洛搜索。

3] 蒙特卡洛搜索樹及其原理

蒙特卡洛樹搜索,簡單地說,就是只在全部可以走的棋步“樹”中,隨機地選取若干棋步,從中挑選出最好的那步棋走。等對方回應的棋步走出後,再繼續隨機地選取相應的棋步,重複這樣的過程;而不是找出所有可能的棋步。

因為摩納哥(Monaco)的蒙特卡洛是世界有名的賭城之一,而這樣的搜索有些像賭博那樣碰運氣,因此得名。

有人舉了一個生動的例子來描述蒙特卡洛搜索樹。

在一個密封的筐里有100個蘋果,人們每次拿出1個蘋果,目的是從筐中挑出最大的蘋果來。

人們最先想到的做法就是:隨機拿出1個蘋果,再隨機拿出另1個蘋果與它相比,從中挑出較大的那個蘋果來;然後再從筐中拿出第3個蘋果,把它與那個大的蘋果相比,挑出大的那個……。這樣重複以上的過程。

人們每次挑出的蘋果都至少不比上次的小。拿出的蘋果越多,就能找到越大的蘋果。但是除非人們挑選完所有的100個蘋果,他們無法肯定挑出了筐里最大的蘋果,但是卻能保證能挑出已經拿出來的蘋果中最大的那個。

這個挑蘋果的算法,就是蒙特卡羅樹的算法:儘量選出好的,但不能保證是最好的。

由於蒙特卡洛樹搜索僅隨機選取了某幾個棋步進行比較,因此,它走出的棋步也並非是最佳的棋步,但是卻是比較好的棋步。對AlphaGo來說,至少是可以取勝的棋步;最壞的情形,大概是能保證它不會輸的棋步。

具體反映到AlphaGo上,這就是為什麼它有時會走出一些“弱手”而讓9段高手們看不起的原因。但是高手們不了解的是,軟件走出的那些“弱”的棋步其實並非不會取勝,只是為了減少計算,它可能選擇了當時棋手們看來只是第二好、第三好,甚至第n好的棋步;只要保證它能贏棋,一步的好壞對它來說是無所謂的。

這也解釋了為什麼AlphaGo僅在幾個月前贏了2段棋手,而在幾個月後卻能以4:1贏了9段棋手李世石(第4盤中,李世石也只能說是險勝)。實際上,軟件是根據對手的棋步來相應地走棋的。對手弱,它選擇的棋步就會弱,而不是像人類棋手那樣,根據自己的水平走出自己的最好走法。遇到9段高手,它也是如此。這顯示出它“遇強則強,遇弱則弱”的特點。

蒙特卡洛算法由數學家烏拉姆(Stanisław M. Ulam,1909-1984)最早提出,再經科學天才馮·諾伊曼(John von Neumann,1903-1957)發展和完善。

烏拉姆曾利用這個蒙特卡羅方法計算裂變材料的中子擴散問題。

4] 題外話

因為AlphaGo是人寫的,因此它肯定有弱點。就是說,它並非不可戰勝的。

AlphaGo軟件的估值網絡,據報道可達13層之多;就是說,它可以看到13步棋步那麼遠。

而在開局階段,由於AlphaGo軟件採用的蒙特卡洛樹搜索的那棵“樹”太大,因此可能會犧牲掉一些搜索的深度,而達不到13層之多,以此來保證有足夠的搜索的廣度。

由此可以看出,AlphaGo的開局是比較弱的。其實這也是所有棋類對弈軟件的普遍弱點。有關資料顯示,AlphaGo這個“軟弱的”開局階段大概持續20手左右,以後隨着棋盤上的棋子越來越多,它的棋力也會越來越強。

因此,人類棋手需要在開局階段儘量找到能占優勢的棋步,而不能寄希望在中盤甚至收官階段來打敗它;或者想把局面弄複雜些來打敗軟件。

從資料來看,平常的比賽時,AlphaGo經常打開一個5x5個局部棋盤的窗口;就是說,它一般能把這25個格子裡的變化都研究得透透的了。這個水平,估計人類9段棋手是做不到的;他們可以根據經驗來大致評估雙方的棋勢,而不能把每個點(目)的各種情況都算透了。

棋類對弈軟件的全局觀較差

有人可能會說,這次AlphaGo與李世石的比賽中,感到軟件的全局觀是不錯的。其原因可能是,據說李的棋,局部計算較好,全局上面則較差。對比之下,反而是軟件更強些。

想想也能明白,畢竟整個棋盤的全局的計算量巨大,而局部的計算量則較小。

棋類對弈軟件沒有主動進攻意識

棋類對弈軟件主要根據對手的走法找出相應的棋步來應對。它們普遍缺乏主動地在某個局部挑起戰爭的意識。尤其在前段棋局時是如此。這也是由於主動挑戰需要的計算量太大,應付局面則需要的計算量小多了。

作為軟件的人類對手,就要利用軟件的這個弱點,主動挑起戰爭。

這也是李世石感到軟件在執黑時弱、執白時強的原因:先手時它不知道走什麼好;而應戰時則比較好走。

多展開幾個局部的戰爭。讓軟件不知道應該把主要精力放在哪兒。

電腦軟件大多是“一根筋”思路。它可以把事情計算得很深層,但是不善於應付多局面的事務。要至少展開2個以上的局部戰爭。

參考連接

https://www.zhihu.com/question/20254139

http://songshuhui.net/archives/94410


 
關於本站 | 廣告服務 | 聯繫我們 | 招聘信息 | 網站導航 | 隱私保護
Copyright (C) 1998-2026. Creaders.NET. All Rights Reserved.