Re: [惡搞] 懸賞踩地雷 AI！

[godfat (godfat 真常)]

  又過了一段時間，報告一下目前狀況... orz

※ 引述《AmosYang (LetMeGoogleThatForYou)》之銘言：
: 可以參考 http://en.wikipedia.org/wiki/Clause
: clue 譯作線索，在這個 context 底下的確代表著「算出地雷位置的線索」
: clause …中文我不知道該譯成什麼，比 clue 抽象，
: 可以算是完整 sentence 的 building block
: 哪個比較正確…我也不知道，就我的語感來判斷我是選 clause
: 但語感這種東西我也不知道該怎麼解釋 XD

  那頁我前後翻了很多次，但仍然不知道為什麼要用在這個地方。
  不過繼續寫下去後，忽然間就可以體會為什麼要叫 clause,
  因為 clause 跟 clause 可以混合而成新的 clause..
  但最後我還是決定繼續叫 clue, 原因是 clue 寫起來比較短，而且：

    type Choices = List[(Probability, Tile)]
    type MineMap = TreeMap[Tile, MineSize]
    type TileSet = TreeSet[Tile]
    type ClueSet = TreeSet[Clue]

  看起來很整齊，我不想改 XD Tile 的名字則出自 tile-based game.

: 能省下來的計算在於
: 1. C1 * C2 與 C2 * C1 的結果會一樣，所以每個 pair 只需要作一次
: 2. 場面上可以會有很多 clauses, 其實 clause 之間的關連性很 sparse
:    所以這裡也能省下一些
:    例如說: C1: 0 <= { Cell1, Cell2, Cell3 } <= 3
:    唯一要跟 C1 計算重疊機率的，就只有
:    「任何含有 Cell1, Cell2, Cell3 的 clause」
:    這就可以省下不少

  我猜你所提到可以省下的，我原本就沒有算了，之所以提到 DP 是因為
  （我不熟 DP..）我的計算方式在每個 tile/cell/block 之間沒有共享任何
  資訊，但感覺應該有些計算是可以共用的。

  另外我也猜你的作法實際上跟我不太一樣，雖然 clause 這邊真的很像，
  而且我也愈寫愈像了.... 但或許有個決定性的關鍵？不確定你的程式怎麼寫，
  不過我寫出來的（想寫出來的，還沒完成...） clause 減法似乎不會套在
  不是 subset 的狀況。也就是假設 C1 - C2, 則 C2 必然是 C1 的 subset.
  如果 C2 不是 C1 的 subset, 則表示程式有 bug...

  所以我的 min/max 計算不需要那麼複雜（雖然我還是寫下去了，
  因為想說這種性質應該寫在呼叫減法的地方，而不是減法本身）

: 我覺得 DP 不會有太大有效用，因為要建表的話，最後整個表會非常 sparse
: 且這個表的 index 會很噁心，省下的時間說不定正好與查表的時間抵消 XD
: 我覺得在上述兩點就能省下至少 50% 的計算
: (最後這段看不懂是正常的 XD 這裡自己寫過一次就懂了)

  我居然還沒寫完 >< 這幾天架構改來改去的...... 希望這個週末能專心
  寫到一個段落，merge 回 master @@

--
#!/usr/bin/env ruby      [露比] /Programming (Kn|N)ight/            看板《Ruby》
# if a dog nailed extra legs that          http://www.ptt.cc/bbs/Ruby/index.html
# walks like an octopus, and                            Welcome ~Ruby@ptt~
# talks like an octopus, then       ◢█◣            http://www.ruby-lang.org/
# we are happy to treat it as       █                http://www.ruby-doc.org/
# if it were an octopus.            ◥  ◤            http://www.rubyforge.org/

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 220.135.160.129
推 tkcn:我自己是打算長期抗戰慢慢寫，不知道其他人怎麼打算?  :p
→ AmosYang:我打算…週末好好睡一覺;接下來工作會一路忙到11月底 orz
→ AmosYang:LolAI v0.5 source code: http://goo.gl/SP00
→ AmosYang:關於 clause 的計算…有興趣可以看 ↗ :D
→ wendly777:目前沒有靈感中，經過3天努力，勝率只比前一版多2~3%
→ godfat:感謝 source code, 等我寫完後再細看 XDXD