Arduino Uno Tournament

[ZirconiumX]

Would we simply communicate via serial, or would we have to use GPIO to communicate?

Of the 32KB limit, I'd imagine a lot of it would go to things like hardware clocks and possible pin control.

Matthew:out

[hgm]

I would be interested. I always wanted to make a program specifically targeting low memory footprint (as opposed to small source-code size, as micro-Max did). I would probably use assembler too.

[DavidEather]

executable in ROM = about 32k, working memory for variables, heap, stack etc 2k.

One reason to exclude machine language is it is an impediment to programmers coming from a different platform. Although if there is enough interest such a category could be added.

[DavidEather]

It has the same difficulties as programing chess on any platform. The compiler takes care of bytes, shorts, and longs. Optimization is a different thing as bytes have a clear advantage...

[DavidEather]

That 16 bit intermediate result is actually a requirement of ANSI C. Why everyone mindlessly adopted it for 8 bit operations is beyond me.

[sje]

It's hard to implement all of the FIDE Laws of Chess with only 2 KB RAM with position repetition detection eating a lot of memory. Much can be done if speed is not a concern. A reasonable search depth can be achieved if moves are stacked just one at a time per ply with the move generator state being saved with each move, but that makes it hard to get good move ordering.

And that's why I wrote Myopic for the Arduino Mega with 8 KB RAM and 128 KB flash. I used 32 KB of the flash for an opening book, and used some of the rest to drive an 8x8 color LED array of discrete diodes -- fun to watch when the array output was activated during perft() or search.

So I recommend a BeagleBone Black. My tests indicate that it has about the same chess throughput for bitboard programs as a 1 GHz 32 bit PowerPC G4. And you can still use some of the board's digital pins to drive an LED array.

http://www.adafruit.com/products/1487

[DavidEather]

I like the BBB but BBB is never going to happen. $55 for the hardware with a much less developed support base and a stepper learning curve, for what could be a one off experiment. Not many people are going to buy into that.

Everyone who wants to say it can't be done seems to ignore the fact that it has been done, with less hardware, less ram, less processing power and less developed tools. We just want to do it better. I should probably make that my signature

[sje]

The Uno costs about US$30, so there's only a US$25 difference between it and the BB Black. But for the Uno, one also needs a special USB cable for communication while the BB Black can use any spare 10/100 Mbps Ethernet RJ-45 cable. Both boards will also need a power supply and maybe a case, so the cost percentage difference turns out to be not that much.

A cool thing with the BB Black is that it has two USB ports and either can be used for a USB WiFi dongle. Some can go further and use as USB keyboard/mouse, an extra small HDMI monitor, and run the whole thing from batteries. Try that with a Uno.

http://www.adafruit.com/products/1033 (7 inch 720p HDMI monitor; also works with a Pi)

In my opinion, there's a sufficiently large user community for the BB Black. Perhaps not as large as that for the Arduino, but that doesn't count the huge Debian Linux support available on the net.

And you can still program the BB Black with assembly language if you really want.

[bob]

And you are so ignorant.

Arduino's program with the AVR-gcc C++ compiler, just like the Atmel AVR studio does - i.e. it is a reasonable complier for a microcontroller and the whole point is to experience working with limited processing resources.

Because of these limits, any unthinking code monkey who simply ports an engine across is very unlikely to get anywhere near the top results.

As to if it is possible, yes, it was first done years ago (2009) with the C++ chess program minimax being ported to an ATMega88. So despite what you say, a C++ engine can be ported, and since the new hardware has four times the ROM and twice the RAM as an ATMeaga88, and in addition for this competition it will not require resources for a human interface, a lot more is possible. I'm not saying "easy", Stockfish is never going to make it across, but your assertion is clearly wrong. A Uno is not nearly as limited as you seem to imagine. AVR-gcc code on a microcontroller is very efficient compared to x86 on any form of PC. For a start only variables need to go into RAM, and program code is written into ROM.

ATMega is modern hardware and one of the highest selling microcontroller ever. So I don't see you having a point at all.

You are also wrong about the hardware / software divide. If maximum performance was the only goal then everyone would be using dedicated hardware and programing their own FPGA and having ASIC's fabricated with non-disclosure agreements.

The reason it doesn't happen is not because of lack of performance, but because most tournaments no longer accept custom hardware for the good reason that the cost and skill sets required would stop many people from starting and discourage anyone from entering software.

Remember that IBM's hardware was thousands of times faster than it's software competitors. It is still the same today, and you can build hardware to perform any algorithm you like. Unrestricted hardware vs software is not even a competition but more like Leeds United kicking the crap out of the local under 5's.

And why do people allow programs to be weakened if max power is the only goal?

Is there no joy in having something that you can say "I built this myself" (followed by a perhaps unvoiced "and it can beat 97% of people who play chess)"?

No point in learning something new or picking up new skills? For every PC sold, thousands of microcontrollers are produced and this is a nice way to leverage your existing programing skills to enter into the Internet of Things.

Arduino is low cost: about $20 but you can make your own for $4 if you want. Arduino avoids the cost associated with custom hardware. It is very well supported with a very active and knowledgeable forum, books, blogs and more, so no one should get stuck alone with a problem that can't be resolved.

And because the hardware is identical who wins will be much more a function of who is the best programmer compared to who has the most money.

World shaking? No., but interesting if you have an open and curios mind (and spare time)!

The only negative I see is it completely eliminates current state-of-the-art algorithms such as bit boards. No way to do magic or rotated bit boards with such a small memory model. Which means this turns into a "niche-based project" rather than something that might evolve into a full-blown contemporary-competitive chess program. Yes, there are people that program LEGO blocks, but that is a LONG way from "the big time".

[bob]

Hi,

Just checking if there would be any interest in this:
A chess engine tournament with all competitors running on the Arduino Uno platform.

This would give everyone the same hardware and a new experience in programing in a limited resource environment. (An Arduino Uno has 32k of ROM, 2K of RAM and 1K of eeprom on a RISC chip running at 16 MHz. It programs in a reasonably standard 'C' language - actually C++). This is (roughly) about the same as good standalone hardware in the 90's. How much has programing technique improved?, evaluation functions? etc

Any interest or thoughts (a tournament won't be up and running before mid 2015)

You are so naive. Just try to compile any modern C++ engine on this, and you will understand...

Only C engines have a chance to be compilable with the kind of paleolithic compiler that will work for this fossil. But even basic C engines would have to be compiled with ancient compilers, or else even a "hello world" program would not run on 2K of RAM. Still I don't think you will be able to compile anything beyond FaryMax and the likes. Even Olithink I'm not sure... So it's completely pointless, because these programs do not represent what I would call "state-of-the-art 2014" in chess programming.

I think it would be far more relevant to compile old engines with a modern C compiler and run them on a modern hardware. Then compare with modern programs.

But this is pointless anyway. The progression since 1990 is >99% in software and <1% in hardware. Anyone who understands something about modern chess engines knows that already.

I don't buy your last statement at all. 1990 was 1K nodes per second or so. Run ANY program today at 1K nodes per second and see just how weak it really is. Probably in the 1000-1200 Elo range if you are lucky. Hardware is at least 50% of the improvement from 1990 to today. In fact, there is not a competitive engine today that will even run on 1990 hardware, due to memory constraints imposed by bit board code and such.

Here's a simple sample, kopec #22. At 1K nodes per second with current Crafty:

Code: Select all

          6    39.41/1:00       ++   1. ... h5? (>+0.71)                  
          6    41.17/1:00     0.55   1. ... h5 2. Rac1 Ne8 3. Nxb6 Bd8 4. Nh2
          6    41.90/1&#58;00       --   1. ... Bxe4! (<+0.54&#41;                  
          6    43.88/1&#58;00     0.43   1. ... Bxe4 2. Bxe4 Nxe4 3. Qxe4 Qxc4 4.
                                     Bd4 Qxb5
          6->  52.17/1&#58;00     0.43   1. ... Bxe4 2. Bxe4 Nxe4 3. Qxe4 Qxc4 4.
                                     Bd4 Qxb5
        time=1&#58;00&#40;100%)  n=106038&#40;106.1K&#41;  fh1=54%  50move=0  nps=1.8K
        ext=33  pruned=16.4K  qchks=420  predicted=0
        LMReductions&#58; 0/15.0K  1/2.4K  2/766  3/34  
        null searches &#40;R&#41;&#58; 3/1.3K  
        splits=0  aborts=0  data=0%  probes=0  hits=0

compared to normal crafty:

Code: Select all

         27    59.40         -0.52   1. ... Bxe4 2. Bxe4 Qxc4 3. Qxc4 Rxc4 4.
                                     Nxb6 Nxb6 5. Bd3 Rc7 6. Rac1 Rfc8 7. Rxc7
                                     Rxc7 8. Nd4 a4 9. Nc6 Nfd5 10. Be2 Bf6
                                     11. Bxf6 gxf6 12. Bf3 Kg7 13. Rd4 Nc3 14.
                                     Rxd6 Nxb5
         27->   1:07         -0.52   1. ... Bxe4 2. Bxe4 Qxc4 3. Qxc4 Rxc4 4.
                                     Nxb6 Nxb6 5. Bd3 Rc7 6. Rac1 Rfc8 7. Rxc7
                                     Rxc7 8. Nd4 a4 9. Nc6 Nfd5 10. Be2 Bf6
                                     11. Bxf6 gxf6 12. Bf3 Kg7 13. Rd4 Nc3 14.
                                     Rxd6 Nxb5
?
         28     1:42         -0.53   1. ... Bxe4 2. Bxe4 Qxc4 3. Qxc4 Rxc4 4.
                                     Nxb6 Nxb6 5. Bd3 Rc7 6. Rac1 Rfc8 7. Rxc7
                                     Rxc7 8. Nd4 a4 9. Nc6 Nfd5 10. Be2 Bf6
                                     11. Bxf6 gxf6 12. Bf3 Kg7 13. Bxd5 Nxd5
                                     14. Rd4 Rb7 15. Rg4+ Kf8
         28->   1:51         -0.53   1. ... Bxe4 2. Bxe4 Qxc4 3. Qxc4 Rxc4 4.
                                     Nxb6 Nxb6 5. Bd3 Rc7 6. Rac1 Rfc8 7. Rxc7
                                     Rxc7 8. Nd4 a4 9. Nc6 Nfd5 10. Be2 Bf6
                                     11. Bxf6 gxf6 12. Bf3 Kg7 13. Bxd5 Nxd5
                                     14. Rd4 Rb7 15. Rg4+ Kf8
        time=1:51(100%)  n=569340085(569.4M)  fh1=93%  50move=0  nps=5.2M
        ext=3.1M  pruned=257.8M  qchks=6.2M  predicted=0
        LMReductions: 0/37.2M  1/17.2M  2/15.3M  3/6.6M  4/209.8K  5/668  
        null searches (R): 3/29.9M  4/123.3K  5/61  
        splits=0  aborts=0  data=0%  probes=0  hits=0

and of course there is "real Crafty" running this at 45M nodes per second on an old 2x6 core box...

You REALLY underestimate the hardware advantage.