MS Paint is underrated MS Paint was always a great time waster, but it was shunned by most graphic designers. Perhaps people lost interest because of the jarring color palette, or because of limited undo levels. Regardless, it's still possible to generate beautiful images with just the standard brush and default color palette.

Challenge

Using only the default brush (a 4x4 square with no corners) and the default color palette (the 28 colors below), attempt to replicate a source image using a technique based on stochastic hill climbing.



Algorithm

Every answer must follow the same basic algorithm (stochastic hillclimb). Details can be tweaked within each step. A movement is considered to be a stroke of the brush (ie. clicking in paint).


Guess next movement(s). Make a guess (of coordinates and colors) for the next movement(s) however you'd like. However the guess must not reference the source image.
Apply the guess. Apply the brush to the painting to make the movement(s).
Measure the benefit of movement(s). By referencing the source image, determine whether the movement(s) benefited the painting (ie. the painting more closely resembles the source image). If it is beneficial, keep the movement(s), otherwise discard the movement(s).
Repeat until convergence. Go to Step 1 and try the next guess until the algorithm has converged sufficiently. The painting should heavily resemble the source image at this point.


If your program does not match these four steps, it is probably not a stochastic hillclimb. I have tagged this as a popularity contest because the goal is to produce interesting painting algorithms based on the limited color palette and brush.

Contraints


The algorithm should be stochastic in some way.
The next guess should not be influenced by the source image. You are guessing each new movement, and then checking to see if it helped or not. For example, you are not allowed to determine where to place the brush based on the source image colors (that is similar to dithering the source image, which is not the goal).
You are allowed to influence the placement by tweaking the steps of the algorithm however you'd like. For example, you could start your guesses at the edges and move inwards, drag the brush to create lines for each guess, or decide to paint dark colors first. You are allowed to reference previous iteration images (but not the source image) in order to calculate the next desired movement. These can be restrictive as you'd like (ie. only make guesses within the top-left quadrant for the current iteration).
The measure of "difference" between the source image and the current iteration can be measured however you'd like, as long as it does not calculate other potential movements to determine whether this movement is considered to be the "best". It shouldn't know whether the current movement is the "best", only whether it fits within the tolerance of the acceptance criteria. For example, it can be as simple as abs(src.R - current.R) + abs(src.G - current.G) + abs(src.B - current.B) for each affected pixel, or any of the well-known color difference techniques.


Palette

You can download the palette as a 28x1 image or create it directly in the code.

Brush

The brush is a 4x4 square without corners. This is a scaled version of it:



(Your code must use the 4x4 version)

Example

Input:



Output:



You can see how the basic algorithm progresses in a short video I made (each frame is 500 iterations): The Starry Night. The initial stages are interesting to watch:
JavaScript

This solution uses the HTML5 canvas element to extract the image data, but without the need to use HTML, that means it can be run in your console. It access the color palette image as an array; I stored all the colors from the palette image in an array). It outputs to the console (after it finishes) and also stores the result in a variable.

The most updated version of the code is in the fiddle. The fiddle also uses a better algorithm to reduce noise in the pictures. The improvement in the algorithm is mostly fixing a function (max to min) which caused the inverse color to be chosen.

Code in the shape of the MS Paint Icon! (formatted code in fiddle or Stack Snippet)

eval(`                                                   function                  
                                                        Paint(t){fun              
                                                         ction n(t){va            
                                                         r n=t.toString(          
                                                         16);return 1==n.         
                                                         length?"0"+n:n}fu        
                                                         nction e(t){return       
                                                         "#"+n(t[0])+n(t[1]       
                                                          )+n(t[2])}var a=ne      
                                                          w Image,i=document.     
                                                          createElement("canv     
                                                          as"),h=null,o=docum     
                                                          ent.createElement(      
                                    "canvas"),r=          o.getContext("2d        
                               ")     ,l=[],u=this,c      =[[0,0,0],[255          
                            ,2       55,255],[ 192,192,   192],[128,12            
                          8     ,128],[126,3,8],[252,13,27] ,[255,25              
                       3,    56],[128,127,23],[15,127,18],[ 41,253                
                      ,    46],[45,255,254],[17,128,127],[2 ,12,1                 
                    2    6],[ 11,36,2 51],[252,40,252],[12 7,15,1                 
                  2    6],[  128,127 ,68],[255,253,136],[4 2,253,                 
                 1   33],   [4,64,64],[23 ,131,251],[133,255,254],                
               [    129   ,132,252],[6,6 6,126],[127,37,2 51],[127,               
              6   4,1    3],[253,128,73],[252,22,129]];a.crossOrigin              
             =   "",   a.src=t,this.done=this.done||function(){},a.o              
            n   load=function(){function t(t){var n=0,e=0,a=0;return              
           t  .forEach(function(t){n+=t[0],e+=t[1],a+=t[2]}),[n/t.leng            
          t  h,e /t.length,a/t.length]}function n(t){for(var n=[],e=0;e           
         &lt;  t.l  ength;e+=1)n.push(t[e]);return n}function g(t,n){retur           
        n  (Ma  th.abs(t[0]-n[0])/255+Math.abs(t[1]-n[1])/255+Math.abs(t          
       [  2]- n[2])/255)/3}function f(t,n){for(var e=Math.floor(Math.ran          
          do m()*n.length),a=n[e],i=(g(t,a),1-.8),h=56,o=[];o.length&lt;=h&amp;          
         &amp;g (t,a)&gt;i;)if(o.push(a),a=n[Math.floor(Math.random()*n.length)]         
     ,  o.length==h){var r=o.map(function(n){return g(t,n)});a=o[r.indexO         
       f(Math.max.apply(Math,r))],o.push(a)}return a}function s(t,n){for(         
    v  ar e=[];t.length&gt;0;)e.push(t.splice(0,n).slice(0,-1));return e}i.w         
   i  dth=a.width,i.height=2*a.height,h=i.getContext("2d"),h.drawImage(a,0        
   ,0,a.width,a.height);for(var d=(function(t){reduce=t.map(function(t){re        
  turn(t[ 0]+t[1]+t[2])/3})}(c),0),m=0,v=i.width*i.height/4,p=0;v&gt;p;p+=1)d        
  &gt;2*Mat h.ceil(a.width/2)&amp;&amp;(d=0,m+=1),l.push(f(t(s(n(h.getImageData(2*d,2        
  *m,4,4).data),4)),c)),d+=1;o.width=i.width,o.height=i.height;for(var d=0        
 ,m=0,v=i.width*i.height/4,p=0;v&gt;p;p+=1)d&gt;2*Math.ceil(a.width/2)&amp;&amp;(d=0,m+=        
 1),console.log("Filling point ("+d+", "+m+") : "+e(l[p])),r.fillStyle=e(l        
 [p]),r.fillRect(2*d+1,2*m,2,1)  ,r.fillRect(2*d,2*m+1,4,2),r.fillRect(2*d        
+1,2*m+3,2,1),d+=1;u.result=o      .toDataURL("image/png"),u.resultCanvas         
=o,u.imageCanvas=i,u.image=a       ,u.done(),console.log(u.result)},a.one         
rror=function(t){console.log       ("The image failed to load. "+t)}}/*..         
............................       ......................................         
. ..........................       .....................................          
............................      ......................................          
.............................    .......................................          
.......................................................................           
.......................................................................           
..................  ..................................................            
................     .................................................            
..............       ................................................             
.............       ................................................              
...........        .................................................              
 .........         ................................................               
 .......          ................................................                
  ....           ................................................                 
                ................................................                  
                ...............................................                   
               ...............................................                    
              ..............................................                      
              .............................................                       
             ............................................                         
             ..........................................                           
              .......................................                             
              .....................................                               
               .................................                                  
                .............................                                     
                  ......................                                          
                                   .....                                          
                                  .....                                           
                                  .....                                           
                                  ....                                            
                                   */`
.replace(/\n/g,''))                                             


Usage:

Paint('DATA URI');


Fiddle.

The fiddle uses crossorigin.me so you don't need to worry about cross-origin-resource-sharing.

I've also updated the fiddle so you can adjust some values to produce the best-looking painting. Some pictures' colors might be off, to avoid this, adjust the accept_rate to adjust the algorithm. A lower number means better gradients, a higher number will result in sharper colors.



Here's the fiddle as a Stack-Snippet (NOT updated, in case the fiddle doesn't work):



/* Options */

var accept_rate = 82,  // 0 (low) - 100 (high)
    attempts    = 16, // Attemps before giving up
    edge_multi  = 2;   // Contrast, 2-4

function Paint(image_url) {
    var image = new Image(), canvas = document.createElement('canvas'), context = null, result = document.createElement('canvas'), resultContext = result.getContext('2d'), final_colors = [], self = this, color_choices = [
        [0,0,0],
        [255,255,255],
        [192,192,192],
        [128,128,128],
        [126,3,8],
        [252,13,27],
        [255,253,56],
        [128,127,23],
        [15,127,18],
        [41,253,46],
        [45,255,254],
        [17,128,127],
        [2,12,126],
        [11,36,251],
        [252,40,252],
        [127,15,126],
        [128,127,68],
        [255,253,136],
        [42,253,133],
        [4,64,64],
        [23,131,251],
        [133,255,254],
        [129,132,252],
        [6,66,126],
        [127,37,251],
        [127,64,13],
        [253,128,73],
        [252,22,129]
      ];
  image.crossOrigin = "";
  image.src = image_url;
  
  this.done = this.done || function () {};

  function hex(c) {
    var res = c.toString(16);
    return res.length == 1 ? "0" + res : res;
  }
  
  function colorHex(r) {
    return '#' + hex(r[0]) + hex(r[1]) + hex(r[2]);
  }
  
  image.onload = function () {
    canvas.width = image.width; canvas.height = image.height * 2;
    context = canvas.getContext('2d');
    context.drawImage(image, 0, 0, image.width, image.height);
    
    function averageColors(colors_ar) {
      var av_r = 0,
          av_g = 0,
          av_b = 0;
      
      colors_ar.forEach(function (color) {
        av_r += color[0];
        av_g += color[1];
        av_b += color[2];
      });
      
      return [av_r / colors_ar.length,
              av_g / colors_ar.length,
              av_b / colors_ar.length];
    }
    
    function arrayFrom(ar) {
      var newar = [];
      for (var i = 0; i &lt; ar.length; i += 1) {
        newar.push(ar[i]);
      }
      return newar;
    }
    
    function colorDif(c1,c2) {
      // Get's distance between two colors 0.0 - 1.0
      return (Math.abs(c1[0] - c2[0]) / 255 +
              Math.abs(c1[1] - c2[1]) / 255 +
              Math.abs(c1[2] - c2[2]) / 255) / 3;
    }
    
    var furthest = (function (cc) {
      // Determines furthest color
     
      // Reduces RGB into a "single value"
      reduce = cc.map(function(color) {
        return ( color[0] + color [1] + color [2] ) / 3;
      });
      
    }(color_choices));
      
    function intDif(i1,i2,t) {
        return Math.abs(i1 - i2) / t
    }
      
    function arrayIs(ar, int,d) {
        return intDif(ar[0],int,255) &lt;= d &amp;&amp;
               intDif(ar[1],int,255) &lt;= d &amp;&amp;
               intDif(ar[2],int,255) &lt;= d
    }
      
    function colorLoop(c1,c2) {
        var edgeCap =  edge_multi * ((accept_rate / 100) / 50), values = c2.map(function (i) {
            return colorDif(c1,i);
        });
        
        
        
      return arrayIs(c1,255,edgeCap)?[255,255,255]:
             arrayIs(c1,0,edgeCap)  ?[0,0,0]:
             c2[values.indexOf(Math.min.apply(Math, values))];
    }
       
    function colorFilter(c1, c2) {
      // Does the color stuff
      var rand  = Math.floor( Math.random() * c2.length ), // Random number
          color = c2[rand], // Random color
          randdif = colorDif(c1, color),
          threshhold = 1 - accept_rate / 100, // If the color passes a threshhold
          maxTries   = attempts, // To avoid infinite looping, 56 is the maximum tries to reach the threshold
          tries      = [];
        
        
      
      // Repeat until max iterations have been reached or color is close enough
        
      while ( tries.length &lt;= maxTries &amp;&amp; colorDif( c1, color ) &gt; threshhold ) {
        tries.push(color);
        color = c2[Math.floor(Math.random() * c2.length)]; // Tries again
        
        if (tries.length == maxTries) {
          // Used to hold color and location
          var refLayer = tries.map(function(guess) {
            return colorDif(c1, guess);
          });
          
          color = tries[refLayer.indexOf(Math.min.apply(Math, refLayer))];
            tries.push(color);
        }
        
      }
      
      var edgeCap =  edge_multi * ((accept_rate / 100) / 50), loop = colorLoop(c1, c2);
        
      return arrayIs(c1,255,edgeCap)?[255,255,255]:
             arrayIs(c1,0,edgeCap)  ?[0,0,0]:
             colorDif(c1,color)&lt;accept_rate?color:
             loop;
    }
    
    function chunk(ar, len) {
      var arrays = [];

      while (ar.length &gt; 0)
        arrays.push(ar.splice(0, len).slice(0, -1));
      
      return arrays;
    }
    
    var x = 0, y = 0, total = (canvas.width * canvas.height) / 4;
    
    for (var i = 0; i &lt; total; i += 1) {
      if (x &gt; (Math.ceil(image.width / 2) * 2)) {
        x = 0;
        y += 1;
      }
      
      final_colors.push( colorFilter( averageColors( chunk( arrayFrom(context.getImageData(x * 2, y * 2, 4, 4).data), 4 ) ), color_choices) );
      
      x += 1;
    }
    
    // Paint Image
    result.width = canvas.width;
    result.height = canvas.height;
    var x = 0, y = 0, total = (canvas.width * canvas.height) / 4;
    for (var i = 0; i &lt; total; i += 1) {
      if (x &gt; (Math.ceil(image.width / 2) * 2)) {
        x = 0;
        y += 1;
      }
      
        console.log("Filling point (" + x + ", " + y + ") : " + colorHex(final_colors[i]));
    
      resultContext.fillStyle = colorHex(final_colors[i]);
      resultContext.fillRect(x*2 + 1, y * 2, 2 , 1); // Top
      resultContext.fillRect(x * 2, y * 2 + 1, 4, 2); // Middle
      resultContext.fillRect(x * 2 + 1, y * 2 + 3, 2, 1); // Bottom
      
      x += 1;
    }
    
    self.result = result.toDataURL("image/png");
    self.resultCanvas = result;
    self.imageCanvas = canvas;
    self.image = image;
    self.done();
    
    console.log(self.result); 
    
  };
  
  image.onerror = function(error) {
    console.log("The image failed to load. " + error);
  }
  
}


// Demo

document.getElementById('go').onclick = function () {
    var url = document.getElementById('image').value;
    if (!url.indexOf('data:') == 0) {
        url = 'http://crossorigin.me/' + url;
    }
    var example = new Paint(url);
    
    example.done = function () {
        document.getElementById('result').src = example.result;
        document.getElementById('result').width = example.resultCanvas.width;
        document.getElementById('result').height = example.resultCanvas.height;
        window.paint = example;
    };
};
&lt;!--This might take a while--&gt;
Enter the image data URI or a URL, I've used crossorigin.me so it can  perform CORS requests to the image. If you're inputting a URL, be sure to include the http(s)
&lt;input id="image" placeholder="Image URI or URL"&gt;&lt;button id="go"&gt;Go&lt;/button&gt;
    &lt;hr/&gt;
    You can get the image URI from a website like &lt;a href="http://jpillora.com/base64-encoder/"&gt;this one&lt;/a&gt;
    &lt;hr/&gt;
    
    Result:
    &lt;img id="result"&gt;
        &lt;span id="error"&gt;&lt;/span&gt;&lt;hr/&gt;
        Check your console for any errors. After a second, you should see the colors that are being generated / printed getting outputted to the console.






To commemorate New Horizon's flyby of Pluto, I've inputted an image of Pluto:







For the following I've set it to make them resemble the original as close as possible:

I ran this with OS X Yosemite's default wallpaper. After leaving it run for a bit, the results are absolutely stunning. The original file was huge (26 MB) so I resized and compressed it:



The starry night (I've used a higher resolution image for better results)



A picture I found on google: