4

私はこの 1 年間、ポーカー ハンドの歴史を解析してきましたが、解析全般についてかなりのことを学びました。

私たちは正規表現から始めましたが、すぐに拡張が容易ではないことに気付きました。Ruby から C++ へと言語を飛ばして、最終的には変更しなければならないのはアルゴリズムであることに気づきました。

Boost::Spirit を手に取ったところ、元の速度の 10 倍以上のオーダーで速度が劇的に上昇するのがわかりました。その後、Java にスキップし、現在、antlr を使用して各サイトの文法を作成しています。これは間違いなくこれまでで最速の方法であり、「完全な」文法の観点から自分がどこに立っているかを正確に知ることができるため、非常に徹底的です。残念ながら、私はこれらの文法を扱うのに信じられないほどの時間を費やしてきました。

とにかく、当面の質問の背景については十分です-私が気付いていない「エキゾチックな」またはあまり知られていない解析手法はありますか? 私は、文法の字句解析/解析と、他の劣った正規表現/ループ方法しか知りません。

ポーカー ハンドの歴史に詳しくない方のために、構造がどのようなものかわかるように投稿します。

Full Tilt Poker Game #12037626529: Table durrrr (heads up, deep) - $500/$1000 -
Pot Limit Omaha Hi - 2:00:48 ET - 2009/05/05
Seat 1: durrrr ($196,456.50)
Seat 2: Gus Hansen ($65,499)
durrrr posts the small blind of $500
Gus Hansen posts the big blind of $1,000
The button is in seat #1
*** HOLE CARDS ***
durrrr raises to $3,000
Gus Hansen raises to $9,000
durrrr calls $6,000
*** FLOP *** [3d 4d 7d]
Gus Hansen has 15 seconds left to act
Gus Hansen checks
durrrr checks
*** TURN *** [3d 4d 7d] [Jh]
Gus Hansen checks
durrrr checks
*** RIVER *** [3d 4d 7d Jh] [Ah]
Gus Hansen has 15 seconds left to act
Gus Hansen checks
durrrr has 15 seconds left to act
123stayfree (Observer): GUS I NOW BRING U LUCK
durrrr bets $7,600
Gus Hansen has 15 seconds left to act
Gus Hansen has requested TIME
Hernandez777 (Observer): Gus has the super-duper nuts
Gus Hansen calls $7,600
Podobed45 (Observer): fluuuuuuuuuush
*** SHOW DOWN ***
durrrr shows [Kc 3s Qd As] two pair, Aces and Threes
Gus Hansen mucks
durrrr wins the pot ($33,199.50) with two pair, Aces and Threes
*** SUMMARY ***
Total pot $33,200 | Rake $0.50
Board: [3d 4d 7d Jh Ah]
Seat 1: durrrr (small blind) collected ($33,199.50)
Seat 2: Gus Hansen (big blind) mucked

情報を収集する他の方法 (スクリーンスクレイピングや dll インジェクションなど) についてはよく知っていますが、ハンド履歴を構造化データに変換する必要性がまだ残っているため、次のような情報を取得する方法のみを調べています。正規表現/文法...

何か見つからない場合は、文法を ocamllex/ocamlyacc で書き直そうと思います。

アップデート

fyi: 正規表現の速度は ~60 ハンド/秒でしたが、文法は 600 ハンド/秒を処理していました... データがすべて整理された後、ハンド全体が xml に変換されます... 20 ～ 30 の正規表現が必要です (最後のカウント) 解析したいサイトごとに....文法側の各サイトには、非常に多くのレクサー/パーサールールを備えた独自の文法があります(ただし、コードサイズはまだ小さいです)

私はドラゴンブックを持っていて、それを読んでいます-これにより、ocamllex/ocamlyacc を使用することに興味がなくなりました....ここでのゲームの名前はスピードです..

4

8 に答える 8

6

エキゾチックなものを探しているので、Vaughan Pratt の Top Down Operator Precedence に関するこの記事を読んでください...

http://javascript.crockford.com/tdop/tdop.html

于 2009-06-02T18:45:18.253 に答える
4

パーサー コンビネーターは、Haskell などの関数型言語でパーサーを構築するための非常に一般的な方法です。

于 2009-06-02T17:57:59.973 に答える
3

速度を最大化することを検討している場合は、ANTLRよりもOcamlYacc/FsYaccを使用する方がよい場合があります。OcamlYaccはLL（1）パーサーを作成します。これは通常、ANTLRスタイルのLL（*）パーサーよりもパフォーマンスが優れています（私が間違っている場合は、誰かが私を修正できます）。 [編集して追加：]誰かが私を修正したようです：OCamlYaccはLALR（1）パーサーを生成します。OcamlYaccパーサーがANTLRパーサーよりも高速であるかどうかは自信を持って言えません。

OCaml / F＃はDSLを構築するのに非常に優れた言語であり、私の意見では、Javaよりもはるかに適切です。これは主に、ユニオンデータ構造として表されるASTを作成してトラバースするのが途方もなく簡単だからです。F＃でSQLを解析する方法を示すこのチュートリアルをお勧めします。

于 2009-06-02T18:28:04.760 に答える
2

あなたが本当にやりたいことはパーサーをいじることなのか (確かに楽しいし、私自身も好きなことです)、それともポーカー ボットで実際に仕事をしたいのか自問する必要があります。ほとんどの場合、エキゾチックな解析手法は、必要なものに対して過剰です。簡単で使いやすいパーサーを備えた高速な言語を選択するだけです。おそらく、ストレート C + フレックスで 10,000 ハンド/秒を処理できるはずです。または、ocamllex + ocamlyacc で十分です。コードを hadoopify する必要がある場合は、何か間違っていると思います。解析速度ではなく、ネットワーク遅延が実際のボトルネックになるはずです。これを実行しているマシンは何ですか？

もう 1 つの方法は、パーサー ジェネレーターを使用して解析テーブルを自動生成し、それを手動で最適化するか、NFA から手動で最適化することです (おそらくあまり節約できず、プログラマーの時間のトレードオフはおそらく価値がありません)。コンビネータの解析は遅くなる可能性があります。

平均して、同等の能力を持つ特定の文法では、LL は LALR よりも遅くなります。特に、ポーカー ハンドが実際に LALR パーサーによって解析可能である場合、bison/byacc + flex は常に ANTLR ハンドを打ち負かします。godi + ocamlbuild で作業するのは猛烈な雌犬と半分ですが、個人的には menhir にかなり満足しています。

――ニコ

于 2009-06-12T17:11:13.267 に答える
1

Recursive Descent Parsingがうまくいくかもしれません。非常にカスタマイズ可能です。yacc/antlr より少し遅いかもしれませんが、十分に速いかもしれません。基本的な考え方: すべての文法規則を関数としてエンコードします。

于 2009-06-02T18:37:59.750 に答える
1

ドラゴンブックを読む: http://www.amazon.com/Compilers-Principles-Techniques-Alfred-Aho/dp/0201100886

字句解析と構文解析を詳細にカバーしています (他のトピックの中でも)。これを使用して、解析しようとしている「言語」を理解して、最適な方法を決定することができます。

于 2009-06-02T18:12:08.763 に答える
1

ウィキペディアには、パーサーの種類に関する優れた概要があります。 http://en.wikipedia.org/wiki/Parser

パーサー ジェネレーター ツールの比較はこちら: http://en.wikipedia.org/wiki/Comparison_of_parser_generators

GLRは言語のあいまいさを扱うため、あまり知られていない興味深い方法だと思います。

于 2009-06-02T18:13:41.897 に答える