Tag: go

AlphaGo Zero 的計算量

在 AlphaGo Zero 論文裡有提到，用同樣的硬體 (4 TPU) 可以用 89:11 碾壓 AlphaGo Master (今年年初與柯潔下的那個版本)，主要是得力於更高品質的 neural network 以及更強的選擇能力 (後面這塊應該是將兩個 nerual network 簡化為一後的好處)：

This neural network improves the strength of the tree search, resulting in higher quality move selection and stronger self-play in the next iteration.

那麼對應的問題就會冒出來了，究竟 DeepMind 花了多少時間才能訓練出這個新的 nerual network？結果吳毅成教授在 Facebook 上先估算出來了：

這邊的 TPU 對 GPU 的推估應該是基於當時 Google 在說明 TPU 的部份「An in-depth look at Google’s first Tensor Processing Unit (TPU)」：

In short, we found that the TPU delivered 15–30X higher performance and 30–80X higher performance-per-watt than contemporary CPUs and GPUs.

用 GPU 大約是 12K 顆，反推回 TPU 大約也是千顆這個數量左右。而這個數量以目前已經將 TPU 商用化的 Google 來看應該是很輕鬆，只能說有錢真好 XD：

1. 從另外一個角度看, DeepMind 僅40天就可以把 40-block 版本練起來, 換算一下, DeepMind 等於用了約12000顆 1080 Ti.

AlphaGo 與柯潔下的三盤棋，包括了雙方的講解

在 Aja Huang (黃士傑) 的 Facebook 上看到 AlphaGo 與柯潔在烏鎮下的三盤棋的講解，這次的講解除了找柯潔與樊麾以外，更重要的是直接拿了與當時相同配備的 AlphaGo 出來使用 (只要柯潔想要看某些變化 AlphaGo 會怎麼應對，樊麾都會輸入進去跑模擬)：

需要說明的是，視頻中參與覆盤的AlphaGo與烏鎮峰會比賽的版本和硬體配置(搭配4個TPU的單機版)完全一樣。希望大家享受這三盤精彩的對局，也能從這三個視頻的覆盤研究中有所收穫。祝大家觀影愉快。

關於圍棋貼目的問題...

前陣子 AlphaGo 大獲全勝後放出了五十盤自戰棋譜 (兩台 AlphaGo 自己下)，其實有件事情有點出乎大家意料，而在圍棋界被一直討論。就是在這五十盤裡，黑棋與白棋的勝率比是 12:38 (中國規則，黑棋貼 7.5 目的情況)，明顯白棋有強大的優勢。

這個 7.5 目指的是，由於黑棋先下 (先手優勢)，所以圍的地會比較多，為了彌補白棋後下的這個缺點，一般都會設計「貼目」這個規則。

交大資工的 CGI 團隊在上個月月底發了一篇論文 (參考「CGOS Whole Period Ratings for 19x19 Board」這邊的記錄，在有參加 CGOS 的團隊裡只輸新版的 Zen)，討論 value network 的新想法：「Multi-Labelled Value Networks for Computer Go」。

他們對貼目的數量做了分析：

For the training data, we label on output ?? as follows. For each self-play game, first calculate territory difference ? at the end of the game. Then, based on the Chinese rule, label 1 (win) on ?? for all ? < ?, and -1 (lose) for all ? > ?. (Note that the draw case ? = ? is ignored in this paper since the komi is not an integer normally.) For example, if black occupies 7 more points of territory than white, the ?-komi game is considered a win for all ? < 7, and a loss for all ? > 7. Thus, in this case, a 7.5-komi game is a loss, and a 6.5-komi or 0.5-komi game is a win.

這個研究完全顛覆了目前職業棋手一般的理解。目前的理解是，貼 5.5 目是黑棋優勢，貼 7.5 目是白棋優勢 (所謂的大貼目時代)。

接下來應該會有更多的研究出來，圍棋界會不會反思貼目規則呢...

zetcd：用 etcd 跑 ZooKeeper 架構

在「zetcd: running ZooKeeper apps without ZooKeeper」這邊介紹了用 etcd 當作 ZooKeeper 伺服器。程式碼在「Serve the Apache Zookeeper API but back it with an etcd cluster」這邊可以看到。

不過可以看到有不少 overhead：

但 etcd 用 Go 寫 (省下 JVM tuning？)，可能是個不錯的誘因...

用 Go 寫的 Badger

Dgraph 在推銷自家發展出來的 Badger：「Introducing Badger: A fast key-value store written natively in Go」。

標靶是 RocksDB，號稱比 RocksDB 快好幾倍：

Based on benchmarks, Badger is at least 3.5x faster than RocksDB when doing random reads. For value sizes between 128B to 16KB, data loading is 0.86x - 14x faster compared to RocksDB, with Badger gaining significant ground as value size increases. On the flip side, Badger is currently slower for range key-value iteration, but that has a lot of room for optimization.

不過我覺得有些重要的功能在 Badger 不提供，這比起來有種橘子比蘋果的感覺... 像是 RocksDB 提供了 Transaction，而 Badger 則是直接講明他們不打算支援 Transaction：

Keep it simple, stupid. No support for transactions, versioning or snapshots -- anything that can be done outside of the store should be done outside.

Linux 上跑電腦圍棋程式 (CGOS)

這邊講的不是對人下的，而是電腦之間的對弈。

目前大多數的對弈軟體會到「CGOS - A Go Server Just for Computers」這邊對弈，當然目前最紅的是一般 (人類) 正式比賽用的 19x19 棋盤，數子採用中國規則 (相當於貼 7.5 目)。

不過與常見的正式比賽比較不一樣的是採用包干制，每方限時 15 分鐘，超時就直接裁定敗，不過有個小例外：

CGOS silently adds a fraction of a second to each players clock for each move played.

要把圍棋程式接到 CGOS 上面需要兩段程式，一段是 Go Engine 本身要支援 Go Text Procotol (GTP)，另外一段是把 GTP 接到 CGOS。

前面 Go Engine 的部份，目前不少圍棋軟體都有支援 GTP，像是 Leela 或是 Ray。

後者一般會用 Python CGOS Client。

其中比較特別的是 CGOS 的帳號密碼，帳號只允許 18 個字，另外沒有帳號申請系統，第一次用什麼帳號他就自動記錄起來，之後就要用這組。

# config.cfg
Common:
  KillFile = kill.txt

# First engine
GTPEngine:
  Name = Leela090-test
  CommandLine = ./leela090-gtp.sh

  ServerHost = yss-aya.com
  ServerPort = 6819
  ServerUser = Leela090-test
  ServerPassword = mypassword

  NumberOfGames = 1

  SGFDirectory = sgf

然後建立 sgf 目錄存棋譜後，用 python bin/cgosclient.py config.cfg 跑起來。當你 touch kill.txt 後，下一盤棋就會自己結束 (預設是一直下)。

再來是裡面提到的 leela090-gtp.sh：

#!/bin/bash
exec /usr/bin/nice -n 20 $(dirname $0)/leela_090_linux_x64_opencl -g -t 8 -b 50 -q -l /tmp/leela090-gtp.log

這邊跑的是 OpenCL 版本，你也可以跑 CPU 版。其中 -g 是 GTP mode，-t 是 CPU thread 數量，-b 是 network latency penalty (避免超時)，-q 是 quiet mode，-l 是 log。

AlphaGo 又要重出江湖了

DeepMind 家的 AlphaGo 又要重出江湖了：「Exploring the mysteries of Go with AlphaGo and China's top players」。這次將會跟中國的頂尖職業棋手對弈，裡面提到三種賽制：

The summit will feature a variety of game formats involving AlphaGo and top Chinese players, specifically designed to explore the mysteries of the game together. The games will include:

  • “Pair Go” — A game where one Chinese pro will play against another...except they will both have their own AlphaGo teammate, alternating moves, to take the concept of ‘learning together’ quite literally.
  • “Team Go” — A game between AlphaGo and a five-player team consisting of China’s top pro players, working together to test AlphaGo’s creativity and adaptability to their combined style.
  • “Ke Jie vs AlphaGo” — Of course, the centerpiece of the event will be a classic 1:1 match of three games between AlphaGo and the world’s number one player, Ke Jie, to push AlphaGo to (...perhaps beyond!) its limits.

有傳言是這樣打 (目前大家都抄來抄去...)，但目前還沒看到正式的公告：

（一）5月23,25,27日 柯潔與AlphaGo三番棋：每方3小時，5次1分鐘讀秒；
（二）5月26日 時越、羋昱廷、唐韋星、陳耀燁和周睿羊5人團隊賽：每方2小時30分，保留3次1分鐘讀秒；
（三）5月26日 古力、連笑人機配對賽：每方1小時，1次1分鐘讀秒。

另外有一篇「Innovations of AlphaGo」講了不少年初 AlphaGo 連勝六十盤的對局給人類棋手的啟發。

另外 DeepMind 的 CEO，Demis Hassabis 前幾天剛好有給了一個演講，也是講了不少東西 (不過都是之前就提過的)：

這樣來安排那幾天空時間下來...

Cloudflare 因為閏秒炸掉...

Cloudflare 這次閏秒炸掉：「How and why the leap second affected Cloudflare DNS」，影響範圍包括了 DNS query 與 HTTP request：

At peak approximately 0.2% of DNS queries to Cloudflare were affected and less than 1% of all HTTP requests to Cloudflare encountered an error.

主要的原因在於 Go 的 time.Now() 不保證遞增：

RRDNS is written in Go and uses Go’s time.Now() function to get the time. Unfortunately, this function does not guarantee monotonicity. Go currently doesn’t offer a monotonic time source (see issue 12914 for discussion).

修正的方式是針對時間回朔時處理：

In this patch we allowed RRDNS to forget about current upstream performance, and let it normalize again if time skipped backwards.

應該是因為 Cloudflare 這段程式還沒遇過 leap second 造成的...

Golang 本身也出字型了...

不愧是 Google 在後面撐腰，Golang 找人設計了一整套字型，叫做「Go fonts」：

The Go fonts are divided into two sets, Go proportional, which is sans-serif, and Go Mono, which is slab-serif.

不過看了一下 monospace 的部份，有點微妙：

其他兩個也許哪天換心情來用看看好了 :o

Go 1.9 的 GC 改善

Update：被提醒後仔細看了一下，是 1.8 預設生效 (但保留選項切回來 debug)，如果沒問題的話 1.9 把舊的方式拔乾淨：

Assuming things go smoothly, we will remove stack re-scanning support when the tree opens for Go 1.9 development.

標題就不改了... 以下原文。

在「Sub-millisecond GC pauses」這邊看到的。Golang 想辦法將 GC 造成的影響降低：「Proposal: Eliminate STW stack re-scanning」。

目標是解決最大的 GC pause 來源：

As of Go 1.7, the one remaining source of unbounded and potentially non-trivial stop-the-world (STW) time is stack re-scanning.

然後拿新的解法來戰，目前初步的測試看起來可以降到 50µs (== 0.05ms)：

We propose to eliminate the need for stack re-scanning by switching to a hybrid write barrier that combines a Yuasa-style deletion write barrier [Yuasa '90] and a Dijkstra-style insertion write barrier [Dijkstra '78]. Preliminary experiments show that this can reduce worst-case STW time to under 50µs, and this approach may make it practical to eliminate STW mark termination altogether.

在「runtime: eliminate stack rescanning · Issue #17503 · golang/go」這邊可以看到進度，現在已經在 master branch 上了，看起來會在 1.9 的時候被放出來... 不過 worst case 的時間上修了 XDDD

The high level summary is that this reduces worst-case STW time to about 100 µs and typical 95%ile STW time to 50 µs (assuming, of course, that the OS doesn't get in the way and that the system isn't otherwise overloaded).

但看起來應該還是很大的效能改善，尤其是 CPU bound 的應用？