[anwtfces] Dreams

One thing we can do in our dreams, easily, is for something or someone to be simultaneously two or more things at once. We cannot observe this in the real world, constrained by Maxwell's Laws of Electromagnetism (not even quantum superposition can maintain two simultanous states under observation).

Why can we dream this?

Inspired by the angel with three faces in X Files.

[lslshtsf] Lossless H.264

Lossless H.264, e.g., x264 -q 0, is interesting as it invites a contest, compress a video as much as possible (I suspect even lossless encoding has degrees of freedom) while still being decodable by a standard H.264 decoder.

Does winning help? Simply discard the residuals to decode lossy.

[mjiahrzp] Chess live commentary by the players themselves

In order to make chess more accessible and interesting to spectate, the two players, probably placed in separate rooms with their own analysis boards, give live commentary about what they are thinking during the game as they play it, which is relayed to the audience.

Inspired by the Diary Room of Big Brother.

[vobzjaio] checksum

A simpler implementation of the POSIX cksum program, calculating CRC32 big-endian, not using a lookup table. This is slower, but may be useful pedagogically.

#include <cstdio>
typedef unsigned int U32;
const U32 polynomial=0x04C11DB7;
void update_crc(U32 *rem, unsigned char in){
*rem^=in<<24;
for(int j=0;j<8;++j){
U32 top_bit=*rem&0x80000000;
*rem<<=1;
if(top_bit)*rem^=polynomial;
}}

int main(){
U32 rem=0;
long long bytecount=0;
for(;;++bytecount){
unsigned char in;
int code=fread(&in,1,1,stdin);
if(1!=code)break;
update_crc(&rem,in);
}
//append the length, LSByte first
for(long long datalength=bytecount;datalength;datalength>>=8){
update_crc(&rem,datalength); //auto-truncate U32 to byte
}
rem=~rem; //seems a bit superfluous, given we are appending the length
printf("%u %lld\n",rem,bytecount);
}

[ruptwqra] How to cheat at chess

A spectre is haunting chess -- the spectre of cheating using computers, because computers these days can play chess much better than people. There is an escalating war between cheaters and anti-cheating countermeasures. It may be interesting to consider the problem of cheating in chess information theoretically.

In the presence of countermeasures, the communication channel between a cheating player and a computer (possibly a confederate consulting a computer) is very limited. Given bidirectional parameters on the communication channel, exactly what information should be sent across the channel to maximize the increase in performance of the player? This is an interesting general problem in its own right; let me present a possible solution for a specific case.

We consider one very minimal situation: the channel capacity or bandwidth from the computer to the player is a very small one bit per move, and the bandwidth from the player to the computer is zero (no communication possible in this direction, the player is under intense scrutiny, and any unusual behavior will be spotted). Actually, it's the covert bandwidth from the player to the computer that is zero; we assume the game is live and public, so the confederate, a member of the audience, can see the moves as they are made. Thus, the channel is such that the player cannot ask, "is this such-and-such a move a good move?" (because of the zero covert bandwidth in that direction), nor can a confederate signal "such-and-such a move is the best move in this position" (because such a message requires more than one bit per move). Nevertheless, one bit of information will be enough to provide a significant advantage to the cheater.

This "one bit of information" may be transmitted, for example, by the player seeing the confederate in the audience. It is helpful if the confederate situates him or herself where the player does not have turn his or her head and adjust his or her gaze. The confederate performs a subtle pre-agreed signal to transmit the bit: perhaps arms crossed left-over-right versus arms crossed right-over-left.

My proposal for the one bit that is transmitted is, "Did the opponent just blunder?" Computers excel at discovering blunders, and a human, armed with the information that an opponent has just just blundered, can engage in a radically different thought process than searching for a "normal" move in a normal situation. Instead, the player can conceptually search for the flaw in the opponent's previous move, and search for a specific attack to punish the mistake. I predict a strong player can become a lot stronger with just this one bit.

The naive confederate may consult a computer after every opponent move, checking if it was a blunder. A more sophisticated confederate, consulting a more powerful computer, can explore and memorize several ply deep at a time, so only having to consult the computer occasionally.

Technically, because blunders happen rarely, the actual entropy in the channel averages less than one bit per move, so perhaps a even cleverer and more subtle encoding than suggested above is possible and even less likely to be caught.

However, the moral of the story is, catching cheaters in chess is going to be very, very difficult, needing to block extremely tiny amounts of information which is enough to gain a significant edge.

P.S.: A nice article: Cheating in Chess, by Frederic Friedel (This paper appeared as a contribution to the book "Advances in Computer Games 9", edited by Professors H. J. van den Herik, University Maastricht, and B. Monien, University of Paderborn. It was published by the Universiteit Maastricht in 2001. The paper on Cheating was written and submitted by Frederic Friedel in 2000.)

[zjqhwxhr] Consumer education via competitor advertising

Americans spend too much, everyone becoming horrendously in debt. One possible cause of the problem is the effectiveness of advertising, inciting us to buy, buy, buy. We rarely see information urging us not to buy a product, telling us what is bad about it. One normally needs to search long and hard to find such information, a review by a consumer report, for example.

However, in this capitalist world, it ought to be a lot easier to find criticism of a product you are considering buying: simply look to a competitor, for whom it is in their best interests to attack their competition with negative advertising. However, we rarely see this. Why?

One reason might be because of fear of lawsuits from the competitor. The legal cost of fighting such a lawsuit (even if the negative advertising is permitted by the freedom of speech) might outweigh the gains from the negative advertising. If so, in the best interest of consumers, we are in need of laws that make it more difficult for one producer to successfully sue another producer for disparaging their product.

A competitor is often in a uniquely qualified position to criticize their competition. For example, consider cell phones, and the problem of discovering a reliable, well-designed cell phone that won't break after a year. A third-party consumer report can only (easily) rely on consumer surveys of the product, statistically measuring their defectiveness rate. This may take months, if not years, and by that time, the cell phone in question is obsolete. However, a competitor cell phone manufacturer, by virtue of being a manufacturer, is (probably) an expert in cell phone manufacturing, and can disassemble the competitor's cell phone, examine its parts, materials, design, and other manufacturing details to determine the robustness of the phone.

Another reason we see little criticism between producers might be some sort of game-theoretic cooperation between competitors. If two competitors criticize each other's products, the consumer buys neither, and both producers lose. Ultimately, this will lessen the consumer's tendency to end up in debt, which might be a desirable outcome.