Chess opponent

[Lesshardtofind]

This board has been slow so I will throw something out here and see if I can get a discussions going that I can learn from. So I am making a chess game. I have made a few in the past, but this time I am actually designing before coding (a book pointed out that I have been skipping this phase) and I plan to have all the internals work independant of the GUI so I can slap whatever interface I like on top after the class is solid. The game will be pretty easy to code but the computer player is where I have notoriously gotten tripped up in the past. I have heard of a couple methods and I am not sure which approach to take. I have read that the best chess AIs reference old championship games. It seems databasing the all that info could be extremely arduous. But I wonder can I really program the AI to make good decisions without it?

What method/ approach would you use?

[Lesshardtofind]

Well my first thought is to have three difficulty levels.

Easy being the equivalent of a barbarain with a hammer. Making random moves and only occasionally taking peices intentionally. This level will rarely win, but will always take a checkmate opportunity if its capable of doing so in one move. So you can't leave yourself wide open.

Intermediate will take any piece that has a greater point value than its own. If equal or less it checks to see if the piece is defended/protected by another piece. It will look for checkmate opportunities. It will always put the player in check if able. (This will be its weakness). If no agressive moves are available it will advance a random piece to a protected square.

Advanced will do all the things intermediate does but won't risk its piece to putU the player in check. This level of the class will have the ability to create multiple game boards in stack memory. Each board can be thought of as a turn. So it will analyze the current board find the best move. Then see what is its best move on the next turn would be and then the turn after. It would only look three moves into the future and it would always take the first sequence that ended in a point value favorable sequence. (A sequence where it lost a pawn and a knight but took a queen and rook for example would be executed as soon as it was found)

Once the advanced algorithms were sufficiently efficient on processor time more turns in the future would be analyzed. The only concern I have is how demanding is looking four moves into the future will be on the cpu. It seems testing every legal move the computer has and then every legal move the human has in response to each if these moves would already take a while and it would only be one turn in the future. And you would have to add some degree of assumed intellect to the human player or it would take sequences based on moves the human would not make.

[rogster001]

I would develop this incrementally - if i was hard enough to take it on! - rather than trying to code a computer Kasaparov from the get go
I mean the board and play move stuff can be nailed fairly easily so thats one step - of course allowing for a call to the ai response functionality
Then i would look at increasingly developing the strength of response.
In some match commentary grandmasters say they barely get out of 'the openings book'
Rather than referencing old games i think you could give your ai a knowledge of openings - up to eight moves say - if the opposition is making opening line moves then your ai can just play 'the line' or change to a line variation - it probably still gets complex but its more of a lookup than decision tree thing. Often If you play against a computer you will see even on high level play that if you play known openings then it responds very fast - ie does not evaluate as such.
- Alongside the openings book you can give it 'quickmate' - when playing against a fool, AI can know a few fast win methods - but pinging the responses too fast may mean foolish human sees what is happening or gets suspicious...

middle game is where the real crunch comes as that is pretty free play.
end game lots of decision stuff obviously but there are also lots of set strategies for combinations of pieces to acheive a win - if a win is possible with the pieces available
At the end of the day chess is about evaluating a given board postion - that is how masters play multiple opponents in those famous old exhibitions - they dont need to remember everything that has happened in each of the multiple opponents boards - or even what they were planning - they just look at the position and play best move they can. - if a 'plan is still on' then that position should still reveal it anyway, but may as well be a random board placed in front of them
So i am sure you have seen some methods for applying 'points' in ai to determine the best move for a given position based on piece strength coverage, xray, etc - this is analogous to the above, - you may well search a couple of moves - or more - ahead when it is ai's turn, but each time the position is evaluated anew -i find it quite fascinating and wish i had the bottle to try and code it myself haha,

Anyway, sure you have considered all of the above already but those are my thoughts anyhow.
good luck.

PS IIRC one of the members here had coded a strong AI opponent that had won online contests - not sure if member still active, cant remember who it was but hopefully you will get a response from them

There is also i think its open source project called NagaSkaki - we used to play against it in work - maybe look it up, it has a nice feature that allows 'thinking time' while the human opponent plays - top stuff - also the game interface itslef exposes some of the AI layers in terms of tree levels of search settings and stuff

[Lesshardtofind]

Good ideas not all of which I had heard. The concept of having the computer think during the opponents move I really like. As this could reduce the amount of time the computer "appears to think" as it already thought about the players most likely move set and best responses. I know I have played people in chess and already figured out their next move and my responding move. I usually use observations of where they are looking during their turn. Maybe I could look for patterns in mouse cursor placement. Like if the player commonly hovered over the piece while thinking about the move the computer could start pre-analyzing move responses to that given piece. I also had a weird thought of having the computer make decisions on its own and logging them. Then writing each log to a file and referencing if the decision turned out good or bad and then reusing the decision if it was good. It could classify a response as really good after it works favorably like 3+ times in a row. When looking for a move it would search database -> really good -> good -> avoid bad -> make a new decision... Stoping at the first condition in the line that satisfied a move. Could be a good idea ideally, but it might fall apart when programming. I just like the idea of the computer learning from its own mistakes.

I finished my design last night for everything but the AI and started coding today so I prob won't get to the AI part until Monday or tuesday so if anyone else has ideas please don't hesitate to throw them in the mix.

[rogster001]

Like if the player commonly hovered over the piece while thinking about the move the computer could start pre-analyzing move responses to that given piece.

That would be cunning - and takes advantage of the dislocation of the players in an electronic setting, but would not truly emulate what happens in a chess game with real opponents - i am not going to sit in front of you and wave my hands over the pieces while i figure out my move. -I think your computer would implode anyway trying to have AI like that... :->
Also there is the one touch rule - in real life, masters have been known to sit on their hands to prevent them inadvertenly drawing attention to something they are thinking about or even worse - touching a piece - (which would oblige them to then play a move with it under the rule) the history of chess is full of obsessive eccentric stuff like that. - 'o course nobody is touching nada in the binary world.. but still...

Judging by the rest of what you are saying i am not sure if you are just coming up with some cool conceptual stuff rather than the actual 'lets make my program play chess' aspect. You should concentrate on making a program that can evaluate a position and return a 'best' move - Its ideal for debug build with your console speaking to you to let you know what is going on in the evaluation , dash it all i have a stack of printouts here somewhere with a really good list of values you can assign to each piece and plus /minus points depending on whats going on etc - if i find it will point you to the document, should be useful

writing each log to a file and referencing if the decision turned out good or bad and then reusing the decision if it was good. It could classify a response as really good after it works favorably like 3+ times in a row.

That is basically chess study - ie match preparation - theory - looking into the history of games blah - its what them crazy cats do - masses of information compiled and analysed that they dip into - i wonder how the grandmasters actually get any enjoyment out of the game - but then i - you - most people could never know - simply could not bring a game out of somebody like kasparov .. if you see what i am saying.. not really relevant to your programming post though - sorry...!

[rogster001]

And you would have to add some degree of assumed intellect to the human player

- agreed - with the tentative exclusion of turbo C users asking for finished homework

[cyberfish]

PS IIRC one of the members here had coded a strong AI opponent that had won online contests - not sure if member still active, cant remember who it was but hopefully you will get a response from them

That would be me I think. It's not very strong compared to many other chess AIs, but it does play at FIDE masters level - Brainless

Some advices:
1. If you want to focus on the AI and not all the interface coding (which would take a significant amount of time and is not very interesting), you can just write an AI that implements either the xboard protocol (Chess Engine Communication Protocol), or the UCI protocol (UCI protocol). Then you can just use any of the hundreds of chess GUIs available as your GUI.

2. There have been some experiments on machine learning/pattern recognition-based AIs, but they are extremely difficult and even the state of art ones are still below human beginner level.

3. Most AIs divide the game into 3 phases - the opening, midgame, and ending.

In the opening, most programs use an opening book (database of positions -> moves from master games) because there aren't many opening positions and playing well in the opening requires very good "intuition" and strategy (vs tactic), which is what computers are bad at compared to top humans.

In the midgame, databases don't really work because there are so many variations that you'll probably never see the same situation twice, and it's very hard to apply knowledge from "similar situations". You'll need to do a depth-bound minimax/negamax (Minimax - Wikipedia, the free encyclopedia) search with a good static evaluation function to find the best move. This is the funnest part of chess programming because there are dozens of optimizations you can do in this stage that will make your program significantly stronger.

In the endgame (5-6 pieces left from both sides combined), most of the strongest programs revert back to database again (google "EGTB"), which is ok because the number of possible situations are small again due to the low number of pieces. However, the advantage here is much smaller than in opening. A lot of programs continue the midgame strategy into endgame, and with a proper evaluation function, they can still play very well in endgame. EGBTs are more for things like very difficult long checkmates that are hard to find in brute force search (like king+bishop+knight vs king). I wouldn't worry about this for now - just continue midgame strategy into endgame.

Play the opening like a book, the middle game like a magician, and the endgame like a machine. – Rudolf Spielmann

[cyberfish]

PS IIRC one of the members here had coded a strong AI opponent that had won online contests - not sure if member still active, cant remember who it was but hopefully you will get a response from them

That would be me I think. It's not very strong compared to many other chess AIs, but it does play at FIDE masters level - Brainless

Some advices:
1. If you want to focus on the AI and not all the interface coding (which would take a significant amount of time and is not very interesting), you can just write an AI that implements either the xboard protocol (Chess Engine Communication Protocol), or the UCI protocol (UCI protocol). Then you can just use any of the hundreds of chess GUIs available as your GUI.

2. There have been some experiments on machine learning/pattern recognition-based AIs, but they are extremely difficult and even the state of art ones are still below human beginner level.

3. Most AIs divide the game into 3 phases - the opening, midgame, and ending.

In the opening, most programs use an opening book (database of positions -> moves from master games) because there aren't many opening positions and playing well in the opening requires very good "intuition" and strategy (vs tactic), which is what computers are bad at compared to top humans.

In the midgame, databases don't really work because there are so many variations that you'll probably never see the same situation twice, and it's very hard to apply knowledge from "similar situations". You'll need to do a depth-bound minimax/negamax (Minimax - Wikipedia, the free encyclopedia) search with a good static evaluation function to find the best move. This is the funnest part of chess programming because there are dozens of optimizations you can do in this stage that will make your program significantly stronger.

In the endgame (5-6 pieces left from both sides combined), most of the strongest programs revert back to database again (google "EGTB"), which is ok because the number of possible situations are small again due to the low number of pieces. However, the advantage here is much smaller than in opening. A lot of programs continue the midgame strategy into endgame, and with a proper evaluation function, they can still play very well in endgame. EGBTs are more for things like very difficult long checkmates that are hard to find in brute force search (like king+bishop+knight vs king). I wouldn't worry about this for now - just continue midgame strategy into endgame.

Play the opening like a book, the middle game like a magician, and the endgame like a machine. – Rudolf Spielmann

[Lesshardtofind]

Yea I was just about to make a post on here about minmax trees. I just found five or six articles on it. And I sighed because binary trees have been one of my programming downfalls lol. As for the implimentation I just finished the chess engine. The controller of the game that recieves signals from th GUI ... I want to be familiar with it because I planned on using it to learn some win APIGui stuff when my petzold book comes in the mail. I also contemplated trying a 3d chess gui in openGL as I already have datafiles of some pictures I drew in 3d max a few years ago. Plus leaving it uncommited to a GUI has made finding bugs really easy just using a second console panel to track my variables and simulate situations without adjusting the actual logic code until I know exactly where a bug is.

I also came across bitboards which I had never thought of using a series of 64 bits to represent different informations about the board. Considering I built my entire engine around the old school 8x8 I am worried I already limit the AIs final abilities vs Computational Speed. As for it being the most fun part I totally agree. I build a sudoku solver few years ago and once it was faster and smarter than me at solving I was pretty excited. I remember the first one it solved took it like five minutes and by the last update it was solving/generating easy sudokus in under 2 seconds.

I think I might have to pause the AI programming and try a few tutorials on binary trees. I don't want my first attempt to be on a giant chess ai or I'll be tearing my hair out trying to find glitches for hours on end lol. Some real interesting articles on trying to simulate neural networks to make chess Ai out there too.

Thanks for the three phases information I had not stumbled on that yet and i know its going to help. I would have strarted trying the tree from the start. I am going to have to spend a pretty good amount of designing this before coding. It seems like it would be really easy to leave a gaping whole in the code.

[cyberfish]

Chess AI is definitely not a good first project if you don't have prior AI experience. It's a very difficult problem.

[Lesshardtofind]

Challenge Accepted!

[rogster001]

It's a very difficult problem

Indeed - Quite a lot of research time and money has gone into it in the past - Because developing an ideal ' chess ' AI has applications in things like long term economic forecasting.

As a side point to this I think Deep Blue which beat Kasparov - Is now being used to manage call centre traffic somewhere. That was an answer in a highbrow quiz show we have on tv here - QI

[Lesshardtofind]

From what I read it completely revolutionized the way computer AI algorithms were written and led to the creation of most modern AI. Apparently GO an Asian board game is now the new frontier in computer AI. The chess AI concept is commonly considered as important for the development of AI and computer algorithms as the fruit fly experiments are considered for genetic engineering.

[rogster001]

GO is seen as very difficult to model yes - there are 'grey areas' which humans handle by deciding between themselves if the game is over or not / stone is dead or not, - they extrapolate out from a position and try and say if it could ever be 'given life' -and it gets quite Zen - but telling a computer how to make that evaluation is bit tricky i suppose..! I tried to get into Go for a while, played against an online computer version, got hammered by it all the time, then beat it once, never went back haha

[cyberfish]

If you don't have prior experience with minimax, one thing I would suggest is doing a tic-tac-toe AI first.

It's of course much much simpler, but it will give you very good "feel" of what minimax is all about. Should only take about 2 hours if you REALLY understand minimax. It will definitely help with chess AI.