[BridgeBidding] Add docs

harukaki commented 1 year ago

日本語でブリッジの説明文を書く

[x] Observation
707
[x] Action
- [x] table
[x] hash table of dds results
192
- [x] example
[x] how to duplicate
771
[x] How to prepare hash table
- [x] Download hash table from google drive
- [x] Create hash table by yourself
[x] reference

harukaki commented 1 year ago

Observation

We follow the observation design of `[Lockhart+20]`, OpenSpiel. more details #889	Index	Description
`obs[0, 4]`	Vulnerability
`obs[4, 8]`	Per player, did this player pass before the opening bid?
`obs[8, 20]`	Per player played bid, double, redouble against 1♧
...	...
`obs[416, 428]`	Per player played bid, double, redouble against 7NT
`obs[428, 480]`	13-hot vector indicating the cards we hold

Action

それぞれのaction `{0, ..., 37}` が`{ Pass, Double, Redouble, 1♧, 1♢, 1♡, 1♤, 1NT, ..., 7♧, 7♢, 7♡, 7♤, 7NT}`を表す	Index	Description
`0`	`Pass`
`1`	`Double`
`2`	`Redouble`
`3, ..., 7`	`1♧, 1♢, 1♡, 1♤, 1NT`
...	...
`33, ..., 37`	`7♧, 7♢, 7♡, 7♤, 7NT`

Hash table of dds results

Bridge AIの先行研究[Rong+19], [Gong+19], [Tian+20], [Lockhart+20]にならい、BridgeBiddingはContract BridgeのBiddingフェーズのみに着目した環境である。そのためdds (Double Dummy Solver)の結果を使用することで、BridgeのPlaying部分を近似している。これを実現するにあたり、本環境では[Tian+20]にならい、生成したhandの配り方に対して事前にddsの結果を計算したdatasetを読み込む実装となっている。

handの配り方とddsの結果を組みにしたdatasetをhash tableとして保存し、使用する。デフォルトの設定では、カレントディレクトリ内のdds_hash_table.npyにhash tableを配置する必要がある。

import pgx

env = pgx.make("bridge_bidding) # You need to place the hash table in `dds_hash_table.npy`.

また、BridgeBiddingを直接呼び出すことで自由にhash tableのpathを指定できる

from pgx.bridge_bidding import BridgeBidding

env = BridgeBidding("path")  # You can place a hash table on any path

また、hash tableの詳細は以下である。 hash tableはnpyファイルで保存されたものであり、hash_keysとhash_valuesのTupleになっている。hash_keysがhandの配り方を、hash_valuesがそれに対するddsの結果を格納したものである。hash_keys、hash_valuesの各要素keyとvalueはそれぞれ4次元のjnp.int32配列で表現されている。そのため、handとddsの結果の組み合わせの個数をNとするとhash_keys = (N, 4)、hash_values = (N, 4)のjnp.int32の配列となる。

keyは各Suit{♤, ♡, ♢, ♧}において各Cardが{N, E, S, W}のどのPositionに配られたかを表した整数列を13桁の4進数とみなし、各Suitにおいて10進数変換した4つの整数を持つ配列である。 valueは各Position{N, E, S, W}において、ddsで計算した各Denomination {♧, ♢, ♡, ♤, NT}でとれるTrick数(0以上13以下)の整数列を5桁の16進数と見なし、各Positionにおいて10進数変換した4つの整数を持つ配列である。

hash tableの例がpgx/tests/asset内のcontractbridge-ddstable-sample100.csvとdds_hash_table.npyにある。

`contractbridge-ddstable-sample100.csv` 100個のhandの配り方とddsの結果の組み合わせが保存。ファイルの内容は以下の表である。	Index	Description	Format
`0`	handの配り方	`PBN format`
`1, ..., 20`	dds results	`N (♧, ♢, ♡, ♤, NT) E (♧, ♢, ♡, ♤, NT) S(♧, ♢, ♡, ♤, NT) W (♧, ♢, ♡, ♤, NT)`

dds_hash_table.npy 上記のdatasetから作成したhash table

例えば、`contractbridge-ddstable-sample100.csv`、`dds_hash_table.npy`の先頭データは以下となる。	Description	Content
csv data	`N:J92.J76.K72.9432 AKQ6.84.J863.T65 87543.KQ9532..K7 T.AT.AQT954.AQJ8,1,1,6,4,1,11,12,6,8,9,1,1,7,5,1,10,12,6,8,9`
hash key	`[19556549 61212362 52381660 50424958]`
hash value	`[ 71233 771721 71505 706185]`

また、BridgeBidding.initでは指定したhash tableからランダムに一つのデータが使用される。 https://github.com/sotetsuk/pgx/blob/b7009f9ea9a9c1cd9257073b53bb59f9b71b77a1/pgx/bridge_bidding.py#L111-L113

How to prepare hash table

1. Download hash table from Google Drive

我々が用意したdds resultsのdatasetならびにhash tableをGoogle Driveで公開している。以下のurlからダウンロードできる。 https://drive.google.com/file/d/1eQAsgJVyiTSSOK78L51UL09YI6Z2jI-3/view?usp=share_link dds_results.zip (202 MB) の内容は以下。	File Name	Description
`bridge_bidding_dds_results_2500000.csv`	Dataset of 3,000,000 combined hand and dds results	337 MB
`dds_hash_table_2000000.npy`	Hash table with the first 2,500,000 of the above data set for training	80 MB
`dds_hash_table_500000.npy`	Hash table with the last 500,000 of the above data set for evaluation	16 MB

ダウンロードしたnpyファイルはBridgeBiddingクラスにそのまま読み込ませることができる。

2. Create hash table by yourself

ランダムに各Position (NESW)に対するhandの配り方を生成し、それに対するddsの結果を計算する。ddsの計算には以下を使用することができる
- C++で実装されたdds
- 上記のPythonラッパー

handの配り方からkeyを作成する

handの配り方から各Cardが`{N, E, S, W}`のどのPositionに配られたかを表す52次元の配列を作成する。	Name	Symbol	Int
Card	`{♤A, ♤2, ..., ♤J, ♤Q, ♤K, ♡A, ..., ♡K, ♢A, ..., ♢K, ♧A, ..., ♧K}`	`{0, ..., 52}`
Position	`{N, E, S, W}`	`{0, 1, 2, 3}`

52次元配列を各Suitの13要素ずつの4つに分け、それぞれを13桁の4進数とみなす。
4つの数を10進数に変換し、4次元のnp.int32配列に保存する。

Example

Phase	Content
hand	`N:J92.J76.K72.9432 AKQ6.84.J863.T65 87543.KQ9532..K7　T.AT.AQT954.AQJ8`
i	`[1 0 2 2 2 1 2 2 0 3 0 1 1 3 2 2 1 2 0 0 1 2 3 0 2 2 3 0 1 3 3 1 0 1 3 3 1 3 0 3 0 0 0 1 1 2 3 0 1 3 3 2]`
ii	`[[1 0 2 2 2 1 2 2 0 3 0 1 1] [3 2 2 1 2 0 0 1 2 3 0 2 2] [3 0 1 3 3 1 0 1 3 3 1 3 0] [3 0 0 0 1 1 2 3 0 1 3 3 2]]`
iii	`[19556549 61212362 52381660 50424958]`

ddsの結果からvalueを作成する
1. ddsの結果を各Positionの5要素ずつの4つに分け、それぞれ５桁の16進数とみなす。
2. 4つの数を10進数に変換し、4次元のnp.int32配列に保存する。
Example

Phase Content

dds results 1,1,6,4,1,11,12,6,8,9,1,1,7,5,1,10,12,6,8,9

i [[ 1 1 6 4 1] [11 12 6 8 9] [ 1 1 7 5 1] [10 12 6 8 9]]

ii [ 71233 771721 71505 706185]
datasetの全てのデータから作成したkey、valueをそれぞれ結合したhash_keys、hash_valuesのtupleをnpyファイルに保存する。
保存したファイルをBridgeBiddingクラスに読み込ませる

Phase	Content
dds results	`1,1,6,4,1,11,12,6,8,9,1,1,7,5,1,10,12,6,8,9`
i	`[[ 1 1 6 4 1] [11 12 6 8 9] [ 1 1 7 5 1] [10 12 6 8 9]]`
ii	`[ 71233 771721 71505 706185]`

How to duplicate match

コントラクトブリッジでは手札の配り方による不公平をなくすためduplicate matchと呼ばれる対戦方式がある。duplicate matchでは一度対戦した後、同じ手札の配り方に対してPositionを入れ替えて再度対戦する。 BridgeBIdding環境を用いてduplicate matchを行うための実装をpgx.experimenatal.bridge_bidding内のduplicate_stepで提供する。duplicate_stepをBridgeBidding.stepの代わりに使用することでduplicate matchを実現できる。ただし、いくつか注意点がある。

duplicate_stepにはBridgeBidding.stepにはなかった引数・返り値がある。
- has_duplicate_result : 最初の対戦が終了したか記憶しておく配列
- table_a_reward : 最初の対戦のrewardを記憶しておく配列
duplicate_stepでは2つの対戦が終了した時に、state.rewardが変更される。rewardは二つの対戦結果から計算されるIMPが与えられる。

import pgx
from pgx.experimental.bridge_bidding import duplicate_step
env = pgx.make("bridge_bidding")

init = jax.jit(jax.vmap(env.init))
duplicate_step = jax.jit(jax.vmap(duplicate_step)) 

N = # You need to determine the number of games to run in parallel
key = jax.random.PRNGKey(0)
key, subkey = jax.random.split(key)
keys = jax.random.split(subkey, N)

state: pgx.State = init(keys)

has_duplicate_result = jnp.zeros(N, dtype=jnp.bool_)   # Array to remember if the first match is over
table_a_reward = state.rewards  # Array to store the reward of the first match

while not state.terminated.all():
    key, subkey = jax.random.split(key)
    action = # You need to implement which actions you take
    state, table_a_reward, has_duplicate_result = duplicate_step(
        state, action, table_a_reward, has_duplicate_result
    )