Writing game AI is very interesting and exciting - I was convinced of this more than once from my own experience. Recently, having accidentally stumbled upon the code of my old chess program project, I decided to modify it a little and put it on GitHub . And at the same time tell about how it was created and what lessons it taught me in the process.
Start
It happened in 2009: I decided to write a simple chess program to practice developing game AI. I myself am not a chess player and I would not even say that I am a chess lover. But the task for training is quite suitable and interesting. In addition, when playing chess on the board or in the program, I was always curious why this or that move is stronger than the other. I wanted to be able to clearly see the entire tree of the development of chess positions. I have not seen such a feature in other programs - so why not write it yourself? Well, since this is training, then you need to invent and write from scratch, and not learn other algorithms and write their own implementation. In general, I think, in three days you can manage and make some kind of working version.
First version
Typically, chess engines use DFS with branch and bound algorithms to narrow the search. But this is not very clear, so it was decided: we will go our own way - let it be a breadth-first search at a fixed depth. Then there will be a complete search tree in memory, which can be visualized somehow. And also find out: a) to what depth can a chess game be calculated within the framework of the available CPU and memory resources, b) how well or badly such an algorithm will play?
I must say that at that time I had a 2-core processor with 2 or 4 GB of memory (I don't remember exactly), 32-bit Windows and a 32-bit Turbo Delphi Explorer compiler. So if the running time could still somehow be sacrificed, then the memory available to the process was limited to 2Gb. I did not know about the PE flag, which extends the user memory to 3Gb. However, since both the system and Delphi and other programs consume memory, less than a gigabyte is available for chess, so as not to go into swap.
The result was the first version of the game, consisting of the following modules:
UI - the main window, drawing a board with shapes.
Game logic - compiling a list of possible moves, making a move, detecting the end of the game.
AI: score is the evaluation function of the position.
AI: brute force - breadth first search through a queue.
UI: - , .
:
3 - , - 5-15 . 4 . .
3 - " ": - , "" , "". . , .
, , .
, : , . .
- . - - , - - . , .
:
:
: - 3, - 5 .. - 1, .
, , ( ). .
. - . ! - . - . 1-2 .
: . AI , .. , .
= (white_rate - black_rate) * (1 + 10 / (white_rate + black_rate)). , , - , .
, , . - , . - 1, - 0.4, - . .
, - .
:
:
- .
- .
- .
. , : . : ?
: - . - . - -. , 64- . 264, , 232, - - - .
"" 30-45%, 80-90%, 5-10 , . !
?
, - 2- , . , , - . :
AI - CPU .
?
AI . ?
: . , . , , . .
, "" . , .
, - . :
: 8-, 2- CPU, .
64- : , , x64. , ! x64 , x86 5-10% . 64- Delphi , .
: 32- PE- . , 1 - - "" . .
: , . - , . - , , . . , - , . .
. - . , . .. .
. . - . , , , .
. - . ? , .
AI , . AI chess.com , 1800-1900. , !
Programming game AI is a hell of a lot addictive: you always want to do better. And although I still have a lot of ideas for further development, the moment comes when I need to stop. I think it came. However, if anyone wants, they can take my code, play around, experiment, implement something. Fortunately, Delphi is now available to everyone thanks to the free Community Edition, not to mention the free Free Pascal and Lazarus. The project code (as well as the compiled exe-shnik) can be taken here (for compilation, you will also need something from https://github.com/Cooler2/ApusGameEngine ). Thanks to everyone who read it.