Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

A step-by-step guide to building a simple chess AI

medium.com

Post reply on HN
Print view View original

11–20 of 44 posts

Re: A step-by-step guide to building a simple chess AI

#11

Post by tbrake »

maxmcd wrote: post #7
woliveirajr wrote: post #5

Earlier quoted context omitted.

Never checked but somehow got me surprised: aren't all chess engines deterministic? The same program, given the same input, should give the same output unless it is specifically programed to try to avoid it (and then we have PRNGs).

A reply that was deleted mentioned that some engines use Monte Carlo simulations which are non-deterministic (?). My experience with chess engines being non-deterministic is that if I pick the same opening I don't always play the same game with the same engine. I really might just be off here, and that variance might be related to random artificial handicapping.

Most chess engine opening books weight their branches to pick certain moves x% of the time, and offer 0 or negative value to 'bad moves' never to pick.

e.g. 1.e4, d4, c4 and Nf3 will get picked more often than 1. b3, c3, nc3 and f4, and 1. g3, e3 even less (or not at all).

Re: A step-by-step guide to building a simple chess AI

#12

Post by throwaway7645 »

lspears wrote: post #9

Love this article. I went through a lot of these same steps when I was tinkering with my own chess bot. Bitboard representation with bitshifting operations can dramatically speed everything up (see here https://chessprogramming.wikispaces.com/Bitboards ). Another easy step is to integrate an opening book. The "Encyclopaedia of Chess Openings" provide a great set. Here is link to CSV of the openings for easy parsing:…

Thank you!

Re: A step-by-step guide to building a simple chess AI

#13

Post by jimsmart »

woliveirajr wrote: post #5
maxmcd wrote: post #2

Interesting that it's deterministic. I can get it to play the same game again and again. Why is this not the case with more advanced chess engines? Edit: Apparently single-threaded stockfish is deterministic. Maybe my experience with non-deterministic chess engines just has to do with the handicapping related to providing easier levels of play.

Never checked but somehow got me surprised: aren't all chess engines deterministic? The same program, given the same input, should give the same output unless it is specifically programed to try to avoid it (and then we have PRNGs).

Unless efforts are made for results to be deterministic, concurrent algorithms may complete their work / return their results in an ordering that is unstable (depending mostly on host OS and CPU management of time-slicing).

Re: A step-by-step guide to building a simple chess AI

#14

Post by Recursing »

I think sunfish (https://github.com/thomasahle/sunfish/blob/master/sunfish.py) would be a much better example of a simple chess AI (~100 lines of python code), even if it's not very well documented.

The article doesn't talk about very important concepts like quiescence search (https://chessprogramming.wikispaces.com/Quiescence+Search )

Sunfish doesn't use any of the "further improvements" proposed in the article and still performs much better

Re: A step-by-step guide to building a simple chess AI

#16

Post by pavs »

vishvananda wrote: post #10
woliveirajr wrote: post #5

Earlier quoted context omitted.

Never checked but somehow got me surprised: aren't all chess engines deterministic? The same program, given the same input, should give the same output unless it is specifically programed to try to avoid it (and then we have PRNGs).

Some things that make chess engines non-deterministic: 1) Most chess engines use an opening book instead of calculating moves early in the game. These books are often programmed probabilistically, so it may have 4 reasonable responses to a given move and pick one randomly. 2) Many engines are programmed to "ponder", that is do optimistic calculations during the opponents turn. This means that the time taken by you to…

You forgot two more things, they might not happen often enough because of the sheer number of possible positions in the early gameplay but it does make a difference in the game if you play the same position every time.

- Opening Book learning. - Position Learning.

Most decent chess engines have these features.

Re: A step-by-step guide to building a simple chess AI

#17

Post by captn3m0 »

I am working on building a generic card game environment/runner which could plugin into different AI systems, and this is very helpful.

I've been looking for a reinforcement-learning version of this. How do you build an AI that plays Tic-Tac-Toe against itself to figure out the best strategy?

Re: A step-by-step guide to building a simple chess AI

#18

Post by kqr2 »

For those interested in understanding how chess programs work, also see Toledo Nanochess: The commented source code

http://www.lulu.com/shop/oscar-toledo-gutierrez/toledo-nanoc...

  Toledo Nanochess is the world's current smallest chess 
  program written in C language. Now for the first time is 
  published the complete documented source code. Also 
  including the documented source code of the JS1K 2010 
  Chess entry (2nd place winner)
Post reply on HN