Chess and Heuristics

[Happy_Reaper]

Hi guys, I have a topic I think everyone on the boards can help with. So lately I've been doing this AI class, and as a term project, we've been asked to create basically a Smess player (Smess being a dumbed down version of chess). Here's an explanation of the game if you're interested :

http://www.chessvariants.com/other.dir/smess.html

Anyhow, the idea here is that I have to create a player that will compete against the players of other people in the class. Further, it is all being done in Java, so I'm not gonna be asking for any code or nothing from you guys.

However, what you could help me with is heuristics, aka what makes a move good and what makes a move bad. I like to think that most people here have probably played chess at least once or twice in their lives, and it is from that experience that I would like to draw. A good heuristic in chess is likely to be a good heuristic in Smess.

So, basically, the question is : when you guys were playing chess, what was your thought process ? What made you decide what good moves were and what bad moves were ? How did you decide ?

Get the idea ? All sharing would be greatly appreciated, and it would be my pleasure to give credit to where it is due if I use anything that has been suggested here.

Thanks in advance.

[dac]

id love to do AI. with studying computing and psychology im naturally attracted to AI. i think your onto a winner by asking people to write down their thought process during a move.

you could perhaps break that down, and down again into a set of logical operations within the brain. and then perhaps build up some rules/laws/algorithms etc as to create an AI program.

good luck with it mate.

[IfYouSaySo]

Eh...Ok I don't quite understand. But let me see if I got this right.

1) direction that a piece moves is determined by the square that it is on.
2)A ninny moves one square
3) Numscull moves any number of squares in the direction indicated by the square its on. Can't jump.
4) Brain moves one square. It's like the king, so once it's captured its the end.

So my questions are:
1) Capture is done when you land on opposing piece?
2) For the numscull, does it move in straight lines, determined by the origin square, or is the direction re-evaluated as it moves over new squares (meaning it can "turn corners" so to speak).

First of all, you'll want to learn the min-max/alpha-beta algorithm, because that's how chess is done. Then you need to assign values to the three pieces. Maybe ninny=1, numscull=5, brain=infinity or something. And then simply using alpha beta and trying to maximize the score, should get you pretty far.

[whiteflags]

http://en.wikipedia.org/wiki/Transposition_table

http://chess.about.com/library/weekly/aa04d24.htm
Glancing over the stuff in the chess section of about.com can give you some idea of how people evaluate positions. I haven't played chess in a while so I'm sorry I can't be of more help.

[Happy_Reaper]

Ok, so you guys seem to have the rules down half decently. Numskulls move in any number of squares in one of the directions specified in the square it originated. It cannot change directions as it is moving (it is sort of like a Queen, so to speak.)

However, although I will gladly answer questions about the game, you need not worry about it. Chess heuristics will do (although Smess ones will be appreciated as well, just not needed).

As for Minimax, the algorithm has already been done, but given that I have a 5 sec deadline to move, and a limited amount of space (I think 200 MB) to run in, as well as the potential very large branching factor, a depth of more than 2 has often turned out innefficient (and often caused timeouts).

Essentially, what'd be great is if a way to prune bad branches straight of the tree and not expand them which could then allow me a little more depth.

And thanks for the link, citizen.

[IfYouSaySo]

Essentially, what'd be great is if a way to prune bad branches straight of the tree and not expand them which could then allow me a little more depth

Yes. That is what alpha-beta does for you. It is an optimization over min-max. And a depth of 2 seems pretty bad...and 5 seconds should actually be quite a lot of time...I would think you could get to depth 4-5 fairly easily...

But I guess what you are really asking is how to write your evaluation function. Or what kinds of heuristics can be put into your evaluation function?

Ok, I know that for example, the order that you evaluate moves in alpha-beta is very important. So if you can guess the best first move, you will prune more branches later. So you need a heuristic that orders your candidate moves, from your guess of best to worst. In chess, I believe the order goes something like 1) look at captures first, 2) look at forward moves next, 3) then everything else.

Next there is something called quiescence search. The idea is that even if you reach your cut-off depth, it makes sense to keep looking until the position is "quiet". In other words, don't stop searching until you are at the end of a capture sequence.

[IfYouSaySo]

Also, it looks like the value of any given piece needs to be modified by some mobility factor. Because for example, a ninny that can only move in two directions is worth much less than a ninny that can move in 8 directions. Not sure which way to approach this--do you simply look at moves to high mobility squares first, and let alpha beta take care of cutoffs? Or do you score the value of a piece higher when it is on a high mobility square? I would guess the second; but then the question is how important is occupation of high mobility squares? I.e. at what point would occupation of these squares equal the value of a ninny? Interesting stuff...

[Happy_Reaper]

Yeah, I was thinking about alpha-beta pruning, but I'm sort of half-and-half about that idea. Frankly, the reason that the depth is so small is because the branching factor becomes really large when a lot of ninnys gain mobility (I would go so far as to say that it becomes bigger than that of chess).

I agree however, that if you order the moves to look at in an alpha-beta search, it could probably improve the searching. That in fact sounds like a decent idea, but again, knowing that ordering would sort of is bring us back to the same initial problem of what a good/bad move is.

As for the mobility factor, I'd thought of that before and was thinking of having something called a guess a Board Position structure which would keep track of the "threat" squares of all my pieces. This would be rather inexpensive, as I could do most of the computation within the first move, and then subsequent moves would just have to update it.

And that's the other thing I don't get. Technically, once my initial minimax tree is built, my player shouldn't be spending nearly as much time rebuilding it, as it only gets updated with 2 levels every move. Yet somehow, its still slow.

One other thing : lately I've been thinking of putting time into statistical anlaysis of an opponent's move to determine future moves. I figure that since I'll be facing computers, they will all follow a formula which, albeit complex, will technically never change (this is an assumption I am making, not a fact), so the more moves they make, the more I'll have an idea what that formula is. Once I know the formula, then I'm in business. You guys think this is a worthwhile effort ?

[IfYouSaySo]

Well I still think alpha-beta is a good idea. It's really not that difficult once you have min-max in place. And consider it this way: If you get your move-order heuristic all wrong, the worst case performance is the same performance you get from min-max. But if you get it right, the best case performance is much much better (I forget exactly how much you get...I think it's something like 10-20% speedup).

As far as move ordering goes, a very simple way is to look at moves which are captures first, then look at moves that go forward on the board, then everything else.

Finally, in terms of mobility. Let's say you value a ninny at 1.0. Then I would add something like .10 for each additional direction that it can move. So for example, a ninny that can only move in 1 direction is valued at 1.1, while a ninny that can move in all 8 direction is valued at 1.8. So what ends up happening is the computer will favor variations where the pieces move to high-mobility squares.

Now, statistical analysis. Well...I think you're looking at a problem that can't be predicted by statistics. The only way to know the next move is by searching the game tree and finding the variation with the highest score. However, if the programs are running on different computers, this is what you can do. Once your 5 seconds is elapsed, you make a move. Next, you assume that whatever you calculated in your primary variation for the opponents best move, is what the opponent will play. So now you know your opponents next move. Now, you begin calculating your next move, as if your opponent had already moved. You can do this extra calculation on your opponents time, meaning you effectively have 10 seconds to calculate each move.

Next you asked about min-max tree already being built etc. Usually the min-max tree is built on the stack. So it's built up and destroyed each time. A transposition table is the way around that. You store previously analysed positions, and before you evaluate any given position, you check if you already have an evaluation for it. But it is kind of tricky...because if you have position X evaluated as +.80 at depth 3, but now you're going to go 4-5 ply deep, X may have a different evaluation. Personally, for a school project, unless you have a lot of time on this, I would just do alpha-beta, move-ordering, and work on making a very fast evaluation funciton.

[Happy_Reaper]

Ok, I'll take these suggestions to mind and get to work. I'll report back what's up in a few days.