Programming language features for computer chess

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Dann Corbit
Posts: 10207
Joined: Wed Mar 08, 2006 7:57 pm
Location: Redmond, WA USA
Contact:

Re: Programming language features for computer chess

Post by Dann Corbit » Fri Jan 28, 2011 1:33 am

Someone has written an alpha-beta search for GPUs and applied it to various games:
http://www.nvidia.com/content/GTC-2010/ ... TC2010.pdf

FlavusSnow
Posts: 89
Joined: Thu Apr 01, 2010 3:28 am
Location: Omaha, NE

Re: Programming language features for computer chess

Post by FlavusSnow » Sat Jan 29, 2011 4:07 pm

As someone who isn't a great programmer, I was very appreciative when CILK was released. It made it very easy to take advantage of more cores. I don't know how it compares to other methods of multithreading in terms of speed, but for me, any speedup is better than none.

Of course if you're not a fan of C, you wouldn't be a fan of CILK. On a side note, Intel has developed CILK++ which is analogous to C++.


I hastily researched Modula-3 prior to posting this. Out of curiousity, have you tried Obliq? What are your thoughts on Obliq, if any?

smatovic
Posts: 953
Joined: Wed Mar 10, 2010 9:18 pm
Location: Hamburg, Germany
Full name: Srdja Matovic
Contact:

Re: Programming language features for computer chess

Post by smatovic » Sat Jan 29, 2011 5:26 pm

I tried to port the MicroMax 0x88 movegeneration to opencl. on different GPUs. It performed very slow compared to the available computing power. I guess the SIMD-like GPU-architecture and the loop-iterations from 0x88 move generation exclude each other.

A Magic BitBoard approach couldnt be completed because the HashTable didnt fit into fast local/private memory.

I still try to figure out how to couple gpu-threads to work on one board to couple private/local memory....

Rein Halbersma
Posts: 685
Joined: Tue May 22, 2007 9:13 am

Re: Programming language features for computer chess

Post by Rein Halbersma » Tue Feb 01, 2011 8:53 am

Xann wrote: I gave some thought about what features would be useful for computer chess.

Two things for me.

1) iterators (with "yield" statement)

Extremely useful for both mailbox (maybe outdated now) and bitboard.
Incremental move gen etc ...

Sure, we can do it with classes, but classes are verbose.
Also when I tried with GCC Linux, it became slower and slower.
Classes with a single field were not optimised properly.
Since then, I was told classes were fine.
Maybe I tried in a wrong way, or it didn't work with GCC then (2003 version I think).

I think if I had iterators in 2005, Fruit would be 4x smaller, and maybe more.
Could you elaborate on this a bit more, please? Did you mean C# style iterators? There are also various macro hacks on the web to do something similar in C++ (but not type-safe, re-entrant etc.). And on which level did you want to apply such iterators? Looping over bitboards? Move generation? Tree traversal?

Rein

Xann
Posts: 125
Joined: Sat Jan 22, 2011 6:14 pm
Location: Lille, France

Re: Programming language features for computer chess

Post by Xann » Tue Feb 01, 2011 2:37 pm

Rein Halbersma wrote:Could you elaborate on this a bit more, please? Did you mean C# style iterators? There are also various macro hacks on the web to do something similar in C++ (but not type-safe, re-entrant etc.). And on which level did you want to apply such iterators? Looping over bitboards? Move generation? Tree traversal?

Rein
Hi,

I don't know C#.
Iterators were invented in CLU, and made popular by languages such as Python.
Their main trait is the "yield" statement.

Where I want to apply them: anything that scans pieces, squares, moves, you name it; that's a lot of code in an engine.
Where I don't: trees.

Fabien.

IanO
Posts: 478
Joined: Wed Mar 08, 2006 8:45 pm
Location: Portland, OR
Contact:

Re: Programming language features for computer chess

Post by IanO » Tue Feb 01, 2011 5:45 pm

Xann wrote:
Rein Halbersma wrote:Could you elaborate on this a bit more, please? Did you mean C# style iterators? There are also various macro hacks on the web to do something similar in C++ (but not type-safe, re-entrant etc.). And on which level did you want to apply such iterators? Looping over bitboards? Move generation? Tree traversal?

Rein
Hi,

I don't know C#.
Iterators were invented in CLU, and made popular by languages such as Python.
Their main trait is the "yield" statement.

Where I want to apply them: anything that scans pieces, squares, moves, you name it; that's a lot of code in an engine.
Where I don't: trees.

Fabien.
I've heard these called "generators" rather than iterators. They are a form of coroutine.

Ken Thompson would agree with you. He added such a mechanism in his new language, Go.

I doubt such a mechanism would gain acceptance in C unless it were extremely light-weight. Python's generators require saving the current generator state on the garbage collected heap.

Perhaps you'd like the language to just have some more convenient collection handling? Some sort of "foreach" looping mechanism?

P.S. There exist chess-specific programming languages. Steven J. Edwards created a domain-specific chess-Lisp to create his program Symbolic.

User avatar
Zach Wegner
Posts: 1922
Joined: Wed Mar 08, 2006 11:51 pm
Location: Earth
Contact:

Re: Programming language features for computer chess

Post by Zach Wegner » Tue Feb 01, 2011 6:18 pm

Xann wrote:
Rein Halbersma wrote:Could you elaborate on this a bit more, please? Did you mean C# style iterators? There are also various macro hacks on the web to do something similar in C++ (but not type-safe, re-entrant etc.). And on which level did you want to apply such iterators? Looping over bitboards? Move generation? Tree traversal?

Rein
Hi,

I don't know C#.
Iterators were invented in CLU, and made popular by languages such as Python.
Their main trait is the "yield" statement.

Where I want to apply them: anything that scans pieces, squares, moves, you name it; that's a lot of code in an engine.
Where I don't: trees.

Fabien.
Iterators would indeed be quite nice.

I would recommend making your own programming language. Start with a parser, and you can do all sorts of transformations, and spit out C code (if you don't have the stomach to make a real compiler :)). If you like Python I will recommend PLY--it makes doing this sort of stuff really easy.

Python-style iterators would probably be done best by inlining the for loop body directly into the generator. There are some tricky things to deal with though (break/continue as the most obvious example).

melajara
Posts: 213
Joined: Thu Dec 16, 2010 3:39 pm

Re: Programming language features for computer chess

Post by melajara » Wed Feb 02, 2011 3:15 am

Did you have a look at the D language (as the name implies, aimed at being a cleaner C successor)?

Iterators are implemented as part of the standard library, see
http://www.digitalmars.com/d/2.0/phobos ... rator.html

The feature set of the language is well summarized here
http://www.digitalmars.com/d/2.0/comparison.html

Last but not least, D is VERY efficient :D
Per ardua ad astra

Ron Murawski
Posts: 397
Joined: Sun Oct 29, 2006 3:38 am
Location: Schenectady, NY
Contact:

Re: Programming language features for computer chess

Post by Ron Murawski » Wed Feb 02, 2011 6:38 am

Xann wrote:
Rein Halbersma wrote:Could you elaborate on this a bit more, please? Did you mean C# style iterators? There are also various macro hacks on the web to do something similar in C++ (but not type-safe, re-entrant etc.). And on which level did you want to apply such iterators? Looping over bitboards? Move generation? Tree traversal?

Rein
Hi,

I don't know C#.
Iterators were invented in CLU, and made popular by languages such as Python.
Their main trait is the "yield" statement.

Where I want to apply them: anything that scans pieces, squares, moves, you name it; that's a lot of code in an engine.
Where I don't: trees.

Fabien.
If you like Python syntax and want generators, then take a look at the Genie language. Genie 'compiles' into C code.
http://en.wikipedia.org/wiki/Genie_%28p ... anguage%29

Ron

Post Reply