Tuesday, September 11, 2012

Perfect Lossless Encryption, is it possible?

At one point of time you may have asked yourself the question: "Is there any perfect lossless encryption algorithm that can compress ALL kinds of data?"

The short answer is no. There isn't such an algorithm that takes inputs of n bits and produces an output of y bits where n > y for all possible inputs.

You may immediately think of zipping or raring files and nearly all the time you get something smaller, and most of the time something, much, smaller. Well I am going to prove you that it's not possible.


Mathematical proof

A lossless encryption algorithm is mathematically a function, but a special type of function, a bijection. This is because the inverse of it must also be a function, if not this means the algorithm we are looking at is not lossless*.





Intuitive Explanation

Example 1) Let's try to design an algorithm for 2 bit strings, there are only 4 different inputs, which are
00, 01, 10, 11
but there are only 3 outputs:
null string, 0, 1
Now, how can we compress them to 1 and 0 bit? It is obvious when we think like that but this is true for all n, it is just not this obvious.

Example 2) Assume for a second we have a program which can compress anything, it doesn't have to be a super method which cuts the file size to half, but a just-fine method which drops file size at least by 1 bit. You give a 100 byte file and you get a file with 800-1=799 bits. Now what happens when you try to compress the resulting file? I mean giving the algorithm a 799 bit file and get a 798 bit file, remember we don't care what type of file that is, it might be compressed before or not. Do you see where this is going? If we compress that 800 times, we get a file with 0 bits. Can that be real?

One Last Point:

One of the first things came to my mind before thinking this through is,
"That might be possible, it doesn't have to go all the way to 0, because it can look like the graph of the function 1/x+n. Each time you compress it will get a little bit lower, but the graph should be asymptotic to a some constant file size." 
Do you see where this chain breaks? The thing that makes the previous statement meaningless is that there are infinite number of real numbers between any two real numbers, so a function may decrease over time for infinite time but not reach zero. Size of bitstrings are natural numbers. Even though there are infinitely many natural numbers, the thing what matters is the question "Are there infinitely many natural numbers between any two fixed natural numbers?" The answer is obviously no, this prevents us from thinking them like decreasing functions.



I am interested in hearing from you, what do you think is worth investigating and creating a simple brainstorming report?

*:At best case lossless, which is bad enough.

Saturday, September 8, 2012

Chess Bot for PlayChess

     As you know I have always been interested in automating things, so creating bots is a passion for me.I have created many bots for games, as well as for websites where you need to automate things. Any program that automates some process is defined as a bot for me.

     Notice that I didn't use the more common term Chess AI because I didn't create it. AI is just about making a decision where bots include scraping data, processing data and outputing data. Chess AI needs a well formatted board state, but if you are writing a chess bot for example for PlayChess.com you don't have the well defined structure in your hands. You need to somehow scrape the data out of it, either by memory reading which can get really tedious if developers added a security measure for it, or by image processing which is easier for most of the cases.

     If it wasn't a native application, and it was but a javascript web application there is a third and easier way, scraping and manipulating DOM. So writing bots for web applications are very easy compared to native applications with some security measures.

     I usually use C#.NET to write bots and most of my projects since I don't care about portability of my pet-projects.

     Part 1) Scraping the data via image processing


     I noticed that everytime I open a new chess game on playchess the board starts at the same pixel coordinates, so that saved me from a great work, I also noticed that the tiles are 64*64 pixels. So using the CopyFromScreen  function I copied the screen to a bitmap and tiled that to 64 bitmaps which are each 64*64 pixels.There are 13 types of tiles possible, 6 white pieces, 6 black pieces, and 1 empty tile. At first I identified all of these pieces uniquely through image processing. But then I realized I don't have to do that. The only thing I need to do is to identify the color of the tile, either white, or black or empty. Because I was creating a fully-autonomous bot, it will never involve in a game in the middle. I mean from the start on it will see all the positions. So if I know all the moves in terms of source and destination coordinates, and if I know the starting position which is well defined and static, so it is enough to know the only piece colors not the piece types. Because latter one can be derived from the known things. So I dropped out the unique piece determining and I continued with color identifying which is easier and more error-prone. This may only cause a problem when opponent is promoting a pawn, you wouldn't know which type of piece it is but it is queen 99% of the time. After getting the board position we must format it so we can pass it to the Chess AI if the AI is not written by us. (mine wasn't)

    Part 2) Passing the board state to a Chess AI


     Picking a Chess Engine is important, if you have your own engine that is good , you can probably connect that easily to your bot, but if that is not the case, you must use 2 functions, first one should convert the board state to a format that engine can understand, and the second one should convert the engine moves to a format that yours output layer can understand.

     If the engine you found is open-source your job is easier since you will obviously have access to code. I found crafty chess engine which is both open source, robust and powerful, you can find it here http://www.craftychess.com/ . But I don't use crafty's open source property, since crafty already gave me enough options. For example the command "output long" makes crafty to output moves like Nb1c3 which is easier to parse, normally chess moves are like Nc3, so you have to calculate the starting position which is a hard work for example when two pieces can move to the same location it gets even harder.
Another command "xboard" mutes crafty's unwanted data, it only outputs it's moves which is also better for us because we don't care about how many positions it analyzed and those kinds of information.

     I got crafty's exe and in my loop everytime a new game starts I start a process too, and redirect it's standart input and output to my C# program.

    Part 3) Passing the result of Chess AI to PlayChess client


     Now the last part is to make the move on the native application. You can try many things, you may intercept TCP packets and send your own tcp packets, or an easier way is to use Windows' SendMessage and SendInput API to make the move. I used this library http://inputsimulator.codeplex.com/ for it's simplicity for this project. You should turn the Chess AI's move output to source and destination coordinates, after that you can write a function like this and make your moves !!

public void makeMove(int r1, int c1, int r2, int c2)
        {
            InputSimulator inputsimul = new InputSimulator();
            inputsimul .Mouse.MoveMouseTo((c1*64+32+76) * (65535.0 / 1366.0), (r1*64+32+161) * (65535 / 768.0));
            System.Threading.Thread.Sleep(200);
             inputsimul  .Mouse.LeftButtonDown();
            System.Threading.Thread.Sleep(200);
             inputsimul  .Mouse.MoveMouseTo((c2 * 64 + 32 + 76) * (65535.0 / 1366.0), (r2 * 64 + 32 + 161) * (65535 / 768.0));
            System.Threading.Thread.Sleep(200);
             inputsimul  .Mouse.LeftButtonUp();
        }

This makes a drap-drop move from r1,c1 to r2,c2 where these variables represent tile coordinates, not pixel coordinates. +32 is used for clicking in the middle, 76 is offset of my board and the inputsimulator library takes input from 0 to 65535 where 65535 represents the maximum width or height of your screen.


Here is a video of my bot working,


http://www.youtube.com/watch?v=sjuB0__N8bE