After much searching, I finally got what I wanted!

With permission from the Mrs (like I even have to ask!) I finally procured myself a new geisha. Quite the cutie too if I might say - although her only short coming is that she is not a native japanese geisha. So be it. A small flaw I can overlook for the bargin price of 200,000 Zambia Kwacha! And its not even really a purchase, its just a loan, and she is on collateral for 20 years. Good enough I say. That will make her 39 when the note is completed, at which point, maybe I'll pick up another. But, if she serves and knows her place well, and wishes to stay, perhaps I will retain her.

100581

Woot! I broke the 100k mark :)

This blog is going to slowly turn into a marathon blog (at least many of the entries). Gonna aim for the Oct 2006 USMC marathon. First goal will be to complete an unofficial one in Oct 2005, no matter how slow (goal seems to be to just finish for the first one according to everyone) and then I can work on getting a little bit of time work done. Not too mention that means when I run the official one, I'll have 1 under my belt already :)

The Lord giveth, and the Lord taketh away

So I got semi excited that my chess was actually playing semi fast (relative to the suckiness of Flash). That was before I added in the castling, enpassant and check rules, which should be no big deal right?

Castling, piece of cake. No performance hit
enPassant? No biggie either
check rules? Oh I'm sorry, Flash sucks remember?

Lets back up a bit, I got semi around the bitboard problem by creating the standard 8x8 array to represent my board, and while that was indeed time consuming, I also implemented a little bit of code that would move and then unmove pieces while the computer thought about what to do. This worked immensely faster than array copying, because array copying in flash is horridly slow. Not too mention it means I'm not storing each board position, and hence, use less memory (and Flash really blows at managing memory). If I had say, 900 boards of 64bits for a bit board, thats not exactly a whole lot of ram to worry about when you are using Gigs. Turn that into 900 8x8 arrays for flash, even with a miniscule amount of info stored in each array position, and its gonna get hurt, badly. It completely drove my system into the ground trying to manage it all. If I had my way, I think I would have used bitboards for the computations and still used a move/unmove system, with maybe 1 "backup" board in the memory per leaf node (which would then be erased upon leaving the leaf completley).

So, back to topic. No bit boards means no fast computations, and of course in chess, you need to make sure your king isn't in check (or mated). I originally started looking at every opponent piece for side X, to see if they could attack row A col B (where the king is) but that was not an acceptable solution as it took too long. So I worked the problem backwards, for some good gains. At row A col B, where could I move to if I was a rook,queen,bishop. If I could move and the square was occupied, was it an enemy piece? And if so, was that piece the corrosponding one to get back to the king location? This works quite well (of course, you slightly alter this for pawns) as a king "sealed" off by its own pieces yields very little check work. If we look at the standard set up (turn 1, white to move):

rnbqkbnr
pppppppp
--------
--------
--------
--------
pppppppp
rnbqkbnr

The "old" way (my first attempt) had me looking at 16 pieces, many of which would have a ton of moves (IIRC the average is 30 something total possible moves, I want to say upper 30s, but don't quote me).

The new way, in this case, has me looking at 5 squares. Much, much better no? Worst case is 27 squares to look at with the king isolate and can be attacked along an entire rank / file / diagonals. An unlikely setup, but better than 30 some odd combinations. And if the game has progressed to the end, there aren't very many pieces left anyway, which means a small (hopefully) first tier leaf.

Ok, so, even tho I made these gains, they still aren't quite enough. 2 moves ahead its taking nearly 2 minutes to complete. Why? Because the extra time spent on making sure the king is or isnot checked for 900 boards (or so) really adds up :(

Santa needs to deliver a better Flash (with binaries as big as I'd like)

I'm not above constructive criticism

And its been suggested, that this blog really needs a flash intro. Of course it does, as we all know every webpage thats any webpage requries a long drawn out flashy flash intro with flashy lights and flashy techno and flashy effects. So I must ponder how I might go about this. If anyone happens to have any suggestions, please feel free to comment.

p.s. Japanese servant position is still open. Inquire within.

Quick little blurb

“Arkos! Arkos!” came the child-like call for the second time. The captain of the guard reined his horse to a halt, and looked over his shoulder to see a figure fast approaching in the moonlit night.
The figure – a young woman – stopped a few paces away, bent over and resting her hands on her knees as she panted to catch her breath in the frozen night air. Shoulder length black hair fell from her hooded cloak, slightly obscuring a soft, pale face. From beneath her fallen bangs peered bright green eyes, full of excitement, and ones that captivated Arkos with intrigue. He immediately recognized her as the serving girl that had tended to his table the night before, but could not recollect her name. It did appear however that her nail polish had continued to be picked at, for only a few specks and blotches remained.
“What do you want?” he finally asked, realizing he had already spent far too much time idling. He had pressing issues to attend to and could afford to wait no longer.
“I want…” she replied, still a bit out of breath. “I want to come with you.”
“We don’t take children,” the captain replied, a smile forming across his face at the notion. “Maybe when you’ve grown some you’ll be fit to swing a sword.”
The girl straightened up, brow furrowed slightly and visibly insulted. She brushed back her green, full-length cloak to reveal a short sword hanging off her hip. “I’m of age and can use this well. Please, you must let me come! I can’t possibly stay here!”
She sensed the captain’s hesitation on the matter, and pleaded further “Surely you can always use another!”
“That may be,” Arkos replied thoughtfully. “But I need strong and able bodies. Not ones that have no formal training whatsoever.”
Her shoulders dropped in disappointment.
“Our recruiter will pass through this spring, I’m sure you can sign up then,” he finally said, putting a final end to the matter. “I bid you farewell.”She watched him turn back and trot off into the darkness, with only the sounds of his horse’s footsteps to keep her company. If he would not take her now, perhaps she could convince him of her worth down the road. At the very least, it would get her out of her frigid prison. With that thought in mind, she turned back with a renewed sense of vigor to fetch the pack she had prepared at home. All she would have to do is slip and out unnoticed.

Girls that tease

are teh suck (pun not intended).

Yet another moral Q

Lets say - hypothetically of course - a particular female on a particular board message me (me as in, me - the author of this particular blog entry, not me as in her) for pics / video hosting. Its all really just a gag, which several people go for and take a bite out of the troll bait, which is all well and good. So afterwards, this particular female actually emails / sends said video as a private donation. O.o!!! No stipulations are attached to said video. Should one share it to others, perhaps even attempting to make monetary gains from it as well? Or should one simply keep it in strict confidence? (Hypothetically of course)

Such are the deeper questions of life.


p.s. Future reference, add the "sappersaur" to the CCG list

Ms Pittens...

...has taken up a new hobby (that's one of 2 cats we have). She has taken to jumping up in my lap and sitting up (like a person) and rests her front paws on either the desk or my arm, at which point, she then bathes either the desk (yes the desk) or my arm. She's a very strange little thing.

Addenda

my Backgammon AI surprisingly plays a pretty decent game. All it needs right now IMHO is a bearoff database.

Punctuation

: is clearly superior to the - . At least some people seem to think so. I never was much a : guy, or even a ; So perhaps the - is where its at? Who knows. Mysteries of the universe I suppose.

I know I said it last time, but Flash really does suck the fat one, in the most unflattering of ways. I went back to refine my checkers, and found that a little function gets called twice, when it only needed to be called once at the top of my stack. This might not seem like much, but when it was being called a second time, it was when move "n+1" was being evaluated, where n is the current search depth. This meant that this particular function was getting called alot. Taking it out, and a few minor adjustments dropped my AI think time by 50%. W00t! Well, almost a woot, its still slow as molasses.

Then I got the idea - actually I read the idea - that bitboards would be the way to go - and hey, Flash actually supports bit operations like OR,XOR, left shift, etc. Being that I don't normally program AI I hadn't used this, but I immediately saw just how clever this solution is (which its cleverness has been around for a long time, imagine my surprise). You see, we could represent the board as a bunch of 0s and 1s. A 0 would be an empty square, while a 1 would have a checker in it. So the opening board of checkers would look like:

10101010
01010101
10101010
00000000
00000000
10101010
01010101
10101010

And then you would also have a bitboard representing ONLY the red checkers, ONLY the red kings, ONLY black checkers, and ONLY black kings. And then maybe 2 more, one for all the red pieces and all the black pieces (just to make things a bit faster)

So, instead of searching through an array of pieces and positions to find valid moves, you can just use the bit operations to see what you can do.

For example, a black checker (bottom) would have a move bit board of say

00000000
00000000
00000000
00000000
00000101
000000#0
00000000
00000000

The checker would be located at # (which would still be a 0, but I put the # in there to illustrate)
You can then compare that bitboard to the one holding all the pieces and quickly see if its occupied.

The real value of this (while still helpful in checkers) would be something like chess where a rook would move something like (again the # for illustration on location)


00000010
00000010
00000010
00000010
11 11 1 1#1
00000010
00000010
00000010

Anyway, there's plenty on the subject on Google's "chess bitboard"

So here's my a great idea, that could probabyl help speed things up marvelously, but can flash do it? No! Of course not! Why? Because it sucks the big fat one remember? Bitwise operations can only return 32bit intergers which means you can toss the chess/checkers board right out the window since each square is a bit, and there are 8 rows x 8 cols of bits (that's 64 for you non math majors ;) )

Wow 2 weeks

How time flies. Turkey came and went, no big surprise there. Except that we did absolutely nothing. First time ever in my entire life, I did absolutely nothing for turkey day (and I imagine the same can be said for Mrs Megos). We had the day off from work (obviously) and basically just goofed off. No big dinner. No family over (or going to). No shopping the next day (God what an awful time that is - 2nd week working my first job I got stuck working that Friday - retail no less - and it sucked, but that's a whole other story).

Anyrate, I completed the first version of my AI Checkers game in Flash. It looks a whopping 3 moves ahead (Ooooo look out!). Why only 3 moves? Well, because Flash sucks. And sucks hard. Its fantastic for slapping together some animation quickly, or even doing card games, but just forget it when you want to crunch lots and lots of numbers quickly. At 3 moves ahead, on my p4 2.6 it took about a minute (or even two!) to come up with a move. This was just a basic minmax sequence. Upon further reflection, I think I could speed it up a bit more with some more work, but I dont think its quite worth it (and my effort to tweak it further won't be compensated). I could push it to four, five, six, whatever with some tree pruning, and make the times bearable for the extremely, but like I just said, such efforts would go unrewarded at this point. Word to the wise, if you really want to make an AI checkers to be delivered on the web (or a client) go with Java if you want a platform independant solution. I imagine Shockwave would also suffice, as some of the games I've played were quite nice, and as such, it just has to be exponentially better than Flash when it comes to handling data and such. After all, Shockwave even moved to 3d!