Chessiverse @HGM
Moderators: hgm, Rebel, chrisw
-
Daniel Shawul
- Posts: 4185
- Joined: Tue Mar 14, 2006 11:34 am
- Location: Ethiopia
Chessiverse @HGM
While reading about the 'evolution of cooperation' in repeated games, I remembered about your chessiverse project. The experiment they did was to match up all sorts of smart strategies and let them play many games in which cooperation is rewarded more. The winner was a 'tit-for-tat' strategy that first cooperates but defects if the other defected last time. So each engine has a memory of past actions of each player. I am not sure if your chessiverse project works like that and adapts to each player, but I guess the goal is to evolve a winning strategy somehow. It seems also that players actually modify their source code (strategy) in your case. Could you explain a bit about your project?
-
hgm
- Posts: 27811
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Chessiverse @HGM
I started that a long time ago, and when the laptop I used for running it broke down after two months, I stopped it, and never returned to it.
It was really a version of 'genetic programming'. I had designed a virtual machine with some interpreted byte code and a small memory. The machines were filled with random instructions, amongst which instructions they could use to probe their environment (the board representation), and to print a square.
The 'supervisor' would then pair two engines, generate a position to put them on (I only tried KQK positions), and set the virtual machine that had the move running. If it would not produce a move within a certain number of 'clock cycles', it would forfeit. If it procuded two outputs, the supervisor would interpret it as a move, and if the move was illegal, they would forfeit. Otherwise it would be played on the board, and the opponent would be set running on the new position.
After a number of rounds a ranking would be computed, the worst performing programs would be eliminated, and the remaining ones would breed offspring to replace them (by usual point mutations, crossing over of their programs). And then the next tourney would start, etc.
Initially all programs would forfeit when they had to play white. After some time they would learn to print King moves, in the hope that they would find a King or Queen on the from-square, and avoid an immediate loss. Then they discovered to test if the from-square was empty, and only print the move if it was not, but otherwise print another move. Then, they discovered the sneaky trick of making that other move exactly the opposite of the conditional one. So when they found an own piece now on the from- or to-square of their initial move, they would start moving back and forth between these squares, and could keep that up forever. This brought them so many points, that any additional trick hardly gave a measurable improvement.
I was not running the simulation with very many individuals, so the noise was high, and it often occurred an obviously more fit organism got extinct by bad luck. The back-and-forth trick got lost many times, that way, and was always rediscovered after some time (usually on another square). I learned it was really important to do this with a very large population.
The interpretation of the byte-code was very inefficient, however, and I had the feeling that I was wasting a lot of CPU time. If I would seriously want to run such a simulation with vary many individuals, and enough games per breeding cycle to be not too dependent on the 'luck of the draw' for an initial position, it could take years. So it seemed better to do it with a virtual machine that would allow compilation to x86 code, and would run an order of magnitude faster. I never got to doing that, however, being consumed by other projects.
It was really a version of 'genetic programming'. I had designed a virtual machine with some interpreted byte code and a small memory. The machines were filled with random instructions, amongst which instructions they could use to probe their environment (the board representation), and to print a square.
The 'supervisor' would then pair two engines, generate a position to put them on (I only tried KQK positions), and set the virtual machine that had the move running. If it would not produce a move within a certain number of 'clock cycles', it would forfeit. If it procuded two outputs, the supervisor would interpret it as a move, and if the move was illegal, they would forfeit. Otherwise it would be played on the board, and the opponent would be set running on the new position.
After a number of rounds a ranking would be computed, the worst performing programs would be eliminated, and the remaining ones would breed offspring to replace them (by usual point mutations, crossing over of their programs). And then the next tourney would start, etc.
Initially all programs would forfeit when they had to play white. After some time they would learn to print King moves, in the hope that they would find a King or Queen on the from-square, and avoid an immediate loss. Then they discovered to test if the from-square was empty, and only print the move if it was not, but otherwise print another move. Then, they discovered the sneaky trick of making that other move exactly the opposite of the conditional one. So when they found an own piece now on the from- or to-square of their initial move, they would start moving back and forth between these squares, and could keep that up forever. This brought them so many points, that any additional trick hardly gave a measurable improvement.
I was not running the simulation with very many individuals, so the noise was high, and it often occurred an obviously more fit organism got extinct by bad luck. The back-and-forth trick got lost many times, that way, and was always rediscovered after some time (usually on another square). I learned it was really important to do this with a very large population.
The interpretation of the byte-code was very inefficient, however, and I had the feeling that I was wasting a lot of CPU time. If I would seriously want to run such a simulation with vary many individuals, and enough games per breeding cycle to be not too dependent on the 'luck of the draw' for an initial position, it could take years. So it seemed better to do it with a virtual machine that would allow compilation to x86 code, and would run an order of magnitude faster. I never got to doing that, however, being consumed by other projects.