9

バックグラウンド

ここhttp://www.ericharshbarger.org/dice/#gofirst_4d12で説明されているように、「Go First」ダイスは、それぞれに固有の番号が付けられた 4 つのサイコロのセットです。

  • 2 つ以上のサイコロを振っても引き分けになることはありません。
  • セット内の他のダイスに対して振られたダイスは、そのダイスに対して「勝つ/負ける」可能性が等しくなります。

上記の 4 つのサイコロの番号は次のとおりです。

DICE COUNT: 4
FACE COUNT: 12
D1: 1,8,11,14,19,22,27,30,35,38,41,48
D2: 2,7,10,15,18,23,26,31,34,39,42,47
D3: 3,6,12,13,17,24,25,32,36,37,43,46
D4: 4,5, 9,16,20,21,28,29,33,40,44,45

（経由）

質問

私は数学が苦手です。私は困惑しています。上記の情報を考慮して、サイコロの数を指定して整数 (「サイコロ」) のリストを生成できるようにしたいと考えています。そのため、出力例は次のようになります (フォーマット済み、python コンソール):

    >>> generate_dice(players=4)
    [[1,8,11,14,19,22,27,30,35,38,41,48],
     [2,7,10,15,18,23,26,31,34,39,42,47],
     [3,6,12,13,17,24,25,32,36,37,43,46],
     [4,5,9,16,20,21,28,29,33,40,44,45]]

ここでの側面の数は、他の例と一致するため、例としてのみ選択されています。それぞれのサイコロの「公平さ」こそが、まさに私が求めているものです。

これは宿題ではないことを保証します。これはただの根っからのオタクで、私を放っておくわけにはいかない一見些細なパズルに悩まされています...そして、何らかの理由で、私はそれを正しく理解できないようです.

ここには比較的簡単な数学と基本的なアルゴリズムが含まれていると確信しており、それが私が探しているものです。これが明らかな場合、どの用語を検索すればよいですか? 私にとって、そうではないからです。

理想的には、解決策は Python であるでしょうが、私は PHP、Javascript、Ruby の一部も十分に読むことができます。

4

2 に答える 2

5

これは（計算的に）難しい問題です。最初に見えるかもしれませんが、各サイコロの期待値が同じであることは十分ではありません (奇妙なことに、あなたが示した例ではそうです)。各サイコロ要素の内積のすべてのインスタンスの 50% で、各サイコロが「勝つ」必要があります。

数学者があなたが「手作業で」与えた例を生成したと記事が言及しているという事実は、次のブルートフォースアプローチを提案するのを少し快適にします:

import itertools

nplayers=4
nsides=2
max_number=8

assert nplayers*nsides <= max_number
assert nsides % 2 == 0 #otherwise x^x (dot product) is not even, so half_wins_fairness always fails

iterations=[]
def half_wins_fairness( dice1,dice2 ):
    dice1_wins= map( lambda x: x[0]>x[1], itertools.product(dice1,dice2) )
    dice_wins_prob= float(sum(dice1_wins))/len(dice1_wins)
    #probs.append(dice_wins_prob)
    return dice_wins_prob==0.5

def fair( all_dice ):
    all_fair= True
    for d1,d2 in itertools.combinations( all_dice, 2):
        if not half_wins_fairness(d1,d2):
            all_fair=False
    return all_fair

for i,dice_pattern in enumerate(itertools.permutations(range(max_number), nplayers*nsides)):
    #cut dice pattern into dices
    dice= [dice_pattern[p*nsides:(p+1)*nsides] for p in range(nplayers)]
    if fair(dice):
        print dice
        iterations.append(i)

def discrete_derivative(l):
    last=0
    for i,x in enumerate(l):
        tmp= x
        l[i]=x-last
        last=tmp

#discrete_derivative(iterations)
#import pylab
#pylab.plot(iterations)
#pylab.show()

ここでの複雑さは n^n であるため、これだけでは、nplayers と nsides の数が非常に少ない場合にのみ問題を解決できます。ただし、コメント行のコメントを外すことで、内積反復に沿ったサイコロの公平性のプロットを調べることができます。これには多くのパターンがあるようであり、いくつかのヒューリスティックを使用してこの検索を高速化できることを示唆しています。一般解を見つけます。

編集

グラフを改善するためにコードを変更しました。誰かがパターンを見つけることに特に長けている場合に備えて、ここにいくつかの写真があります.

nplayers=2, nsides=2, max_number=8 nplayers=2、nsides=2、max_number=8 nplayers=2, nsides=4, max_number=8 nplayers=2、nsides=4、max_number=8 nplayers=4, nsides=2, max_number=8 nplayers=4、nsides=2、max_number=8

いくつかの最初の観察:

  1. それは対称的です
  2. max_number % (nplayers*nsides) == 0 の場合、「最もクリーンな」グラフが生成されるようです
于 2012-09-08T21:53:48.233 に答える
0

記録のために、この回答にcodegolfは、少なくともサイコロの面の数が偶数である場合はいつでも機能するように見える単純なアルゴリズムがあります: https://codegolf.stackexchange.com/a/7238/5376

def generate_dice(count, sides = 12):
  dice = []
  for i in range(count):
    dice.append([])

  value = 0
  for sindex in range(sides):
    if sindex % 2:
      for dindex in range(count):
        value += 1
        dice[dindex].append(value)
    else:
      for dindex in reversed(range(count)):
        value += 1
        dice[dindex].append(value)
  return dice
于 2012-09-09T01:29:44.520 に答える