flat assembler
Message board for the users of flat assembler.

 Index > Projects and Ideas > [IDEA] New approach to solving the game "Checkers"
Author

Joined: 25 Sep 2003
Posts: 2140
Location: Estonia
Now that we'we got 64-bit computers at the doorstep (some have already invited them in ) its time to take a new look at some old stuff. Many algorithms can be optimized by the new registers we have and of course the 100% wider registers.
I've been running a few threads in my head for quite a few nights now and its time to let you know what debugger has found this far.
The Checkers is a simplified variant of Chess. Where instead of 64 squares you are only to browse around half of them. Chess is relatively easy game, but still requires tactics/strategy to come out as a winner. The rules are mostly known to people but just to be clear:
Rules (of course there are many variants)
------
You can move your pieces diagonally one square at a time to a free spot on the board. You can do this only to the opposite player's direction. You can jump over the opponent's pieces to "eat" them.
There's another set of rules for "kings", but it doesn't concern us at this time.
------
The general programming applies binary- or other trees to both Chess and Checkers to predict the opponents moves and pick the optimal ones out of them. Trees can be rebuilt every move or by updating the previous ones.

A totally different approach can be brought to Checkers where 64-bit computing can help.
There are 3 states that every square on the board can be in. These are: empty, white (piece), black (piece). We need at least 2 bits to hold that kind of info. Though there are 8x8 squares on the board, only half of them are playable so 64/2=32 squares need to be stored as states and when each occupies 2 bits it totals 32*2=64 bits.
If we agree on the state constants:
Code:
```  EMPTY=00b
WHITE=01b
BLACK=10b
```

we can actualize the starting positions in a 64-bit registers by saying this to the CPU:
Code:
```  mov rax,5555550000AAAAAAh
```

Now that rax holds the starting position of the Checkers game we can draw very interesting colclusions.
The least expensive *theoretical* operation on any Checkers move takes 1 clock (or 1 uop on current CPUs).
You can save/load every state of the game to/from a 64-bit memory location that usually in a cached manner takes 5 clocks or less.

There's more to it. Specifically there is one important fact that is necessary for fast evaluation of board state at hand. If you do the population count, then its 24 that tells you the amount of pieces on the board. But if you remember we defined white and black as 01b and 10b. This is useful because when you AND rax with 01010101... or 10101010... you have effectively applied a filter on the board. The first filters out all the black pieces, while the second all the white ones. The population count after that is 12 for both colours (only at the beginning of the game).

When you need to move, the things get a bit (hehe bit) more complicated. With every move, you need to reset the bit where you move from and set the bit where you move to. Notice that you don't have to (re)set more than one bit! This can be done with AND/OR commands or special BTR/BTS commands. You can even use XOR or BTC for unified purpose. I think there are even clever tricks with rotations and carry, but that will most probably be more pain than gain

There's one easy example for the first move (white begins):
Code:
```  mov rax,5555550000AAAAAAh ;Opening
mov rbx,rax               ;Copy the board
and rbx,0C00000h          ;Pick out the interesting piece
xor rax,rbx               ;Pick up the button (A3)
shl rbx,8                 ;and
xor rax,rbx               ;lay it down (B4)
```

That isn't a very clean approach, but works. If you'd like to see a one clock move, then here you go:
Code:
```  mov rax,5555550000AAAAAAh ;Opening
xor rax,0000000080800000h ;Move white A3->B4
```

You have seen only white moves, but what happens with blacks. The 64-bit instructions won't let you handle more than 32 bits very easily. That is where we turn the table around. You can imagine in real world you need to turn the table around to "see" it better.
We're using:
Code:
```  mov rax,5555550000AAAAAAh ;Opening
bswap rax                 ;Turn it around
```

to do that. The BSWAP instruction only swaps bytes so it actually doesn't really turn the table around but rather invert (mirror) it. Why doesn't that bother us is that the proximity of the buttons remain the same. You can still go from i.e. H6->G5. Btw each byte in the register is exactly four pieces! The move you *actually* make is G3->H4 but it won't come out so expressively so you may as well forget it.

Now there are some different rules that need to be applied. When in real life you move your pieces diagonally then in the register you move from one byte to another. There are usually two possibilities to move (except the borders), one of them is moving exactly 8 bits (one byte), the other depends on the row your piece situates. When its on an odd row it can only move 8 or 10 bits (white) in one direction and 8 or 6 bits (black) to other direction. On even rows the numbers are 8 or 6 for white and 8 or 10 for black.

There's some thoughts thrown out. I hope there are implementers out there. I'm going to put these ideas in Prolog (my school project), but others might try doing that in FASM. Maybe even make a hyper-fast brute force for Checkers

Cheers,

_________________
My updated idol http://www.agner.org/optimize/
06 Oct 2006, 21:15
UCM

Joined: 25 Feb 2005
Posts: 285
UCM
This seems to be very interesting.. unfortunately, it is not possible to play a "real" game of checkers like this, because of the kings.
However, I would be very interested if somebody actually created something out of this.
06 Oct 2006, 22:26

Joined: 25 Sep 2003
Posts: 2140
Location: Estonia
Yeah - the kings are problematic. There are 5 different states then. Although usually when there are kings, the game has probably very few pieces on the board and you can dynamically move to other algorithms. This idea is just to pack Checkers into minimal amount of memory. You can i.e. make use of MMX or XMM (not very probable...) to hold many states and operate on them.

I'm trying to get over some issues still and if I'm able to do that, I'll post them here.
07 Oct 2006, 09:33
bitRAKE

Joined: 21 Jul 2003
Posts: 2937
Location: vpcmipstrm
bitRAKE
I thought the same thing and tried to put together some algorithms for MMX registers. I was aiming for just a very dumb brute force algorithm - hopefully so fast that it doesn't matter how dumb it is. For example, no pruning of decision tree for duplicate branches.

First find possible moves in four directions, and push them onto the stack to itterate through them for the opponents move. The moves are cleared as the tree is tracked forward - leaving the remaining move mask on the stack. So, it quickly jumps to a depth and rates that position. When the popped mask is zero then go up a level.

Of course, there is a lot of redundancy, but if a million moves could be looked at each second it should do okay against a human. Project was put aside about two years ago, though.
23 Oct 2007, 04:40
Raedwulf

Joined: 13 Jul 2005
Posts: 375
Location: United Kingdom
Raedwulf
8x8 draughts have been solved btw That no matter the opening move you make, the outcome of the game will be a draw if both sides play perfectly.

It came to mind to start a project with chess... with 64-bit bit-boards which would be quite fast. Any takers?
06 Nov 2007, 14:39
bitRAKE

Joined: 21 Jul 2003
Posts: 2937
Location: vpcmipstrm
bitRAKE
IIRC, there is atleast one very active chess person in alt.lang.asm group. Or, rather I remember several optimization threads with regard to bitboads for chess there.

Chess doesn't seem doable with just low level move generation - a high-level pattern matching and/or position evaluator seem required. Checkers on the other hand has a very simple board evaluation that works for okay game play.

As the cost of board evaluation increases it becomes more important to prune the move tree. Furthermore, this makes Chess is an exercise in efficient data structures to manage all the 'expert' pruning methods.

(Of course this isn't true if you have specialized hardware to look at 500mil moves/sec: Deep Thought = 10 moves ahead. PC's aren't quite there, yet.)

We can imagine a future multi-core processor or GPU that would be able to brute force with a simple evaluator!

[edit: http://en.wikipedia.org/wiki/Rybka seems intriguing!]
06 Nov 2007, 19:35
Raedwulf

Joined: 13 Jul 2005
Posts: 375
Location: United Kingdom
Raedwulf
Haha yes I read http://en.wikipedia.org/wiki/Rybka yesterday lol .

Ok sounds interesting but maybe an ambitious project using x86-64 assembly might be doable? I dunno just speculating here .
07 Nov 2007, 06:25
 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First

 Jump to: Select a forum Official----------------AssemblyPeripheria General----------------MainDOSWindowsLinuxUnixMenuetOS Specific----------------MacroinstructionsCompiler InternalsIDE DevelopmentOS ConstructionNon-x86 architecturesHigh Level LanguagesProgramming Language DesignProjects and IdeasExamples and Tutorials Other----------------FeedbackHeapTest Area

Forum Rules:
 You cannot post new topics in this forumYou cannot reply to topics in this forumYou cannot edit your posts in this forumYou cannot delete your posts in this forumYou cannot vote in polls in this forumYou cannot attach files in this forumYou can download files in this forum