Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

estimate win rate (pure theoretical by math computations) #26

Open
Ledenel opened this issue Dec 4, 2019 · 4 comments
Open

estimate win rate (pure theoretical by math computations) #26

Ledenel opened this issue Dec 4, 2019 · 4 comments
Labels
algorithm Fancy algorithm idea enhancement New feature or request

Comments

@Ledenel
Copy link
Owner

Ledenel commented Dec 4, 2019

Since here we could get all possible combination for win:

def _win_selections_in_tiles(self, hand: TileSet, ignore_4counts, current_state: WinPattern,

assume each invisible tile is equal probability, we could leverage multinomial distribution for given a possible combination with r tiles in the invisible set:

like wikipedia explained,
we could directly get all possible combinition probability just simply sum the pmf of each combination
here.

@Ledenel Ledenel added algorithm Fancy algorithm idea enhancement New feature or request plan Project next step (Milestone) and removed plan Project next step (Milestone) labels Dec 4, 2019
@Ledenel
Copy link
Owner Author

Ledenel commented Dec 9, 2019

for more round than r, for example draw 4 tiles to get (4s,5s) in (3*4s,2*5s,otherwise*70) invisible, we could:

  1. merge anything except (4s,5s) as otherwise condition to get a new p.
  2. enumerate all conditions:
    1*4s-1*5s 1*4s-2*5s
    2*4s-1*5s 2*4s-2*5s
    3*4s-1*5s
  3. sum up all to get possibility of (4s,5s) term.

Since P(1s,2s) is dependent to P(3s,4s) while r>2, Inclusion–exclusion Principle should be used to calculate precise probability.

but the time complicity increased to O(2^n), which is not acceptable since n could up to 100.A cleaner division or some simplified method should be applyed to allow computation.

MultiNomial equally estimation can also be adjusted by analysis other's player hand based on discarded tiles.

@Ledenel
Copy link
Owner Author

Ledenel commented Dec 9, 2019

consider that pick away tiles influence the remain tiles, we could directly use combinitions to calculate classical probability, then directly use Gamma function to get a general result for real-numbers remain tile estimation (adjust distribution by other's player hand by directly add tile expection to invisible tile)

@Ledenel
Copy link
Owner Author

Ledenel commented Dec 9, 2019

we could divide it by define "useful-tiles" (u1,u2,u3,..un), "otherwise" to get a clean division. then enumerate on u by restrition sum(ui) <= r and each ui <= invisible-ui

@Ledenel
Copy link
Owner Author

Ledenel commented Dec 10, 2019

Another idea is making this a 0-1 Knapsack Problem (counting combinitions) by mapping volumn to remain tiles to choose, mapping tiles to weights-values, add restriction below:

mactch at least a useful set lead to win (i.e. '4s5s1z' in 6s123m456789p1z7z)

this could be achieved by some common sequence dynamic programming, or something like AC-machine to represent state like

f(picking-tile, remain-volumn, useful-set-maching-state)

then apply something like O(n^3) dynamic-programming algorithms (which is acceptable since n<=136, the total tiles in mahjong) to find the answer.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
algorithm Fancy algorithm idea enhancement New feature or request
Projects
None yet
Development

No branches or pull requests

1 participant