flat assembler
Message board for the users of flat assembler.
Index
> Projects and Ideas > [IDEA] New approach to solving the game "Checkers" |
Author |
|
UCM 06 Oct 2006, 22:26
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 |
|
Madis731 07 Oct 2006, 09:33
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 23 Oct 2007, 04:40
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 06 Nov 2007, 14:39
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 06 Nov 2007, 19:35
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 07 Nov 2007, 06:25
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 |
|
< Last Thread | Next Thread > |
Forum Rules:
|
Copyright © 1999-2024, Tomasz Grysztar. Also on GitHub, YouTube.
Website powered by rwasa.