Wesnoth's RNG has statistical weaknesses

All of the people playing Battle for Wesnoth complaining about Wesnoth’s random number generator (RNG) having problems were right.

There is a test used called the “minimum distance” test which tests a random number generator by filling up a volume of space with points determined by the random number generator and determining the minimum distance between any two points. Or, in other words, we take a cube, fill it with points “randomly” by using the RNG we are testing, and make spheres of each point and the point closest to that point. The smallest such sphere is our minimum distance. We do this a number of times.

There is a range of minimum distances we should have. But, with Wesnoth’s random number generator, we don’t get that, especially in four dimensions (it also fails in three dimensions) [1]. A good randomness tester like Dieharder can readily distinguish Wesnoth’s RNG from a good RNG (such as RadioGatún).

The reason for this is because Wesnoth’ random number generator is as follows:

static int32_t state;
uint32_t mask;

state = (state * 1103515245) + 12345;
mask = (state >> 16) & 0x7fff;
return mask;

(The actual code uses division and modulo where I use a shifter and a logical and above).

This is a very simple Linear congruential generator, and is considered a rather poor RNG.

One of these years, I should submit a patch to replace Wesnoth’s junk RNG with RadioGatún. Although I have a feeling the developers will not accept it. It would, after all, be a pretty big blow to their pride to admit the RNG Wesnoth has been using for years has significant, measurable problems.

I should, before signing out, point out that Wesnoth is an excellent game and I appreciate all of the hard work done on it. I just wish the Wesnoth FAQ would stop pretending the random number generator is any good with nonsense like “programmers have examined the random number generator. No flaws have been found”. Because I found significant flaws in under an hour with Dieharder.

I should probably point out that Wesnoth’s RNG also flunks the “Diehard DNA test”.

[1] To properly test Wesnoth’s random number generator in three dimensions with Dieharder, I had to modify the random number generator to use a 32-bit unsigned integer and take the top 16 bits from the generator state (instead of using a 31-bit integer and taking 15 bits). The stream is identical if we remove the high bit from these 16-bit numbers to make them 15-bit numbers.

My final ObHack release

A while ago, I found a minor bug in ObHack which Fritz fixed.

I have finally gotten around to integrating Fritz’s patch in to my version of ObHack, which I call “ObHack-006b-pl1” (ObHack release 006b patchlevel 1). This is simply ObHack 006b with Fritz’s patch.

Barring a security hole in ObHack, this will be my last ObHack release. Fritz is the current maintainer and has made a lot of improvements and changes which I encourage people to download and use. Also, Andrew has very recently made a release of Oblige which makes some impressive maps.

As always:

http://samiam.org/slump/

Civilization V announced

Fans of turn-based strategy games will be very pleased to hear that Civilization V has been announced.

Its most significant new feature will be using a hex grid. This is an interesting divergence from a square grid but reduces the error in land movement from 40% to only 15% or so. I recently discussed this on C-evo’s forum. There are three different ways Civilization clones have grids:

• A square grid, with diagonal movement costing as much as horizontal or vertical movement. Most Civilization games do things this way.
• A hexagonal grid, with movement in the six directions having the same cost. FreeCiv has had support for this for many years. East-west movement is 15% slower than north-south movement (or vice versa)
• A square grid where diagonal moves cost more than horizontal and vertical moves. C-evo does this: A diagonal move costs 1.5 as much as a horizontal or vertical move. No, any fractional move left over at the end of a turn does not roll over for one’s next turn.

Update: There is an official website at http://www.civilization5.com/

ObHack Windows zipfile fixed

I haven't used the program to make .zip files in *NIX in a while, and its command line parameters can be a bit confusing (the correct way to make a zipfile is zip -r ObHack-win-006.8.zip ObHack-win-006.8, with that '-r' being lower case; the manpage incorrectly states that you can do it as zip -r ObHack-win-006.8 ObHack-win-006.8 but that doesn't actually work); as a consequence, the zipfile had a single invisible file with the name .zip in it.

I have remade the zipfile and uploaded it to the ObHack webpage.

ObHack 006.8 released

Fritz has released ObHack 006.8, a random map generator for Doom and Heretic, today. It can be downloaded here:

http://samiam.org/slump/

Support for ObHack is in this forum:

http://www.doomworld.com/vb/doom-editing/

I do not support ObHack

I no longer maintain and do not support ObHack, some hacks I did for a Doom random map generator until a couple of years ago. To get support for ObHack, go to this location:

http://www.doomworld.com/vb/doom-editing/

and look for the most recent thread about ObHack. You may have to go back a page or two (click on the small link marked “>>”) to find the most recent ObHack thread.

Right now, the last poster to post about ObHack was Fritz, the maintainer. He is doing a a good job maintaining and updating ObHack, and can best handle your concerns.

I’m done with chess variants

Taking chess too seriously

Years ago, I went to a local club where I would meet people and hang out with friends. Among other things, we have a couple of cheap $5 chessboards like what you buy at Wal*Mart and Target and people would sometimes play chess at this club.

Tired of getting my butt kicked all the time at this club, I bought some chess books, started studying them, and looked up and joined a local US Chess Federation club with stronger players. Pretty soon, I had very strong chess players teaching me how to correctly develop my pieces and I was winning instead of losing games at that local club where people played casual chess games.

One time, while playing a game at the local club, there was a position where I was winning the game and my opponent (who beat me countless times before I learned how to move at that USCF club) made a move where my best reply was to capture his pawn using an unusual move called “En Passant”. Well, since he was a casual player, he didn't know about this rule. We ended up having an argument over it and ending the game over the argument.

Looking back, I was in the wrong. Yes, at the local USCF club, any tournament director would have told him that en passant was legal and forced him to accept the move. But, we weren't at the USCF tournament. We were at a local club hanging out and playing a casual game of chess. I was taking the game of Chess far to seriously at this point and didn't get a chance to finish a game I was winning because I was acting in a manner appropriate for the local USCF club but inappropriate for a friendly Chess game.

Well, once I was able to beat all of my buddies who used to kick my butt at the casual club, I realized that Chess was only a game and I was working too hard to get good at something without any real-world use. I started concentrating on improving my computer skills instead and soon had a good job in the computer industry. I also let my USCF membership lapse.

Chess Variants

It was around this time that I got interested in Chess variants (ways of changing the rules of Chess). I was studying the opening in regular Chess, and it really amazed me how people went to so much effort trying to evaluate a move in the opening, but I was disappointed in how they only looked at the opening of one game, when regular Chess is a subset of an infinite number of possible Chess games.

What I really wanted to see was people start studying the opening in depth of a different Chess game; once people felt that opening was studied, I wanted to see people study the opening of yet another chess variant. The Chess we know is just one grain of sand in the infinite beach of possible Chess games, and I wanted to see more of the beach explored.

This wish finally became last last couple of years possible because of some programs made or hacked by a talented programmer by the name of H.G. Muller. I was able to use his software to play tens of thousands of my single contribution to the world of Chess variants (which, ironically enough, is one of the relatively few Chess variants to be mentioned in the Wikipedia, albeit as a single one-line mention). After studying the opening, I realized that Schoolbook Chess (my one Chess variant) was a bit unbalanced in favor of white, but my research also showed another similar setup is a more balanced game, with white only having a very slight advantage.

Once I was finally able to do this research, my interest in Chess variants waned. I realized that the infinity of possibilities only exists in the abstract. Most Chess players will be perfectly content playing only regular Chess for the rest of their life; the very few people who are open to playing variants haven't played a single given game enough to make studying its opening worthwhile or even feasible in any manner besides using computer simulations. One community, looks at a given variant, plays at most a dozen games with the variant, and moves on to the next variant.

Chess bores me

I realized, while doing this opening research, that the results of opening research bore me, as well as actually playing a Chess variant. I just don't enjoy Chess any more. It was only a fun game for me in the context of that club many moons ago and having something to do with my buddies. It hasn't been a fun game for me for over a decade, when my last casual buddy got sick and tired of me beating him all of the time.

The only thing about Chess variants that interests me today is studying the opening and developing opening theory. Even that is not too interesting; I seem to be the only person in the world who likes the idea of studying a Chess variant's opening in any amount of detail.

In addition, there isn't anyone out there who appreciates the effort I went in researching my one chess variant. So, not only is it no fun, but there isn't any demand for the work I did researching chess variants.

It's time to move on. That in mind, not only will I no longer visit Chess-Variant related web sites, I have deleted my webpage with all of my Schoolbook-related files (A chess variant I invented). I'm keeping the ChessV webpage around, for the simple reason that, if I delete this webpage, Greg's ChessV program will no longer be available on the internet, and there has been interest in this program.

Actually, I wish someone else would offer to host ChessV so I can let go of it too, but I can host it until we find another host.

People's Tactics was written in Visual Basic

Looking at how People’s Tactics handles errors (by popping up a windows saying something like “Run time error ‘11’: Division by zero”), and seeing how slowly the program runs, I looked more closely at the code. Looking at the PeoplesTactics.exe binary, I discovered this string near the top: MSVBVM60.DLL. Yep, People’s Tactics was written in Visual Basic, which explains why the AI is so slow when trying to make its move.

The newer Advanced Tactics is written with a .NET language, probably VB.NET (since People’s Tactics was written in Visual Basic, I find it quite unlikely Vic decided to use C# instead for Advanced Tactics).

Also, yesterday’s hack to allow another set of rules to be used with People’s Tactics random maps results in crashes when trying to play with Civil War units. I’m not sure if other rules (such as WWI units) will also cause problems; my testing of a hacked form of the Banana Republic units for a random game, however, shows no problems.

Changing the random scenario in People’s Tactics

I discovered today that it is possible to change the random scenarios in the game People’s Tactics (scroll down and look in the sidebars to see the People’s Tactics download).

People’s tactics uses the scenario scenarios/2PL_Two_Rivers.pt1 to determine the type of units and other game rules for random scenarios; if you back up this file and then rename, say, 2PL_World_War_One.pt1 to have the name 2PL_Two_Rivers.pt1, random scenarios will now have World War I units (no tanks until this technology is purchased with political points, etc.).

Cool way of getting more variety out of People’s Tactics’ random scenarios.

Cool blog on the problems of freetards

There is a cool blog entry on the problems of the attitudes freetards have, and the issues with “free content”. There is no such thing as a free lunch, and the new economy hasn’t changed that.

People who think open-source software (OSS) makes it possible for all content to be free don’t understand how OSS changes the relationship between the developer and the user. A lot of people think an OSS program is like a commercial program, but free, and that they can ask for features or get support for free, and it gets pretty tiring to have people email me asking for free support, even though I make it clear that I don't provide free email support for my program.

The thinking behind OSS is that I donate some of my coding time and effort to the greater community. In return, people are free to contribute bug fixes or improvements to the program, or supply support on the mailing list. For example, someone wanted better IPv6 support, supplied patches, and now MaraDNS has good IPv6 support. Another person wanted better Windows service support, and supplied patches to make MaraDNS’ new recursive core be a full Windows service. Other people answer user's questions on the mailing list or translate documentation. Webconquest very generously provides me a free Linux shell account and hosting for the web site.

Likewise, I found an OSS Doom random generator I liked and provided bug fixes and improvements to it; when I lost interest in it, another person became the maintainer and improvements continue to be made even though I no longer work on that code. And, there is a Free Windows Civilization clone for Windows which I have provided a bug fix and extended the documentation with.

OSS doesn’t mean we have the right to demand all content be free or that we are justified in pirating media and software. OSS means that we can, together, make free content which complements the for-pay content out there.

A programming project idea

One idea I have had bouncing around my head for a while is to make an generalized engine for a turn-based strategy game. I’m thinking something along the lines of Xconq, but done right.

I’ve blogged about Xconq before; Xconq is a game that had a lot of potential that was never realized.

To be fair to Stan Shebs, when he started the Xconq project in the 1980s, he did not have a lot of tools available today for making video games.

To wit, if this idea in my head every become reality, I’ll use two libraries Stan did not have:

• SDL for handling graphics, and for abstracting the OS away from the application (SDL runs on Linux, Windows, and Mac OS X)
• Lua for handling the scripting; the best embeddable scripting language Stan had was a Lisp dialect, which, while elegant, is hard for end-users to learn

In addition, while the goal will be something that can easily make just about any turn-based game out there, I will focus on only one turn-based game.

My plan is to have a C-language layer between SDL and LUA; this layer will handle the nuts and bolts of the game (drawing the tiles, pathfinding, drawing the units, making the GUI), and have LUA control all of the rules of the game. To keep things simple, the engine will only allow hex tiles, and allow only either a flat map (border around the edges), or what I call a “sphereoid” map: Flat map, wraps like a cylinder left-right; going north of the North pole puts you at another square on the north pole, ditto with south pole; this is topologically equivalent to a sphere. The engine, if ever made, will assume units move to one adjacent hex per movement point (teleports, a.k.a. the “Silver Mage” in Wesnoth, will come later), and different hex types will have a weight (for the pathfinder), movement cost (different from weight for tiles that damage units), and visibility (for determining shroud updates and fog of war).

Movement will be Wesnoth style; click on a unit once to see where it can move; click on a square to move the unit there; right click after left-click to cancel the movement; right click on a unit will pop up a menubar defined by the LUA script. With the exception of things like "Save Game", "Load game", other menubar items will be determined and processed by the LUA script.

Anyway, this is just a “blue sky” idea right now. Back on Earth, it’s time to give Deadwood real recursion. Speaking of which, Deadwood is now used by CERN laboratories. You know, the guys who invented the World Wide Web (which was just a side-project to help people share research) when not doing real research.

C-evo on netbook bug fixed

There's a bug in C-evo (the largest game I put on my 50 megabyte "desert island" disc) where it doesn't fully work on a netbook. In more detail, the diplomacy screen is nay-to-impossible to use on a screen only 600 pixels high because its top is cut off.

Since one rule I have for all software on my desert island disk is that it must work on a netbook [1], I have fixed this bug. Look at c-evo-netbook-fix.c and c-evo.netbook-fix.exe at samiam.org/cevo. This program, which is run in the same directory as cevo.exe, creates a cevo-netbook.exe with this bug fixed.

In more detail, the offending code is this line in Term.pas:

NatStatDlg.UserTop:=Screen.Height-PanelHeight-NatStatDlg.Height-8;

These are the variables used:

NatStatDlg: The window that pops up when you hit F9 (the nations window)

UserTop: Its default starting position, whose top is off the screen on a netbook unless we fix the above line.

Screen.Height: How high our screen is

PanelHeight: How high the "panel" on the bottom of the screen is

NetStatDlg.Height: How big the nations window is.

8: An eight pixel cushion so it looks a little nicer.

Since I don't have Delphi 4, I had to find the resulting compiled code the hard way. The offending -8 above is byte number 723333 in the code (as a positive 8, since the compiled code subtracts 8, instead of adding -8). Since C-evo is using the "subtract this 8-bit signed value with a value of 8" opcode here, we can make the number in question a negative number, resulting in the window being moved down instead of being moved up.

[1] The target netbook is a Intel N450-based netbook with a 1024x600 display.

Battle of Wesnoth random map templates

I have created a few Battle of Wesnoth random map templates. One (the forest one) I actually created back in 2007; the others I made this week. They can be downloaded here:

http://samiam.org/wesnoth

ObHack 006.7 released

Fritz has created and I have uploaded and released ObHack 006.7, a random map generator for Doom, Doom 2, and Heretic:

http://samiam.org/slump/

New C-evo maps

I have made a couple of preset maps for C-evo today; both are very small maps. One is best for a 1-player game against the AI; there are a number of starting positions but the human has a better island. The other has three starting positions on a tiny map.

Also included is one of the “Total fairness” C-evo maps.

The main reason I have made these maps available is because I had a small file with just one map which was only about 800 bytes in size; since the Desert Island CD uses the ISO filesystem with a 2 kilobyte block size, making this file a little bigger (any size 2048 bytes or less) doesn’t increase the amount of space the file takes up on the disc.

It can be downloaded here:

http://samiam.org/cevo/

C-evo tutorial finished

While I finished all of the essential writing for the C-evo Tutorial yesterday, I spent some time this morning cleaning up the wording (removing typos, simplifying one paragraph that was a little hard to understand, etc.) and have uploaded the tutorial here:

http://samiam.org/cevo/

C-evo tutorial made

I have spent a good deal of the last 24 hours working on a C-evo tutorial. It can be downloaded at http://samiam.org/cevo.

I found a couple of websites with small games

Last night, I found a couple of places where I can look at and download small games.

The quickest way to find small games is to go to a website hosting files from the “demo scene”. One very significant part of the “demo scene” is coming up with tiny little demos or fully playable game whose .exe fits in a given size, such as 4k, 32k, or 96k. 4k gives you a very basic Tetris clone; 32k can give you a remarkable playable game in the vein of a 1980s or early 1990s Amiga or Atari ST game. 96k can give you a small but complete full game; there’s even a playable First-person shooter that fits in 96k (but, alas, can be finished in about 15 minutes).

The website I used to find demos was http://www.pouet.net/; the page which starts to list the tiny playable demos is at this link.

The one I like the most is a 32 kilobyte PacMan-style game. This got a few bad reviews when it first came out, but ignore them; the game has since been updated with sound added to the main game and the collision bugs people complained about have been fixed.

Some other notable demo games include a Tempest clone with 21st century graphics and sound, complete with configuration menus in only 96k (but the extensive eye candy sometimes makes gameplay a little difficult, and the screen moves around while playing in a way that can give you a headache), a 32k clone of a late 1980s platform shooting game which while beautiful and groundbreaking for its time, has hard-to-use controls, and a 32k clone of a late 1980s platform jumping game that, while amazing, is a very challenging game and the controls are a little awkward.

Another place to find tiny games is http://www.acid-play.com/, a listing of thousands of Windows freeware games. Finding diminutive games is a little harder at this site; there is no way to sort games by size. However, each game has its download size listed, which makes it possible to browse for small games.

There are a few tiny gems here; one I like is a simple little late 1980s shooter called Light-Z which 7-zip compresses down to 174k.

I’ve decided to put that 32k tiny Pac-Man style game on the next version of my Desert Island Disc. I would like to have precisely seven games; I haven’t decided whether to make the seventh game the 21st century Tempest clone or the simple shoot-em-up Light-Z.

Javascript Manic Miner

I found a version of Manic Miner more suitable for putting on the next (2010) version of my Desert Island CD: There is a Javascript implementation of Manic Miner out there.

I was able to scrape all of the files needed to play this, and after using PNGCRUSH and advpng to make the PNG files as small as possible, I was able to get this entire working Manic Miner implementation to fit in under 32k (7zip compressed).

Unlike other Manic Miner implementations, where the authors take a sadistic delight in hiding the cheat codes from users (I don’t understand why Andy Noble changed the cheat code for Manic Miner), this one is easily modified with a text editor to change the initial level or give the player unlimited lives; these are even variables easily set at the beginning of the program.

So, I’ve gotten Manic Miner down from 450KB to 32KB. Like I said before, I’ll put wedding photos in the newly opened up free space or another tiny video game if I can find something usable out there.

Desert Island future plans

Right now, I have the following games on my Desert Island CD:

• The excellent C-evo
• David Teach's Gin Rummy
• A tiny version of Zillions of Games
• Cultivation
• Andy Noble's take on Tetris and a 1980s video game called "Manic Miner"

Of these six games, I am going to delete two for the next Desert Island release: Cultivation and Manic Miner.

Cultivation doesn't have compelling graphics, IMO, and its gameplay is a bit far-fetched for my tastes.

Manic Miner's problem is that it's a faithful copy of the original 1983 game, and like the original game, it's, as TVTropes calls it, "Nintendo Hard". After struggling for an hour, I was able to get past the first screen, and even on to the third screen, but there's no way to save the game so I have to go back to the first screen every time I start the game up.

There is supposedly a cheat code for it (802926) which lets one jump past levels, but it doesn't work. So, out it goes. Andy's take on Tetris is nice (and my fiancée likes it), but I'm ditching his take on Manic Miner (which, yes, is faithful to the 1983 game, but we've moved beyond that).

There's a couple of other takes on Manic Miner for the PC out there but I don't like either of them either -- one of them has the audacity to ask for a shareware registration fee for the game. As a programmer who despises freetards myself, I agree people should get compensated for their work, but when original Manic miner creator Matthew Smith flat out says "if they are making money then I want my share", I don't feel it's ethical to make a shareware Manic Miner without giving Matt his cut.

So, deleting all this leaves me about 850k to play with. 150k or so of that will be some C-evo stuff (my HOWTO, a couple of small programs to mod C-evo's gameplay, a diagram of the tech tree, and slightly modified Mongol nation graphics); that leaves me with about 700k. Some of that will become wedding photos once I marry my fiancée January sometime; but I need to find one or two more really tiny games with compelling gameplay that doesn't quickly get stale.

Some ideas:

• An emulator and some old video games. My biggest issue here is finding games the creators don't mind having available on the Internet
• Win Frotz (under 200k) and a few text adventure games. The issue here is that these kinds of games have no replay value.

Does anyone else know of any good tiny video games for Windows? Replay value is important.