Editor, Experienced Forum User, Published Author, Active player
(296)
Joined: 3/8/2004
Posts: 7469
Location: Arzareth
Hmh, it still doesn't work... after 122925844 analyzed board positions, it bails out saying that the position it was supposed to handle next wasn't seen yet.
Because the bug persisted over changing the method the board positions are indexed, the cause of it must be either in the radixtree implementation or the filebacked ring buffer...
Edit: I think I found a bug in the ring buffer implementation. It reused deallocated pointers...
Edit 2: Nope, it still doesn't work :-/
Editor, Experienced Forum User, Published Author, Active player
(296)
Joined: 3/8/2004
Posts: 7469
Location: Arzareth
Walker Boh wrote:
FODA wrote:
Same as walkerboh, i remember the game MAPPY, this looks like a sequel. I never knew this one existed.
Ah. That's the game I had in mind! I'd really love to see a TAS on that one ;)
Your wish is granted.
https://files.tasvideos.org/bisqwit/mappy.fcm
It plays the first 20 levels seriously, then gives up (because there doesn't seem to be end to the levels - after 18 it just seems to loop the same levels with progressively faster kittens).
The first and second bonus level could be played faster. I fixed the error in later bonus levels.
Edit: And, the first level could be played faster, too. I sort of caught the techniques while playing.
I tried to utilize the microwave doors and other kitten-handling measures as well as possible without wasting time for it. Unfortunately I didn't have opportunity to visit the roof or to use the churchbells.
Editor, Experienced Forum User, Published Author, Active player
(296)
Joined: 3/8/2004
Posts: 7469
Location: Arzareth
Gorash wrote:
Your Choo function is broken then...
I replaced your original function with the new one, and I get the same error.
You are right. Okay then, I'll try using this!
Edit: Apparently, it's the "if(K==0 || N<K) return 0;" rule which breaks it. Hmhm.
Edit 2: Right, because it should have been "if(K==0) return 1;".
Edit 3: It works, and is in use, and using the mpz_bin_uiui function of GMP, it isn't very slow either
Let's see what kind of effect it has. :)
Editor, Experienced Forum User, Published Author, Active player
(296)
Joined: 3/8/2004
Posts: 7469
Location: Arzareth
Gorash, can you make a version that iterates over B instead of iterating over P?
Edit: And another thing...
Your function gives the same result, 2185700, for both 18-23-45-59 and 18-23-45-96.
My C() function is now this:
/* Calculates the C(N,k) function. */
unsigned long long Choo(unsigned N,unsigned K)
{
if(K == 0) return 0;
// std::cout << "C("<<N<<","<<K<<")=";
unsigned long long Result = N;
if(K > 1)
{
if(N <= K) return 0;
Result = Result * Choo(N-1,K-1) / K;
}
// std::cout << Result << "\n";
return Result;
}
And Sum3 is:
unsigned Sum3(unsigned Buf[4])
{
unsigned B = 4; // block count
unsigned P = 100; // position count
unsigned i = 0, result = 0;
for (unsigned bp=0; bp<P && i<B; ++bp)
if (Buf[i] == bp)
++i;
else
result += Choo(P-bp-1, B-i-1);
return result;
}
Editor, Experienced Forum User, Published Author, Active player
(296)
Joined: 3/8/2004
Posts: 7469
Location: Arzareth
Gorash wrote:
I really want to see more perfect solutions. :P
In that case, would you like to try writing out the Sum3() function to this test program?
It should be generalized enough so that the number of blocks (and number of coordinates) can be later tuned at compile time (but not runtime) without touching the source code.
#include <cstdio>
#include <set>
#include <iostream>
#include <algorithm>
/* Calculates the C(N,k) function. */
unsigned Choo(unsigned N,unsigned K)
{
unsigned long long nom=1, denom=1;
std::cout << "C("<<N<<","<<K<<")=";
while(K > 0)
{
nom *= N--;
denom *= K--;
/* Use euclidean GCD algorithm to simplify nom/denom */
/* In order to make integer overflows unlikely.
* They still do happen easily though.
*/
unsigned long long gcd = std::min(nom,denom), util=std::max(nom,denom);
for(;;)
{
unsigned long long tmp = util % gcd;
if(!tmp)break;
util = gcd;
gcd = tmp;
}
nom /= gcd;
denom /= gcd;
}
std::cout << nom/denom <<" (nom="<<nom<<",denom="<<denom<<")\n";
return nom/denom;
}
/* Introducing three methods of converting an array
* of 4 elements in range 0-99 into a single unique integer.
*/
/* Easiest method. Output value range: 100^4. */
unsigned Sum1(unsigned Buf[4])
{
unsigned result=0;
for(unsigned a=0; a<4; ++a)
{
result *= 100;
result += Buf[a];
}
return result;
}
/* Sum2 is Sum1 altered to take advantage of the assumption
* that the input values are (1) ordered and that (2) same
* value will not appear twice.
* Output value range: (100-4)^4
*/
unsigned Sum2(unsigned Buf[4])
{
unsigned result=0;
unsigned last = Buf[0];
result += last;
unsigned limit = 100-4;
for(unsigned a=1; a<4; ++a)
{
unsigned coord = Buf[a];
result *= limit;
result += coord-last-1;
last=coord;
}
return result;
}
/* Sum3 should, in theory, output values in range C(100,4),
* that match the same uniqueness rule as Sum1 and Sum2
* already do. But somehow we're not there yet. This is a FIXME.
*/
unsigned Sum3(unsigned Buf[4])
{
unsigned result=0, scale=0, begin=0;
for(unsigned a=0; a<4; ++a)
{
result *= Buf[a]-scale;
result += Buf[a]-begin;
scale = begin;
begin = Buf[a]+1;
}
result *= 100-scale;
return result;
}
int main(void)
{
Choo(100,4); /* Outputs 3921225, which is the value of "100 choose 4". */
/* This loop verifies that the functions work as supposed to.
* Tests performed:
*
* - Verify that all Sum() functions match the same rules of uniqueness
* - Verify that Sum3() won't create values greater or equal to C(100,4).
*/
std::set<unsigned> set1,set2,set3;
for(unsigned a=0; a<1000000; ++a)
{
Retry:
unsigned Buf[4];
Buf[0] = rand()%100;
Buf[1] = rand()%100;
Buf[2] = rand()%100;
Buf[3] = rand()%100;
std::sort(Buf,Buf+4);
if(Buf[0]==Buf[1]
|| Buf[1]==Buf[2]
|| Buf[2]==Buf[3]) goto Retry;
unsigned s1 = Sum1(Buf);
unsigned s2 = Sum2(Buf);
unsigned s3 = Sum3(Buf);
bool f1 = set1.find(s1) != set1.end();
bool f2 = set2.find(s2) != set2.end();
bool f3 = set3.find(s3) != set3.end();
std::printf("%2u-%2u-%2u-%2u: s1=%u,s2=%u,s3=%u f1=%s,f2=%s,f3=%s\n",
Buf[0],Buf[1],Buf[2],Buf[3],
s1,s2,s3,
f1?"true":"false",
f2?"true":"false",
f3?"true":"false"
);
if(f1 != f2
|| f1 != f3
|| s3 >= 3921225)
{
abort();
}
set1.insert(s1);
set2.insert(s2);
set3.insert(s3);
}
return 0;
}
Editor, Experienced Forum User, Published Author, Active player
(296)
Joined: 3/8/2004
Posts: 7469
Location: Arzareth
I have to say that you lost me on the explanation of enumerating board positions.
As you already know, I need a method to convert an array of block positions (which are assumed to be sorted in ascending order) into an integer.
I'll try to analyze your post better when I'm better awake.
> Not that it matters, but couldn't peter stand a little bit away from a box after kicking?
Yes, I think this point invalidates my idea. The shape of the level immediately after kicking is indeed stored to the radixtree, and thus the optimization on Peter's position can't be taken. However, your idea to eliminate the coordinates that coincide with boxes' locations still applies.
Editor, Experienced Forum User, Published Author, Active player
(296)
Joined: 3/8/2004
Posts: 7469
Location: Arzareth
Gorash wrote:
What if your map uses compressed situations as keys (as now?) and saves the last move plus the overall framecount of that solution as values.
You are trying to optimize wrong issue.
The size taken by the list of attempted moves is not an issue. The current program uses generally 5-6 bytes per move (including the link to the previous move). At worst it has taken about 600 MB of memory, even if the unworthy moves are never deallocated. This memory is currently taken from a temporary file, so it's really not an issue at all. At any given moment, it only reserves at most 2 MB of the program's address space.
This wasn't the situation when I wrote the technical explanation though.
I'm also doing the same treatment (temporary file with portions mmapped and munmapped on fly) for the TODO-list of board positions. The size of that list may approach 4 GB, but it is not an issue: an address space of 16 TB may be used for them, if only the disk space allows it. They are stored in a disk-backed ring buffer.
> Hmm, my personal calculation says:
10 boxes disregarding order in 46 places are binom(46,10) possibilities.
I am not familiar with this "binom()" expression you use, and I don't know how to convert it into an integer.
And I certainly don't know how to form an integer from those 10 block positions according to this binom() rule.
I think you might be right however.
In Finnish lottery, there are 7 numbers chosen from the 1..39 range. According to Wikipedia, the number of possible combinations is 15380937. According to my formula, it would be 34359738368 ((39-7)^7).
I don't understand where the difference comes from.
With Google, I found that the formula (for lottery) is 39! / (7! * (39-7)!), but I still don't understand.
[Edit 2]: Okay, now I do. My coordinate system _allows_ expressing the same board configuration with different numbers (different order of blocks), even though the game can never generate more than one of them. (The block position list is always in a coordinate-sorted order.)
In other words, my coordinate system stores the delta between each two coordinates (and the first coordinate position), and the maximum theoretical sum of those delta values is greater than the actual maximum possible sum of the delta values.
So now I need a new method of enumerating the board configurations.
The current algorithm is here:
function GetCompactData returns bigint
{
bigint result;
result = PlayerCoordinateTranslation(playerpos);
int last = BlockCoordinateTranslation(blockpos[1]);
result *= PlayerCoordinateLimit;
result += last;
int limit = (BlockCoordinateLimit - NumBlocks);
for(int blockno = 2 to NumBlocks)
{
int coord = BlockCoordinateTranslation(blockpos[blockno]);
result *= limit;
result += coord-last-1;
last=coord;
}
return result;
}
Where PlayerCoordinateTranslation is a static table of that maps real player coordinates into those "allowed player coordinates", and PlayerCoordinateLimit is the number of those "allowed player coordinates",
and Block* are respectively the same for blocks.
> In each of these situations Peter may be in 70-10 positions on the field
Now that you mention it, in fact, Peter may be in 41 different positions as most, because he's always either in the beginning location or facing one of the boxes from some direction.
The intermediate walking positions are not seen by the solution finder except when calculating how many steps are there from point A to point B (for the cost).
But this difference only saves 0.1 bytes. :)
([Edit]: In 2-2, there are 49 points of floor. 49 points where Peter can stand. But there are 13 blocks. If using the method explained above, Peter has 13*4+1=53 different points. However, such space-cramped levels are rare.)
> if I read that glimpse correctly the actual stuff is a lot more.
Yes, that particular code are the template functions which are responsible of loading/generating&saving maps of dead N block position combinations (where N is an integer template parameter).
Editor, Experienced Forum User, Published Author, Active player
(296)
Joined: 3/8/2004
Posts: 7469
Location: Arzareth
Gorash wrote:
Have you tried throwing away the caching of blunder situations and computing them again everytime?
In the beginning, some cache is created of blunder situations, and that cache takes relatively very little memory compared to the amount of iterations (and thus, memory) it saves.
> You could also merge walking and push/kicking into one cycle, reducing the intermediate situations that need to be saved.
Already done.
> Another idea I see from your tech description
Which, is very outdated.
> would be only saving the last (best) move (10 bit for desciption
> of the starting position of kick/push, other 6 bit for length of pushing,
> 0=kick, implies that peter has moved there from last position) and
> the framecounter after the situation, and then reconstructing the
> movie after the puzzle is solved. Would save a little memory.
The problem is that there still needs to be a container that can answer the question "has this situation been tested before?" and also "if the situation was tested before, did we reach the situation now faster than we did back then?".
Therefore, all the game states need to be saved.
Otherwise you can't know whether you're progressing at all, or if you're just pushing the same boxes back and forth.
The storage for those situations is currently a very effecient implementation of a radix tree. The level itself is compressed as an arbitrary-precision integer that is mathematically composed of the positions of the player and the boxes, with a coordinate system that only allows valid non-blunder positions.
A state of the level 3-2, for example, where there are 10 boxes + player, takes only 8 bytes.
In 3-2 you see, there are 70 possible locations on floor for the player to reside in, and 46 possible locations for boxes. But since two boxes can't be placed in same coordinate, the number of possible locations for boxes is actually 36 when considering the other boxes too. For the blunder checker, +1 is added to allow boxes to be removed from the field.
Thus, the state of the level 3-2 is stored in ceil(log2(70*37^10)/8) bytes, that is, 8 bytes.
> Is it possible to get a glimpse on the source? :)
Due to the possibility that someone might abuse it, I'm keeping it closed. Of course, someone might still create a similar effort, but from my experience, I think that's rather unlikely.
But ok, I will offer a glimpse :)
Editor, Experienced Forum User, Published Author, Active player
(296)
Joined: 3/8/2004
Posts: 7469
Location: Arzareth
In August 2005
- Globally on my webserver, there were 1912905 hits, 15.7 GB of traffic, with average of 2571 hits per hour.
854k hits in the name of MSIE 6, 876k in the name of Mozilla.
However, this balance is likely skewed by the fact that the Peter Box players have played with Mozilla browsers exclusively and playing the game inflates the hit counters a bit.
In August 8th, there was a fourth-fold spike in the traffic, caused by Digg's mentioning of the Super Mario Bros Tricks page.
According to the logs, the page was however loaded "only" 15139 times during this month.
In comparison, movies.cgi was invoked 137494 times and the front page 110657 times.
In August, the audience favourite movie was still Spezzafer's Super Mario World 2. The torrent file was loaded 8246 times. However, many of those who downloaded the torrent file, apparently didn't know what to do with it, because the AVI itself has been downloaded just 9262 times since it's publication in June 18th.
Editor, Experienced Forum User, Published Author, Active player
(296)
Joined: 3/8/2004
Posts: 7469
Location: Arzareth
schneelocke wrote:
No, but if you add a line that says "GroupAgent Opera Opera" to the config file, it'll Do The Right Thing(tm). Just be sure to put it before the GroupAgent line that gobbles up MSIE entries.
Thanks, let's see next month if it worked properly :)
Editor, Experienced Forum User, Published Author, Active player
(296)
Joined: 3/8/2004
Posts: 7469
Location: Arzareth
movie description wrote:
This movie was made and encoded with an emulator that lags in places where the original game doesn't. The emulator has since been fixed, and so a new version of this movie that will be encoded at the proper speed is in the making.
Editor, Experienced Forum User, Published Author, Active player
(296)
Joined: 3/8/2004
Posts: 7469
Location: Arzareth
Dan_ wrote:
I still finish the first stage 17 frames ahead of you.
Any comment, Shinryuu?
If I had to guess the reason, I'd say that you still shoot some enemies too late.
You should kill them as soon as they appear (the shots have to be fired before the enemies appear) so that they cause the least possible amount of lag.
Also, you could maybe luck-manipulate some enemies' shots (which cause lag) off.
Editor, Experienced Forum User, Published Author, Active player
(296)
Joined: 3/8/2004
Posts: 7469
Location: Arzareth
Still made in Game mode B, it seems.
Therefore I can't say whether it's better or worse than the existing publication.
Voting Meh.
Note: I will not publish two movies of Circus Charlie parallerly.
Either this has to be better than the existing movie (in which case it will obsolete the old one), or it will be rejected.
In frames, this movie is faster than the existing submission, but that's not to say much because the timers are different in the two game modes.
Editor, Experienced Forum User, Published Author, Active player
(296)
Joined: 3/8/2004
Posts: 7469
Location: Arzareth
Xaphan wrote:
Unless we, users of this site, find a place to host WIP and exhibition movies i do not think it would be (for now) a good idea to add this section to the site... Look at the submissions page, it has submissions that have been posted last year (2004)...
In fact, a system for WIP movies is under construction for this site.
The submission queue will eventually be converted to some kind of project manager.
However the schedule for that project is not yet established.
-There are numerous bugs that are inherent in the game and have nothing to do with the patch
itself (such as an item duplication bug, and various freezing or crashing bugs). Check the
Star Ocean Shrine [...] for info on these bugs.
Strangely though, I was able to complete the game several times with a single crash, and that particular crash was a bug in the translation I was betatesting (the crash was then fixed), not in the game itself.
Editor, Experienced Forum User, Published Author, Active player
(296)
Joined: 3/8/2004
Posts: 7469
Location: Arzareth
Mike OShay wrote:
Yeah, but I still think it'd be cool to see. Plus, you could jazz it up by beating the warp, pre-warp, and Bowser's Castle stages as fast as possible.
And you could fill the other levels (1-1, 4-1, 8-1, 8-2, 8-3) with all kinds of tricks.
But you can't have a mushroom, break a brick, take a coin or kill a single enemy.
There _is_ some challenge in the task. Some coins in 8-1 are quite hard to avoid.
