I am currently trying to make a chess game in Java, and have reached the move generator part. I have build the routine that finds all possible moves. Now what I want to do is sort them and prepare them for my search. I have thought of a way that is tempoary. I categorize each move in to one of the following categories: - Moves that will capture enemy queen(s). - Moves that will capture enemy medium strength units (rooks, bishops, knights) - Moves that will capture enemy pawns. - Moves that will lead to a friendly pawn promotion. - All other moves. The moves are prioritized in that order as well. So that queen capture moves are searched first and so on. So far I have created 5 arrays of arraylists to hold the moves. I then add them to a stack list, adding so that the queen is on top of the stack and will be returned first. In that way my moves will be sorted to have the most important to be searched first. Each arraylist is in an array of 15 so there is one arraylist for each ply. However making one move might invalidate old found ones, and so I'll need to rebuild the lists at each ply this will ofcourse take lots of time, and resources which should be used for other things. Which leads me to my first question is there any way of storing the moves for use in later plys and constantly keeping the list up to date on new moves, without having to build a new list for each ply? Further more does any one know any good way of sorting moves without taking too long to execute? mine is really basic so I'm sure there must be better and faster ways? Does anyone have any good suggestions as to how to do this? examples would be welcomed. I know this is not the most optimal way of doing, not even close, but I just needed to have something done so I could watch the computer start doing something. I have searched the internet alot but haven't found a guide or site that describes. How the data is stored between ply's etc. Anyway hope anyone can help me figure out a better way of storing and calculating optimal moves. Thank you :) Tommy

Quote: Original post by TommyA
[...]

However making one move might invalidate old found ones, and so I'll need to rebuild the lists at each ply this will ofcourse take lots of time, and resources which should be used for other things. Which leads me to my first question is there any way of storing the moves for use in later plys and constantly keeping the list up to date on new moves, without having to build a new list for each ply?

Building a new list for each ply is probably not such a bad idea. Keeping move lists updated has been done, but it requires a ridiculous ammount of detail in programming, and it is very hard to get bug free.

Quote:
Further more does any one know any good way of sorting moves without taking too long to execute? mine is really basic so I'm sure there must be better and faster ways?

Simple is usually good.

Quote: Does anyone have any good suggestions as to how to do this? examples would be welcomed. I know this is not the most optimal way of doing, not even close, but I just needed to have something done so I could watch the computer start doing something.

You mean other ways of sorting the moves? There are many good ideas out there. Static Exchange Evaluation is a nice one.

Quote: I have searched the internet alot but haven't found a guide or site that describes. How the data is stored between ply's etc. Anyway hope anyone can help me figure out a better way of storing and calculating optimal moves.

It may not describe what you want exactly, but Bruce Moreland's guide is very valuable.

I am sorry I am not giving you very detailed answers, but you didn't pose very specific questions.

Quote: Original post by alvaro
Building a new list for each ply is probably not such a bad idea. Keeping move lists updated has been done, but it requires a ridiculous ammount of detail in programming, and it is very hard to get bug free.

I'm really surprised to hear that, but surely if the amount of code it takes to build the routines to avoid are so huge that the benefit simply isn't big enough, I'll just stick with the current.

Quote: Simple is usually good. ...

You mean other ways of sorting the moves? There are many good ideas out there. Static Exchange Evaluation is a nice one.

I know that :) however with basic I mean real basic, my current one is a sort of basic MVV move ordering, it does not take into account the value of the attacker, but that shouldn't be too hard to implement. And yes I meant a good way of sorting the moves. Did some searching on SEE and it sounds really interesting, wasn't able to find any other article than the on you mentioned on the topic, and although it gives an idea of it, it still doesn't supply me with enough knowledge to implement it. Are you aware of any place with more information about this?

Quote: It may not describe what you want exactly, but Bruce Moreland's guide is very valuable.

It sure is... one of the best out there :)

Quote: I am sorry I am not giving you very detailed answers, but you didn't pose very specific questions.

I appreciate your reply very much... What I was trying to know was the best way of handling the move ordering routine, between ply's. One thing is the move ordering it self, which I will look into with SEE as you suggested. Another thing is how to avoid having to construct a complete list of legal moves again at next ply. However having a list for each ply won't easily allow me to share the moves. A workaround for this would be great.

I know move ordering is one of the most important issues in chess ai, so naturally I wanna make sure that this part of my game is made, the best I can.

On a sidenote:
As I said I'm implementing it in Java, and I'm not totally into the Java data containers yet, which datatype would you suggest for holding moves? did some consideration on the Stack component, but again it is simply an extended vector, so perhaps linkedlists are faster.

Thank you very much for your time, and help. I really appreciate it. Hope to be able to find out more about SEE.

I don't have time right now to go through your post point by point. Let me just point out that MVV/LVA is a reasonable order for captures. However, you should try a move from the hash tables first, if one is available. Then you need to sort the non-captures somehow. History heuristic works, or you can just use a square-piece table so you would try first moves that place pieces in natural places.

About what containers to use, I recommend plain old arrays of fixed size. Anything that allocates memory dynamically is going to kill your performance far worse than recreating the list of available moves every time.

Also, Java is fine for a toy program, but once you want real performance, you'll probably have to go with C++.

Quote: Original post by alvaro
Also, Java is fine for a toy program, but once you want real performance, you'll probably have to go with C++.

A quick reply before I'm leaving to get some sleep, will take a good look at your reply in the morning though. I am a C++ programmer, but making this game with a friend of mine, where the only language we share in common is java, that is the reason for the choice of language... Thanks for your reply, will look it through in the morning :)

Take a step back for a moment and at least consider..

Is it really necessary to have a list of moves (let alone a sorted one)?

Ok, maybe you think it is, but still.. step back again!

Is it really necessary to generate a list of ALL moves (let alone a sorted one)?


Just saying that you shouldnt jump into the design of this without thinking.. you truely do not need to generate any move lists.. and even if you do, generating all moves at once is definately sub-optimal.

There is a very common way of sorting captures by their importance called MVV/LVA.

Most Valuable Victim, Least Valuable Attacker.

The idea is that a pawn capturing a queen is much more profitable (in terms of potential cut-offs) than a queen capturing a queen.

Essentially you divide the victims value by the attackers value, and this gives you a number. Sort the captures based on this number and search them first.


Based on your post it sounds like you might be trying something wonky with your move generation. For ChessPig I generate all of the valid legal moves for a given position, and then search them one by one. I don't bother trying to generate only certain types of moves first. ChessPig is a memory hog though. This isn't really a big deal, given ChessPig only goes out to ply 30 or so, and there are only 100 (+/- 10) possible moves for any position.

Sorting doesn't have to be expensive. Sort indexes to moves, not the moves themselfs. This will save you from making expensive copy's of objects.

Moves myMoveList[112];int   moveIndex[112];moveIndex[0] = 0;..moveIndex[112] = 112;...AlphaBeta ( myMoveList[ moveIndex], ........);.

You mentioned that you're using Java. By trying to make your code 'proper' OO Java code you're going to make your Chess program very slow, and may even cause crashes on some computers. You might want to consider statically allocating all of the objects you're going to need right from the get go and reusing them.

I should mention first: Do not worry about any of this stuff until after you have your Chess program playing with at least Alpha/Beta and Quiscence searching. Those are _essential_ and should take priority over all other things.

Will

Quote: Original post by RPGeezus
There is a very common way of sorting captures by their importance called MVV/LVA.

Most Valuable Victim, Least Valuable Attacker.

The idea is that a pawn capturing a queen is much more profitable (in terms of potential cut-offs) than a queen capturing a queen.

Essentially you divide the victims value by the attackers value, and this gives you a number. Sort the captures based on this number and search them first.

...

Sorting doesn't have to be expensive. Sort indexes to moves, not the moves themselfs. This will save you from making expensive copy's of objects.

...

You mentioned that you're using Java. By trying to make your code 'proper' OO Java code you're going to make your Chess program very slow, and may even cause crashes on some computers. You might want to consider statically allocating all of the objects you're going to need right from the get go and reusing them.

I should mention first: Do not worry about any of this stuff until after you have your Chess program playing with at least Alpha/Beta and Quiscence searching. Those are _essential_ and should take priority over all other things.

Will

Thank you very much for your reply will, even though I'm using Java doesn't mean I'm trying to make it proper OO though, this I do know. It is a really interesting idea you've given me. I have looked a bit into MVV/LVA and SEE, and they seem like really proper ways of doing this, also I like your idea by just dividing the two pieces values. This is a good idea, which I will definetly try.

Your suggestion on how to sort moves is also very interesting, the memory usage shouldn't be of any concern, the focus is mainly on the AI part, so this should be a good way of doing it.

Considering the quiscence search I am about to trying to implement this feature, I will put my movegeneration a bit on hold while I do this as you suggested.

Again thanks for your reply really appreciate it.

Tommy