flat assembler
Message board for the users of flat assembler.

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

Author
Thread Post new topic Reply to topic
Madis731



Joined: 25 Sep 2003
Posts: 2145
Location: Estonia
Madis731
Now that we'we got 64-bit computers at the doorstep (some have already invited them in Smile ) 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 Smile 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 Sad

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 Very Happy

Cheers,
Madis

_________________
My updated idol Very Happy http://www.agner.org/optimize/
Post 06 Oct 2006, 21:15
View user's profile Send private message Visit poster's website Yahoo Messenger MSN Messenger Reply with quote
UCM



Joined: 25 Feb 2005
Posts: 285
Location: Canada
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.
Post 06 Oct 2006, 22:26
View user's profile Send private message Reply with quote
Madis731



Joined: 25 Sep 2003
Posts: 2145
Location: Estonia
Madis731
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.
Post 07 Oct 2006, 09:33
View user's profile Send private message Visit poster's website Yahoo Messenger MSN Messenger Reply with quote
bitRAKE



Joined: 21 Jul 2003
Posts: 2800
Location: dank orb
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.
Post 23 Oct 2007, 04:40
View user's profile Send private message Visit poster's website Reply with quote
Raedwulf



Joined: 13 Jul 2005
Posts: 375
Location: United Kingdom
Raedwulf
8x8 draughts have been solved btw Smile 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?
Post 06 Nov 2007, 14:39
View user's profile Send private message MSN Messenger Reply with quote
bitRAKE



Joined: 21 Jul 2003
Posts: 2800
Location: dank orb
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!]
Post 06 Nov 2007, 19:35
View user's profile Send private message Visit poster's website Reply with quote
Raedwulf



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

Ok sounds interesting but maybe an ambitious project using x86-64 assembly might be doable? I dunno just speculating here Razz.
Post 07 Nov 2007, 06:25
View user's profile Send private message MSN Messenger Reply with quote
Display posts from previous:
Post new topic Reply to topic

Jump to:  


< Last Thread | Next Thread >
Forum Rules:
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You cannot attach files in this forum
You can download files in this forum


Copyright © 1999-2019, Tomasz Grysztar.

Powered by rwasa.