Saturday, January 25, 2020

P vs. NP - The Biggest Unsolved Problem in Computer Science

https://youtu.be/EHp4FPyajKQ

A crude chess program in order to look 10 half moves ahead would take the hypothetical 25 moves possible and do roughly 25 to the 10nth power calculations, which would take a very long time. However, the alpha-beta algorithm eliminates mathematically unnecessary calculations making this more like 5 or 6 to the tenth power, which is a huge difference.

What surprises me is that program Stockfish reduces this to more like 2 to the N power, which is considerably less. Exactly how it does this I'm not sure, although I have some idea.

I would contend that looking deeper in chess will always involve an exponential increase, by definition. To not be exponential means that we could look infinitely far ahead and completely solve chess. This is kind of the point of the video.

No comments:

Post a Comment