偽MCMC

/**
 * Copyright uwi ( http://wonderfl.net/user/uwi )
 * MIT License ( http://www.opensource.org/licenses/mit-license.php )
 * Downloaded from: http://wonderfl.net/c/iLZO
 */

// forked from uwi's GGAP-RBF + Q-Learning
// forked from uwi's Q-learning test
package {
    import flash.utils.*;
    import flash.display.*;
    import flash.text.*;
    import flash.geom.*;
    
    public class FlashTest extends Sprite {
        private var _bmd : BitmapData;
        
        public function FlashTest() {
            _bmd = new BitmapData(465, 465, false, 0x000000);
            addChild(new Bitmap(_bmd));
            
            var tf : TextField = new TextField();
            addChild(tf);
            tf.textColor = 0x0080ff;
            tf.height = 465;
            
//            bmd.perlinNoise(465, 465, 6, 0, true, false, 7, true);
            var i : int;
            for(i = 0;i < 100;i++){
                _bmd.fillRect( 
                    new Rectangle(Math.random() * 465, Math.random() * 465, Math.random() * 50, Math.random() * 50), 
                    0xffffff
                    );
            }
             
            var s : int = getTimer();
            
            // t:時刻, ac:行動
            var actions : Array = [{t : 0, ac : 0}];
            var next : Array = actions.concat();
            var pa : Number = pp(actions);
            var maxpa : Number = 0;
            var maxactions : Array = null;
            for(var r : int = 0;r < 100000;r++){
                if(r % 10000 == 0)tf.appendText("" + r + " : " + maxpa + "\n");
                if(Math.random() < 0.5){
                    // append
                    var t : int = Math.random() * 93;
                    var res : Object = bSearch(actions, t);
                    if(res.f)continue;
                    var acc : int = Math.random() * 2;
                    if(acc == actions[res.i].ac)acc = 2;
                    next.splice(res + 1, 0, {t : t, ac : acc});
                }else{
                    // remove
                    if(actions.length == 1)continue;
                    var ind : int = Math.random() * (actions.length - 1) + 1;
                    next.splice(ind, 1);
                }
                var pn : Number = pp(next);
                if(pn / pa > Math.random()){
                    pa = pn;
                    actions = next;
                    
                    if(pa > maxpa){
                        maxpa = pa;
                        maxactions = actions.concat();
                    }
                }
            }
            
            var g : int = getTimer();
            tf.appendText("" + (g - s) + " ms\n");
            tf.appendText("max : " + maxpa + "\n");
            
            var p : int = 0;
            var y : int = 230;
            var x : int = 0;
            var ac : int = 0;
            for(t = 0;t < 93;t++){
                if(p < maxactions.length && maxactions[p].t == t){
                    ac = maxactions[p].ac;
                    p++;
                }
                _bmd.setPixel(x, y, 0xff0000);
                x += 5;
                y += (ac - 1) * 5;
            }
        }
        
        private function pp(a : Array) : Number
        {
            var nhit : int = 0;
            var p : int = 0;
            var ac : int = 0;
            var y : int = 230;
            var x : int = 0;
            for(var t : int = 0;t < 93;t++){
                if(p < a.length && a[p].t == t){
                    ac = a[p].ac;
                    p++;
                }
                if(y < 0 || y >= 465)nhit += 10;
                if(_bmd.getPixel(x, y) > 0)nhit++;
                x += 5;
                y += (ac - 1) * 5;
            }
            return Math.exp(-nhit/5);
        }
        
        private static function bSearch(a : Array, t : int) : Object
        {
            var s : int = 0;
            var g : int = a.length;
            var m : int = (s + g) / 2;
            while(s < m){
                if(t == a[m].t)return {i : m, f : true};
                if(t < a[m].t){
                    g = m;
                }else{
                    s = m;
                }
                m = (s + g) / 2;
            }
            return {i : s, f : false};
        }
    }
}