News for hackers. Stuff that matters.
Re:Full ZX-81 Chess in 1K (1983) by sillysaurus3 on Saturday January 31, 2015 @09:40PM (#8978967)
Here's an interesting question for you:

Your goal is to implement full Chess in the smallest number of bytes. However, you're allowed to design your own instruction set to accomplish this. The instruction set must be Turing complete.

Given this, what's the smallest Chess program possible? Is there an ultimate limit, information-theory style?

I know there's no easy answer or perhaps no answer at all. Maybe it's an NP-complete problem whose best answer can only be approximated or brute forced. But it's still really interesting to think like, if you toss aside all of the normal constraints, what's the smallest chess program that anyone can make?

Bonus points if you dive into experimental instruction sets like imprecise computing or quantum computing, though I doubt those things could help implement a precise rigid ruleset like Chess.

Re:Full ZX-81 Chess in 1K (1983) by tbirdz on Saturday January 31, 2015 @10:00PM (#8979004)
I'll define an instruction set with a single instruction CHESS that when executed will play a game of chess with the user.

I'm sorry, I know this is a bit of a "snarky" type reply, but I don't really understand what you are driving at with your question. Without more constraints on the question, there's not really any point in searching for the minimum solution.

Re:Full ZX-81 Chess in 1K (1983) by Shoop on Saturday January 31, 2015 @10:08PM (#8979022)
> The instruction set must be Turing complete.
Re:Full ZX-81 Chess in 1K (1983) by tbirdz on Saturday January 31, 2015 @10:15PM (#8979035)
I don't quite see how this requirement changes anything. You could have a full Turing complete instruction set, and still have a CHESS instruction that plays a game of chess with the user. The "Chess program" would still be 1 instruction.
Re:Full ZX-81 Chess in 1K (1983) by sillysaurus3 on Saturday January 31, 2015 @10:33PM (#8979065)
Well, an instruction set is said to be Turing complete if it can be used to simulate any Turing machine. A single instruction can't, so if you design an instruction set to implement Chess and then don't use it, that's not really the point of the question.

Any ideas about how to better specify the rules of the competition to exclude degenerate answers like the one you provided? The goal is to answer the interesting question. You'd never find such a high-level instruction in a real instruction set, because it wouldn't be useful except to play Chess.

I'd add a rule like "The goal of your instruction set is to be useful while still implementing Chess," but then that would exclude answers which give interesting instruction sets that aren't necessarily useful except in implementing Chess in the fewest possible bytes.

Thanks for pointing out the flaws in my ruleset. I've been toying around with creating a blogpost about this, so having a bulletproof ruleset or at least one that isn't so easily sidestepped would be great.

Re:Full ZX-81 Chess in 1K (1983) by dragonwriter on Saturday January 31, 2015 @10:56PM (#8979113)
> Well, an instruction set is said to be Turing complete if it can be used to simulate any Turing machine. A single instruction can't

Incorrect. A single instruction can be Turing complete.

http://en.wikipedia.org/wiki/One_instruction_set_computer

Though the relevant question is whether universal computation can be built on the back of an instruction which plays chess rather than one of the more typical bases for a OISC.

Re:Full ZX-81 Chess in 1K (1983) by taejo on Sunday February 01, 2015 @03:43AM (#8979498)
> Though the relevant question is whether universal computation can be built on the back of an instruction which plays chess rather than one of the more typical bases for a OISC.

Well you can have two instructions: SUBLEQ and CHESS. Then it's Turing-complete, and there's a one-bit program that plays chess.

Re:Full ZX-81 Chess in 1K (1983) by sillysaurus3 on Saturday January 31, 2015 @11:47PM (#8979200)
This is awesome. Thank you.

What are some typical bases for OSIC?

Re:Full ZX-81 Chess in 1K (1983) by RodgerTheGreat on Sunday February 01, 2015 @12:07AM (#8979232)
Specify the problem in terms of logic gates. You can spend gates building special-purpose ALUs, you can sink everything into RAM/ROM and have a complex program written in an extremely simple RISC instruction set or strike any balance between. Going with gates instead of transistors keeps things tidy and not tied to any particular strategy for physically building the system.
Re:Full ZX-81 Chess in 1K (1983) by gambler on Sunday February 01, 2015 @04:14AM (#8979529)
How well does it need to play? You could just do random moves withinh the allowed rules.
Re:Full ZX-81 Chess in 1K (1983) by sillysaurus3 on Sunday February 01, 2015 @04:34PM (#8981755)
Sure, that's fine. It's not about making an AI but rather implementing chess.