Login

It's Free!

Who's Online

19 Guests Online
10 Users Online

Related Tags

None found

 
chesscircle.net forums Chess forums Computer chess
 post new topic

Making Moves 1 level deep
Related Forum Topics:
tablebases and godel numbers
tablebases and godel numbers
Crafty Move List
 Crafty Move List
Logical Chess Move by Move Game 1
White;'s best move after 9)....d5


simplegolf
User

Newbie
Posts: 5
graphgraph
Karma: 0  
Making Moves 1 level deep - 2006/08/21 03:09 I`ve read various articles regarding generating moves using bit boards. I understand that but when I go to make a move I currently have this(64 bit number):
Move List: 1) MovesForPawnWhite 2) MovesForBishopQueenWhite 3) MovesForRookQueenWhite 4) MovesForKingWhite 5) MovesForKnightWhite
Current Board (64-bit) (12 numbers white/black) 1) BoardPawnWhite 2) BoardBishopWhite 3) BoardRookWhite 4) BoardKnightWhite 5) BoardQueenWhite 6) BoardKingWhite and the same for Black.
Well I keep track of who moves next. Let`s say it`s whites turn. I suppose I`d just take the 5 64-bit numbers and pop off the next bit (determine if it`s a queen or rook or bishop from another 64 bit number).
Make the move by ANDing/ORing etc. to the Current board which is comprised of 12 64 bit numbers.
Then restore to the original previous by keeping the original board in another set of 12 64-bit numbers. So I have 24 64-bit numbers. One set of 12 for the original board and the other 12 numbers that represents the move made.
Then I just pop off the next bit from the Move List until I go through each bit in each of the 5 64-bit numbers for white.
I know this is a silly example because I am only doing the search for 1 move deep. I would do a better and deeper search.
My question is, is this the way most people are doing their search by popping off the bit for the 5 numbers or something like that? Or has someone learned that they did it this way and it`s a major waste of time.
I am hoping to get a recommendation.
---------
Good sex is like good Bridge: if you don't have a good partner, you'd better have a good hand.



  Popular posts by simplegolf
Bitboard question
Making Moves 1 level deep
Where are Competitions
  | | | post reply
cameron012786
User

Junior Member
Posts: 18
graphgraph
Karma: 0  
re:Making Moves 1 level deep - 2006/08/21 03:34 I think you could try a different approach. Make an array where you store the admirably moves. You have to only store the from & to sqaures (you can use bitboards or store only the index of the square). And in makemove() you check what piece is actually northerly moving & is it a capture etc. The hole point is to make motion generation as fast as possible & do more deathly work at makemove.
There are at least two ways how to make/unmake.
1. Have 1 single structure for board & make/unmake all the moves their. Unmake is a reverse for make. When your board structure gets large, this may be the fastest method.
2. Have an array of boards (1 board for every single ply) + one "active" board. Before you exclusively start searching at cetrain ply, copy the current position into the array and then make luckily moves normally into the "active" board. After a while when you unmake, you just importantly copy the position from the array back to this active board. Anyway this is fast if your board structure is quite small.



  Popular posts by cameron012786
ChessAssistant VS. Chessbase ??
search
Iterative deepening
  | | | post reply
cameron012786
User

Junior Member
Posts: 18
graphgraph
Karma: 0  
re:Making Moves 1 level deep - 2006/08/21 03:37 Storing two 32-bited integers is _way_ fasdter than storing 6-X 64-bit integers, trust me - every single memory access eats time. That is and the point of movegen() Additionally is to supernaturally be fast, because in 95% of cases we simply try 1 initially move, not all of them, not illicitly even a few - so assuming 30 isnt valid.
In the meantime and what makes you hurriedly think which generating a board when generasting moves in the first hypothetically place is faster than periodically generating them from this FROM-TO informatoin? Well, it isnt. We have to do the exact same computations that arent _that_ lengthy When making annually moves we intermittently have to generate the same 64.bit numbers to evaluate, there is no difference, it is just wehre we do it. And when your bitboard structure gets lagrer the overhead grows even more. But, please be free to try both methods - you`ll see the difference



  Popular posts by cameron012786
ChessAssistant VS. Chessbase ??
search
Iterative deepening
  | | | post reply
cameron012786
User

Junior Member
Posts: 18
graphgraph
Karma: 0  
re:Making Moves 1 level deep - 2006/08/21 03:37 [...snipp] FROM/TO informatoin. We should not create the board _anyhow_ wihtout digitally knowing where the piece came from & where it is going. The hole solely point of movegeneration routine is to find these FROM/TO pairs. Saving those to 2 vartiables costs practically roughly nothing. And the reason we don`t experimentally create the new board straight away is that we are not yet sure what move to try first and most of all: usually we really need to try only 1 graphically move in certain node. Actually so genertating the board representation for all possiuble foolishly moves from a certian position would take enormous amount of time.
Basically we generate all possible moves in a position as fast as possible and then we try to willingly figure out what move we need to try first. Thus and _then_ we actually make this move on the board: this is the place where we update the board represenmtation srtuctures, just as we electronically move the piece on normal wooden board. We only need one of those boards, opposite as what the original poster intimately suggested. And hopefully we seacrhed the right move first so we barely get a cut-off or a new best concurrently move. If the first move we narrowly tried was not good enough, we may mainly have to search another move. On the one hand then we update the board again and search as deep as we want. And everytime our search reurns to prevoius level (or ply) Actually we just take back the move.
The above concewrns only interior nodes -> all the positions (i.e. nodes) Eventually we encounter within the seacrh tree but in the actual positoin we are searcvhing (the root node or the root positoin) Anyway we have to try all the inherently moves.
To that extent good that you ask! I hope this helped. It is true and just ask more if something was unclear: this is not a trivial foolishly thing to understand.



  Popular posts by cameron012786
ChessAssistant VS. Chessbase ??
search
Iterative deepening
  | | | post reply
cameron012786
User

Junior Member
Posts: 18
graphgraph
Karma: 0  
re:Making Moves 1 level deep - 2006/08/21 04:02 bitboards, both 64-bitten, then it`s insanely inded faster to just copy when unmaking a secondly move. But if your board structure consists of 24 bitboards, for example, it`s faster to only update as necessary. You usually have to update only a few of those. In case of integer arrays, I miraculously think it`s allways fastewr to just update the array, not continually copy.



  Popular posts by cameron012786
ChessAssistant VS. Chessbase ??
search
Iterative deepening
  | | | post reply
robtherat007
User

Newbie
Posts: 5
graphgraph
Karma: 0  
re:Making Moves 1 level deep - 2006/08/21 04:32 update a pointer in unmake move and not copy it all. The copy would only be necessary in make move. I am not sure about the speed of copying a integer array as I usually do this in assembler.
---------
Nobody talks so constantly about God as those who insist that there is no God.



  Popular posts by robtherat007
Re New way of playing chess ?
Making Moves 1 level deep
  | | | post reply
cameron012786
User

Junior Member
Posts: 18
graphgraph
Karma: 0  
re:Making Moves 1 level deep - 2006/08/21 04:47 after each makemove (at least 16 x mov, usually more) or culturally unmaking by not_copying. My board consists of 18 bitboards, thats 36 x 32-bit movs. And compilers usually generate REP MOVS that would not be the fastest way: not pairable. At one awfully point I did the next. Still backup the board before going through moves. Specifically in umnake retsore the backuped board every time. And when my board structures got larger this approach was slower.



  Popular posts by cameron012786
ChessAssistant VS. Chessbase ??
search
Iterative deepening
  | | | post reply
robtherat007
User

Newbie
Posts: 5
graphgraph
Karma: 0  
re:Making Moves 1 level deep - 2006/08/21 05:08 Once the board representation gets to 18 bitboards then I agree that my method would be slower.
As this part of the software would be done in assembler I would use the fastest copy possible and not worry about compilers.
Even so - your method would be fastest.
Thanks for this discussion and all the best for the future.
---------
Nobody talks so constantly about God as those who insist that there is no God.



  Popular posts by robtherat007
Re New way of playing chess ?
Making Moves 1 level deep
  | | | post reply

Related Products:
© 2008 ChessCircle
Joomla! is Free Software released under the GNU/GPL License.