This feed contains pages in the "software" category.
I participated in the google ai challenge. In the end I was placed 134 out of 708: My profile url.
Since I am working on a Monte Carlo tree search based Computer Go program, I figured I would try to use that as a basis for my bot.
In general it worked quiet ok. Especially in close range combat it is often able to play quite well:
At longer range and when looking for the longest path in endgame situations lack of depth in the tree search shows and quiet many mistakes are made.
I also experimented with using the distance between the players as a heuristic to bias the tree search into deeper branches, this was only mildly successful however. It seemed to be very hard to strike a balance between the heuristic not making a difference and turning my bot into a chaser.
In the final version my bots strategy is as follows:
Test if there is a path reaching the opponent using the a* pathfinding algorithm.
# ###############
## ... #
## .#1 #
## # .### #
# # . #
# # . #
# # ..... # #
# # .#### #
# ### # . #
# #### # . #
# # . # #
# # . # #
# # ###. # #
# # .... # #
# # .# #
# ..# ### #
# . # ### #
# ####. # #
# # .... # #
# .. # #
# . # #
# ###. # ##
# 2#. ##
# ... ##
###############
a* found shortest path between players
In case there is not, enter special endgame mode: the value of nodes in tree search is number of moves divided by flood fill size. I am unhappy with the endgame, this should make less mistakes.
In case opponents can still reach each other, use a biased tree search:
p and P are nodes searched for player 1
e and E are nodes searched for player 2 (enemy)
1 is the principal variation for player 1
1 is the principal variation for player 2
###############
#1PPPPPPP #
#111PPPPP #
#1111PPP e#
#PPP1PP eE#
#PPPPPPP eEE#
#PPPPPPPe eEEE#
#PPPPPPEEEeEEE#
#PPP p EEEEEEE#
#PPp EEEEEEE#
#Pp EEE2EEE#
# EEE2222#
# EEEEEE22#
# EEEEEEE22#
###############
nodes evaluated for each player in tree search at long range
At long range nodes closing in to the opponent are preferred.
Nodes are evaluated using flood fill if they divide opponents into separate areas.
Otherwise random playouts until either player crashes are used.
###############
## PPP e #
#### pPPPPWEEE#
# #PPPP111222#
# #PPP11W22E2#
# #PPP11W2EEE#
# #####1W2EEE#
# ##1122EEE#
# PPPW#EEE #
# PP ##E #
# # #
# #####
# ####
# ####
###############
nodes evaluated for each player in tree search at closer range
Tree search terminates as soon as 0.9 seconds are spent and return the best move found so far.
After reading a little about strategies other people have used, it may also have been a bad heuristic to just approach the other bot. "Voronoi territory" - the number of points that can be reached by each bot first - may have been a better choice. In general a good heuristic is key for Monte Carlo tree search to be able to deeply explore the tree without missing the wrong branches, so this could have helped a lot.
Further links:
The other day I was playing a little bit with laby, a small program to help in understanding basic programming concepts for kids, but maybe grown ups too.
It is available in Ubuntu in the laby package from karmic (9.10) on. I can highly recommend it, it is always fun to watch a graphical representation of a programmed creature do its job after the coding. I have created a general solution in ocaml that will successfully solve at least all the levels included in 0.5.0.
(* ocaml wall hugger for laby *)
let ant =
(* go straight ahead til we hit something *)
while (Robot.look () = `Void) do
Robot.forward ();
done;
(* main wall hugin' loop *)
while not (Robot.look () = `Exit) do
if (Robot.look () == `Void)
then (
Robot.forward ();
Robot.right ();
);
if (Robot.look () == `Rock)
then (
Robot.take ();
Robot.forward ();
Robot.left ();
Robot.left ();
Robot.drop ();
Robot.left ();
);
if (Robot.look () == `Wall) or (Robot.look () == `Web)
then
Robot.left ();
done;
Robot.door_open ();
;;
Go little robot ant!
Coyly I'll do it,
no code, count Five-Seven-Five
to make a haiku.
orphans
- bookmarks
- cross.png
- key.png
- tick.png
- readme.txt
- readme.txt
- doc.png
- email.png
- external.png
- feed.png
- im.png
- pdf.png
- visited.png
- xls.png
- readme.txt
- readme.txt
- grid.png
- cv.pdf
- debienna
- foaf.rdf
- laby.ml
- 2010-01-07---sudoku
- me
- lefant wa.jpg
- recentchanges
- robots.txt
- soup
- tags
- key-transition-2009-06-04.txt.asc
brokenlinks
- ?computer from WlanLefantNet
- ?network from WlanLefantNet
- ?password from supergenpass
- ?web from supergenpass
- ?BazBar from linkingrules
- ?C02860F0 from index
- ?DataDir from collectd and nagios
- ?FooBar from linkingrules
- ?FotoFortunes from 2007-07-22---phpfspot
- ?LoadPlugin from collectd and nagios
- ?OtherPage from linkingrules
- ?PageSpecs from pagespec
- ?RandomQuote from 2007-07-22---phpfspot
- ?WikiLinks from wikilink, templates
pagecount
93
linkmap and pagestats
sandbox
shortcuts
smileys
templates
just testing
soup lefant: new feed (0 posts)
% scalable monitoring with collectd and nagios % Fabian Linzberger e@lefant.net % 2008-12-04
some links beforehand
- debienna vnc presentation page
- this presentations url on lefant.net
- slides url
- collectd website
- nagios website
collectd
- rich performance monitoring (snmp has little data for a linux host)
- push model
- uses rrdtool for storage
- allows for mod_perl-style plugins
- can poll snmp stuff
- faster than munin
- little config needed, just works!
see yourself for more: collectd features
minimal collectd server config
#Hostname "localhost"
FQDNLookup true
<span class="createlink"><a href="http://lefant.net/cgi-bin/ikiwiki.cgi?page=loadplugin&from=debienna%2Fcollectd_and_nagios&do=create" rel="nofollow">?</a>LoadPlugin</span> network
<span class="createlink"><a href="http://lefant.net/cgi-bin/ikiwiki.cgi?page=loadplugin&from=debienna%2Fcollectd_and_nagios&do=create" rel="nofollow">?</a>LoadPlugin</span> rrdtool
<Plugin network>
Listen "217.19.46.22"
Listen "2002:d913:2e16::1"
</Plugin>
<Plugin rrdtool>
<span class="createlink"><a href="http://lefant.net/cgi-bin/ikiwiki.cgi?page=datadir&from=debienna%2Fcollectd_and_nagios&do=create" rel="nofollow">?</a>DataDir</span> "/var/lib/collectd/rrd"
</Plugin>
minimal collectd client config
#Hostname "localhost"
FQDNLookup true
<span class="createlink"><a href="http://lefant.net/cgi-bin/ikiwiki.cgi?page=loadplugin&from=debienna%2Fcollectd_and_nagios&do=create" rel="nofollow">?</a>LoadPlugin</span> network
<span class="createlink"><a href="http://lefant.net/cgi-bin/ikiwiki.cgi?page=loadplugin&from=debienna%2Fcollectd_and_nagios&do=create" rel="nofollow">?</a>LoadPlugin</span> cpu
<span class="createlink"><a href="http://lefant.net/cgi-bin/ikiwiki.cgi?page=loadplugin&from=debienna%2Fcollectd_and_nagios&do=create" rel="nofollow">?</a>LoadPlugin</span> df
<Plugin network>
Server "rerun.lefant.net"
</Plugin>
collectd webfrontend
enable using
sudo cp /usr/share/doc/collectd/examples/collection.cgi \
/usr/lib/cgi-bin/collection.cgi
and adapt webserver as needed.
demo url: http://rerun.lefant.net/cgi-bin/collection.cgi
just for fun:
- install collectd and send your data to rerun like in the example above!
nagios
- host and service availability monitoring
- testing for sysadmins!
webinterface statusmap
webinterface services
notification email
***** Nagios *****
Notification Type: PROBLEM
Service: LOAD
Host: rerun.lefant.net
Address: rerun.lefant.net
State: CRITICAL
Date/Time: Thu Dec 4 17:20:48 CET 2008
Additional Info:
(Service Check Timed Out)
cnagios
- homepage
- runs in screen and can do grep for host and service names
nagios objects
- hosts
- services
commands
contacts
- escalations
timeperiods
maps (using parent relationships)
host example
define host{
use generic-host-bundled
host_name rerun.lefant.net
address rerun.lefant.net
parents odyssey.lefant.net
}
service example
define service{
use generic-service-bundled
hosts www1,www2
service_description HTTP
check_command check_http
}
command example
very easy to extend, just put your script there or collectd-nagios (debian version buggy, see end)
define command{
command_name check_collectd
command_line /usr/local/bin/collectd-nagios \
-s /var/run/collectd-unixsock -H $HOSTNAME$ \
-n $ARG1$ -d $ARG2$ -w $ARG3$ -c $ARG4$
}
define command{
command_name check_collectd_percentage
command_line /usr/local/bin/collectd-nagios \
-s /var/run/collectd-unixsock -H $HOSTNAME$ \
-n $ARG1$ -g percentage -d $ARG2$ -d $ARG3$ \
-w $ARG4$ -c $ARG5$
}
templates
define default properties via templates:
define host{
name generic-host
notifications_enabled 1
process_perf_data 1
retain_status_information 1
retain_nonstatus_information 1
check_command check-host-alive
max_check_attempts 10
notification_interval 0
notification_period 24x7
notification_options d,u,r
contact_groups admins
register 0
}
inheritance
this can also be inherited and customized:
define host {
use generic-host
name generic-host-bundled
register 0
contact_groups lefant
}
works fine for things that can be configured for hosts.
problem: service centric
however hosts cannot configure services to be monitored...
define host{
use generic-host-bundled
host_name rerun.lefant.net
address rerun.lefant.net
parents odyssey.lefant.net
services HTTP,SMPT # doesn't work!!!
}
problem: service centric (2)
define service{
use generic-service-bundled
hosts www1,www2
service_description HTTP
check_command check_http
}
define service{
use generic-service-bundled
hosts www1
service_description SMTP
check_command check_smtp
}
imagine 10 or 20 services to be monitored for every box, you get to configure all of them, for every host.
pay your service hostgroup tax!
define service{
use generic-service-bundled
service_description HTTP
hostgroup_name HTTP
check_command check_http
}
define hostgroup{
hostgroup_name HTTP
}
host config with taxes paid
define host{
use generic-host-bundled
host_name rerun.lefant.net
address rerun.lefant.net
parents odyssey.lefant.net
hostgroups HTTP,COLLECTD
}
service hostgroup tax (continued)
then even grouping services works fine:
define service{
use generic-service-bundled
service_description SWAP-FREE
hostgroup_name SWAP-FREE
check_command check_collectd\
!swap/swap-free!value!209715200:!104857600:
}
define hostgroup{
hostgroup_name SWAP-FREE
hostgroup_members COLLECTD
}
(note the collectd nagios integration example here)
more nagios collectd service checks
define service{
use generic-service-bundled
service_description LOAD
hostgroup_name LOAD
check_command check_collectd\
!load/load!midterm!5!10
}
define hostgroup{
hostgroup_name LOAD
hostgroup_members COLLECTD
}
more nagios collectd service checks
(percentage needs patch, see end)
define service{
use generic-service-bundled
service_description DF-ROOT
hostgroup_name DF-ROOT
#check_command check_collectd\
#!df/df-root!free!601000000:!301000000:
check_command check_collectd_percentage\
!df/df-root!used!free!20:!10:
}
define hostgroup{
hostgroup_name DF-ROOT
hostgroup_members COLLECTD
}
further links
more examples: lefants config templates in git
to compile cnagios / collectd
sudo aptitude install lex yacc automake autoconf \
libtool bison flex libltdl3-dev pkg-config \
libperl-dev libncurses5-dev
fixed collectd-nagios:
git clone git://git.verplant.org/collectd.git
git checkout 953bd0f881faa40c415a1f1a9d7e2da739d343ff
#or just use latest
further links (2)
my puny percentage patch:
playing with initial version of openvz monitoring via perl plugin:
final notes
know-how for this talk was in part sponsored by RevDev my current employer
questions?
i have created debian backports to etch of current versions of mpd, rtorrent and mt-daapd and the dependencies needed to build / install them.
add
deb http://lefant.net/debian/ etch-backports main
to your /etc/apt/sources.list in case you are interested.
mt-daapd and rhythmbox are a great pair to store music on one computer and play on another, with little configuration on the server and none on the client, by the magic of zeroconf! highly recommended. should also work with itunes and other stuff from apple.
2007-07-22
for some time now i have been using f-spot (website: http://f-spot.org/, which is a nice photo organization software for gnome. above all f-spot has great support for tagging, which in my opinion is a very important feature. you can also automatically create a static html thumbnail gallery for your website or export to flickr or gallery (the php thing many people seem to be using). however this way either you loose your tags (static html, gallery) or you handover your pictures and control over the url to flickr (which limits you to 200 pictures in their free plan anyway).
phpfspot (website: http://oss.netshadow.at/oss/phpfspot/Project, freshmeat: http://freshmeat.net/projects/phpfspot/) to the rescue!
after some whining on my part at work my colleague at work andreas unterkircher started looking for a better webfrontend solution (foremost including good support for the tags) himself and, finding none, started coding. for reference there is pennave with a similar goal (website: [http://pennave.sourceforge.net/](http://pennave.sourceforge. net/)), however speed was really lacking and development very slow).
i am now happily running phpfspot myself (link: http://gallery.lefant.net/). i also use the thumbnail export feature to create thumbnail galleries for use in the debienna wiki (link: http://debienna.at/). the thumbnails on the starting page are created dynamically for each page visit (try reloading, see http://debienna.at/?action=raw for the page source and the ?RandomQuote hack) which uses the FotoFortunes wiki page as its source (warning, huge page). using phpfspots export feature i can now create the content of the ?FotoFortunes page automatically after selecting all pictures with the debienna tag.
the same works with literal html for blog entries like this one. find a thumbnail gallery of all my images tagged with "screens" below:
i am happy, thanks unki!
welcome to the home of LeShaper script...
since wondershaper only almost did what i wanted and sometimes pings were slow when they shouldn't have been and i couldn't figure out why. i thus followed the "keep it simple stupid" principle, use tbf and prio and created my own version of a "slow down the uplink so the queue is local, always prioritise ssh/dns/fill-in-your-favourite-kind-of-nework-traffic, but give all idle bandwith to whatever can make use of it"-bandwith shaper.
i hope it may also save someone else some trouble. darcs based version control is easy, so why not use it. questions and comments welcome.
darcs repository: darcs repository of leshaper
via darcsweb webfrontend: darcsweb view of darcs repository of leshaper
version of may 2007 inline:
#!/bin/sh
. /etc/rc.conf
# leshaper, based on the fabulous wondershaper:
# Set the following values to somewhat less than your actual download
# and uplink speed. In kilobits. Also set the device that is to be shaped.
DOWNLINK=4000
UPLINK=500
DEV=ppp0
case $1 in
autostart)
test x"${leshaper:-NO}" = x"NO" && exit 0
exec $0 start
;;
start)
########## uplink ###############
# shape the root at UPLINK speed to keep the queue local no matter what
tc qdisc add dev $DEV root handle 1: tbf rate ${UPLINK}kbit burst 5k latency 50ms mpu 64b
# prio band on top of that (automagically prioritises interactive traffic according to TOS bits)
tc qdisc add dev $DEV parent 1: handle 11 prio
tc qdisc add dev $DEV parent 11:1 handle 111: sfq perturb 10
tc qdisc add dev $DEV parent 11:2 handle 112: sfq perturb 10
tc qdisc add dev $DEV parent 11:3 handle 113: sfq perturb 10
# prioritize small packets (<64 bytes) into first class
tc filter add dev $DEV parent 11:0 protocol ip prio 1 u32 \
match ip protocol 6 0xff \
match u8 0x05 0x0f at 0 \
match u16 0x0000 0xffc0 at 2 \
flowid 11:1
# higher prio for voip
tc filter add dev $DEV parent 11:0 protocol ip prio 2 u32 match ip src 172.23.1.29/32 flowid 11:1
tc filter add dev $DEV parent 11:0 protocol ip prio 2 u32 match ip dport 4569 0xffff flowid 11:1
tc filter add dev $DEV parent 11:0 protocol ip prio 2 u32 match ip sport 4569 0xffff flowid 11:1
tc filter add dev $DEV parent 11:0 protocol ip prio 2 u32 match ip sport 5004 0xffff flowid 11:1
########## downlink #############
# slow downloads down to somewhat less than the real speed to prevent
# queuing at our ISP. Tune to see how high you can set it.
# ISPs tend to have *huge* queues to make sure big downloads are fast
#
# attach ingress policer:
tc qdisc add dev $DEV handle ffff: ingress
# filter *everything* (0.0.0.0/0), drop everything that's
# coming in too fast:
tc filter add dev $DEV parent ffff: protocol ip prio 50 u32 match ip src \
0.0.0.0/0 police rate ${DOWNLINK}kbit burst 10k drop flowid :1
;;
stop)
# clean existing down- and uplink qdiscs, hide errors
#tc qdisc del dev $DEV root 2> /dev/null > /dev/null
#tc qdisc del dev $DEV ingress 2> /dev/null > /dev/null
tc qdisc del dev $DEV root
tc qdisc del dev $DEV ingress
;;
restart)
$0 stop
$0 start
;;
status)
tc -s qdisc ls dev $DEV
tc -s class ls dev $DEV
;;
*)
echo "Usage: $0 {start | stop | restart}"
;;
esac
exit $?