Dice Calculator thingie. - Instant Kingdom

GAMES ABOUT US DRIFTMOON NOTRIUM FORUM

Forum » Dice Calculator thingie.

Dice Calculator thingie.

Narvius 15 years ago

I did maed dice throw probability calculator, in Java.
The pretty random limits are 8 for dice and 40 for sides. (Note to myself: Replace with warning in the future.)
Output to out.txt in the same folder as the app.
Has nifty progress bar for the bigger calculations.

<a class="postlink" href="http://www.box.net/shared/sffg8ax8lp">http://www.box.net/shared/sffg8ax8lp</a>

E_net4 15 years ago

Yay, Java.

I've yet to be taught in the ways of Java forms and graphics. I'm a bit tired of using the same console, and having a GUI would increase capabilities.

And uh, I wonder if you could hand us the source code.

Narvius 15 years ago

Nau problem, here ya go: <a class="postlink" href="http://www.box.net/shared/jpkuk8vy5c">http://www.box.net/shared/jpkuk8vy5c</a>
(whole projects structure, ready for Eclipse project importage.)

Also, once I finish my other Java thingy I'm doing at the moment (kind of Snake clone with full rotation, actually 98% done, playable and so on) and it's published on my school's homepage I can show you the source, there's custom graphicsing on java applets.

And, when it comes to graphics in applications, this might be interesting: <a class="postlink" href="http://www.box.net/shared/e3loorxrn5">http://www.box.net/shared/e3loorxrn5</a>
You have to compile it yourself, though :3

Amarth 15 years ago

Eh. There's no way this has to run so slowly. I'll think about it for a while (might not be today because I have more pressing matters) and present my own Java code.

Narvius 15 years ago

I'm pretty sure there is a formula for this, but at the moment the only way I could do it is iterating the hell out of it.
Also, once it I made it work I didn't clean it up, except console output (which in fact speeded it up a *LOT*). So, yeah, it's surely possible to make it work faster.

[Edit]
I replaced that messy double for-loop that makes the calculations with one clean while-loop.
It is slower. Wtf.

[Edit 2]
A little cleanup. It's faster now, but still blunt iteration.
<a class="postlink" href="http://www.box.net/shared/x5agc3tt5i">http://www.box.net/shared/x5agc3tt5i</a>

Anonymous1157 15 years ago

Is there any chance you can get it multithreaded to speed it up? I would notice.

Also, I had it compute 8d40s, and it sorta hung there. It never wrote the result to file, but it held at 100% for ten minutes.

Narvius 15 years ago

Uhm, oh.
I'll look into it (it probably has to do with integers going out of range.).

It's multithreaded! The calculations are all done in another thread, so the progressbar can still be actualized

Anonymous1157 15 years ago

"Narvius" said:
Uhm, oh.
I'll look into it (it probably has to do with integers going out of range.).

It's multithreaded! The calculations are all done in another thread, so the progressbar can still be actualized

That's not quite what I meant about multithreading, but I like your sense of humor. What I meant is splitting the work in two, so ex: thread one is updating the GUI, thread two gets the first 2-160 possible results in 8d40s and thread three gets 161-320 (or whatever method is more efficient).

Anyhow, I ran a few values =< 8d10s and they all worked fine. Now I've run 8d40s and it's hung again. I'll let it run for a bit longer and see if anything happens. (Oh, and when I said it stood there for ten minutes, I meant that I decided to forcibly kill it after ten minutes.)

Narvius 15 years ago

Hm... I could split it up thread-wise for 4+ dice.
Interesting idea.

That's why I suspect it has something to do with integer max values...
In the code, I have a variable "calculationsDone" (integer), which is incremented with every cycle.
It is compared to Sides^Dice. While Sides^Dice *can* go beyond integer max, calculationsDone cannot -> The calculations will repeat endlessly.
Previously I've been checking whether all dice are at max (I'm iterating: [example is 4d4]
1111
1112
1113
1114
1121
1122
1123
1124
...
4444), but I thought it'd increase the speed if it wouldn't do that check.
Now that I think of it... I know how :3 Will post tomorrow.

Anyhow, I'll call it a day for today and go to sleep. Good night to you all :3

Anonymous1157 15 years ago

It just occured to me that you might even eventually be able to use the probability data to generate a very fair dice roll from the same program. It would have a practical purpose that could be used for forum games! (Yay)

... Oh, and I have it hanging at 8d20s now.

Amarth 15 years ago

Integer.MAX_VALUE is 2147483647, smaller than 40^8 or 20^8, so yeah.

MageKing17 15 years ago

"Narvius" said:
In the code, I have a variable "calculationsDone" (integer), which is incremented with every cycle.

Now, I haven't seen the source code, and I know very little about Java, but why?

"Narvius" said:
Previously I've been checking whether all dice are at max (I'm iterating: [example is 4d4]
1111
1112
1113
1114
1121
1122
1123
1124
...
4444), but I thought it'd increase the speed if it wouldn't do that check.
Now that I think of it... I know how :3 Will post tomorrow.

Anyhow, I'll call it a day for today and go to sleep. Good night to you all :3

What? Why would you want or even need to iterate through every combination? Have I missed the purpose of this program?

Narvius 15 years ago

I keep track of the calculationsDone for the progressbar. It doesn't adjust itself :3

It iterates through every combination because I hadn't have another idea on how to do it. It iterates through every combination, and keeps track what sums came out (the x in y parts in the out.txt are an effect of that).

ANYWAYS. Today I was bored at school (maths.), and nothing motivates more than boredom, ambition and you guys taken together. So, I made up a formula that makes the iterations unnecessary. It's not fully perfected, and I need to correct it a little, but it's generally there. It will make the thing much faster, I hope. It works for <= 4 dice. If I manage to universalize it, yay for me. I can't really test the speed on such small calcs, though :/

It's a little brainbreaking, so I'm taking break for the moment, but soon I'll be done.

Anonymous1157 15 years ago

"Narvius" said:
I can't really test the speed on such small calcs, though.

I hold the record for the slowest laptop owned and regularly used by a Monkkonen.net forum member. Just release it if it seems to work and I'll tell you if it's faster.

E_net4 15 years ago

Now that I think of it, using another language rather than Java would definitely make it faster.

Narvius 15 years ago

Yeah, probably.
But I like it. :3

I think I should turn back to C# for some time again.

Anonymous1157 15 years ago

This could be my 6502 Assembly "Hello World" when I get around to it, now that you mention it. *Holds onto a copy of the source*

... And yes, some flavor of C would be much faster. Something is of concern, however: Is it physically possible to compile C# without automatically requiring .NET? I'd still want to do your speed tests for low-end hardware if you rewrote this calculator, but I want it to run on Win98. (I could still do it if it only needed .NET 1.x, I suppose.)

E_net4 15 years ago

I thought of Linoleum myself. It's faster than C.

Narvius 15 years ago

Eh, screw it. Since I'll be forced to write fucktons of C++ in the near future (note to myself: never ever again tell somebody about my l33t program0rzing skills), I might as well try converting it into that archaic language.

[Edit]
Hey, Ville, turn censoring off please :3 It's not like we're [censored]ing twice every two words

MageKing17 15 years ago

"Narvius" said:
Eh, screw it. Since I'll be forced to write fucktons of C++ in the near future (note to myself: never ever again tell somebody about my l33t program0rzing skills), I might as well try converting it into that archaic language.

[Edit]
Hey, Ville, turn censoring off please :3 It's not like we're [censored]ing twice every two words

That's actually a user preference. I actually see "f***tons" without the stars, if you know what I mean.

Anonymous1157 15 years ago

I completely forgot about Linoleum! Shame on me, I just prolonged the NV curse or something.

C++ would actually be very nice. My father wants me to learn it, and something that isn't a stupid Hello World to play with that actually does something interesting would be helpful.

... You can turn off the censor? Censording brilliant, let's do it. *Changes settings*

Narvius 15 years ago

"Anonymous1157" said:
*Changes settings*

Indeed, *Changes settings*.
Yes, I will do convert it, but, I'm pretty busy right now.
School :/

E_net4 15 years ago

I'm also tired of not knowing what's behind the censors. Besides, I'm not a kid anymore.
*changes settings*

So, can we say Linoleum ftw?

Narvius 14 years ago

Today I had a kind of enlightenment (after spending a whole school lesson ignoring the teacher and scribbling incomprehensible-to-anyone-but-me notes - I heard they call this a "fey mood"), and wrote a whole new algorithm in Ruby.
It now runs in 8 seconds for 50d50 on my computer.

def diceCalc(number, sides)
	current = Hash.new
	current[number] = 1
	number.times do |iteration|
		new = Hash.new
		new.default = 0
		current.each_pair do |key, value|
			0.upto(sides - 1) { |i| new[key + i] = new[key + i] + value }
		end
		current = new
	end
	return current
end

This doesn't include the full functionality of my Java implementation (GUI, full analysis output to file), it just calculates and returns it in a Hash mapping ints (rollable value) to ints (# of occurences)
But it's still so much more awesome.

Basically, the idea came from data trees and one of the hunches was how J (a pretty cryptic language I dabbled in a few months back) displays multidimensional arrays. Steven Wolfram's "A New Kind Of Science" did help too (he, among other things, writes about substitution systems there).
This one is... heavily? optimized, though, so it's not really clear what is happening (unless you spend some time on it).

Let's assume x dice y sides each (xdy).
We start with this here (practically zero-dimensional) array: [x]. For every xdy, x is the minimal obtainable value; you cannot roll 2 with 3d4.
What I'm doing with the algorithm is, at every step I'm replacing every element z in the array with [z, z+1, z+2, z+3... z+y-1], so for 3d4 it would look like this:
[3]
[3, 4, 5, 6] - effectively 1d4 + 2
[[3, 4, 5, 6], [4, 5, 6, 7], [5, 6, 7, 8], [6, 7, 8, 9]] - effectively 2d4 + 1
[[[3, 4, 5, 6], [4, 5, 6, 7], [5, 6, 7, 8], [6, 7, 8, 9]], [[4, 5, 6, 7], [5, 6, 7, 8], ...]...] - effectively 3d4

This effectively (yes, I overuse that word) simulates a data tree.
Now [amount of occurences] / [y ^ x] is the probability of that roll occuring.

This concludes the core algorithm.

I thought it would be a pretty memory-eating algorithm, after all it would store millions of values for higher input (which inevitably is the first thing everyone tries out...), so I used a hashtable storing the amount occurences of each value, so the maximum amount of values stored for xdy is (2 * (x - 1) * y) - or something like that (ie. 4900 for 50d50 - two values for each number between 50 and 2500 both inclusive).
What happens for 3d4:

{3 => 1}
{3 => 1, 4 => 1, 5 => 1, 6 => 1}
{3 => 1, 4 => 2, 5 => 3, 6 => 4, 7 => 3, 8 => 2, 9 => 1}
{3 => 1, 4 => 3, 5 => 6, 6 => 10, 7 => 12, 8 => 12, 9 => 10, 10 => 6, 11 => 3, 12 => 1}
(equivalent of what I wrote a few lines earlier in the form of arrays - see? Takes much less numbers to store).

This approach is probably slightly slower, but this doesn't make much of a difference for smaller input, and EXTREMELY cuts the memory cost for larger input. Also, it makes post-processing (ie. actually using the data) easier, because it already is stored in a usable form.
Also, this being Ruby, which allows numbers beyond Int.MAX (although it calculates these slower) the algorithm is much more graceful.

I'm pretty happy now. Today I had a kind of enlightenment (after spending a whole school lesson ignoring the teacher and scribbling incomprehensible-to-anyone-but-me notes - I heard they call this a "fey mood"), and wrote a whole new algorithm in Ruby. It now runs in 8 seconds for 50d50 on my computer. [code]def diceCalc(number, sides) current = Hash.new current[number] = 1 number.times do |iteration| new = Hash.new new.default = 0 current.each_pair do |key, value| 0.upto(sides - 1) { |i| new[key + i] = new[key + i] + value } end current = new end return current end[/code] This doesn't include the full functionality of my Java implementation (GUI, full analysis output to file), it just calculates and returns it in a Hash mapping ints (rollable value) to ints (# of occurences) But it's still so much more awesome. Basically, the idea came from data trees and one of the hunches was how J (a pretty cryptic language I dabbled in a few months back) displays multidimensional arrays. Steven Wolfram's "A New Kind Of Science" did help too (he, among other things, writes about substitution systems there). This one is... heavily? optimized, though, so it's not really clear what is happening (unless you spend some time on it). Let's assume x dice y sides each (xdy). We start with this here (practically zero-dimensional) array: [x]. For every xdy, x is the minimal obtainable value; you cannot roll 2 with 3d4. What I'm doing with the algorithm is, at every step I'm replacing every element [i]z[/i] in the array with [z, z+1, z+2, z+3... z+y-1], so for 3d4 it would look like this: [3] [3, 4, 5, 6] - effectively 1d4 + 2 [[3, 4, 5, 6], [4, 5, 6, 7], [5, 6, 7, 8], [6, 7, 8, 9]] - effectively 2d4 + 1 [[[3, 4, 5, 6], [4, 5, 6, 7], [5, 6, 7, 8], [6, 7, 8, 9]], [[4, 5, 6, 7], [5, 6, 7, 8], ...]...] - effectively 3d4 This effectively (yes, I overuse that word) simulates a data tree. Now [amount of occurences] / [y ^ x] is the probability of that roll occuring. This concludes the core algorithm. I thought it would be a pretty memory-eating algorithm, after all it would store millions of values for higher input (which inevitably is the first thing everyone tries out...), so I used a hashtable storing the amount occurences of each value, so the maximum amount of values stored for xdy is (2 * (x - 1) * y) - or something like that (ie. 4900 for 50d50 - two values for each number between 50 and 2500 both inclusive). What happens for 3d4: {3 => 1} {3 => 1, 4 => 1, 5 => 1, 6 => 1} {3 => 1, 4 => 2, 5 => 3, 6 => 4, 7 => 3, 8 => 2, 9 => 1} {3 => 1, 4 => 3, 5 => 6, 6 => 10, 7 => 12, 8 => 12, 9 => 10, 10 => 6, 11 => 3, 12 => 1} (equivalent of what I wrote a few lines earlier in the form of arrays - see? Takes much less numbers to store). This approach is probably slightly slower, but this doesn't make much of a difference for smaller input, and EXTREMELY cuts the memory cost for larger input. Also, it makes post-processing (ie. actually using the data) easier, because it already is stored in a usable form. Also, this being Ruby, which allows numbers beyond Int.MAX (although it calculates these slower) the algorithm is much more graceful. I'm pretty happy now.

Forum » Dice Calculator thingie.

Post Reply