Archive for November 2009

Battleship AI contest on Stack Overflow

Recently there was a contest running on Stack Overflow to design the best Battleship AI. Here is a link to the page:

What is the best Battleship AI?

I must admit that I am still smarting over this contest, as my BP7 contest entry did awesomely well and incredibly poor at the same time. Here is the code:

namespace Battleship
{
    using System;
    using System.Collections.Generic;
    using System.Drawing;
    using System.Linq;
 
    public class BP7 : IBattleshipOpponent
    {
        public string Name { get { return "BP7"; } }
        public Version Version { get { return this.version; } }
 
        Random rand = new Random();
        Version version = new Version(0, 7);
        Size gameSize;
        List<Point> scanShots;
        List<NextShot> nextShots;
        int wins, losses;
        int totalWins = 0;
        int totalLosses = 0;
        int maxWins = 0;
        int maxLosses = 0;
        int matchWins = 0;
        int matchLosses = 0;
 
        public enum Direction { VERTICAL = -1, UNKNOWN = 0, HORIZONTAL = 1 };
        Direction hitDirection, lastShotDirection;
 
        enum ShotResult { UNKNOWN, MISS, HIT };
        ShotResult[,] board;
 
        public struct NextShot
        {
            public Point point;
            public Direction direction;
            public NextShot(Point p, Direction d)
            {
                point = p;
                direction = d;
            }
        }
 
        public struct ScanShot
        {
            public Point point;
            public int openSpaces;
            public ScanShot(Point p, int o)
            {
                point = p;
                openSpaces = o;
            }
        }
 
        public void NewGame(Size size, TimeSpan timeSpan)
        {
            this.gameSize = size;
            scanShots = new List<Point>();
            nextShots = new List<NextShot>();
            fillScanShots();
            hitDirection = Direction.UNKNOWN;
            board = new ShotResult[size.Width, size.Height];
        }
 
        private void fillScanShots()
        {
            int x;
            for (x = 0; x < gameSize.Width - 1; x++)
            {
                scanShots.Add(new Point(x, x));
            }
 
            if (gameSize.Width == 10)
            {
                for (x = 0; x < 3; x++)
                {
                    scanShots.Add(new Point(9 - x, x));
                    scanShots.Add(new Point(x, 9 - x));
                }
            }
        }
 
        public void PlaceShips(System.Collections.ObjectModel.ReadOnlyCollection<Ship> ships)
        {
            foreach (Ship s in ships)
            {
                s.Place(
                    new Point(
                        rand.Next(this.gameSize.Width),
                        rand.Next(this.gameSize.Height)),
                    (ShipOrientation)rand.Next(2));
            }
        }
 
        public Point GetShot()
        {
            Point shot;
 
            if (this.nextShots.Count > 0)
            {
                if (hitDirection != Direction.UNKNOWN)
                {
                    if (hitDirection == Direction.HORIZONTAL)
                    {
                        this.nextShots = this.nextShots.OrderByDescending(x => x.direction).ToList();
                    }
                    else
                    {
                        this.nextShots = this.nextShots.OrderBy(x => x.direction).ToList();
                    }
                }
 
                shot = this.nextShots.First().point;
                lastShotDirection = this.nextShots.First().direction;
                this.nextShots.RemoveAt(0);
                return shot;
            }
 
            List<ScanShot> scanShots = new List<ScanShot>();
            for (int x = 0; x < gameSize.Width; x++)
            {
                for (int y = 0; y < gameSize.Height; y++)
                {
                    if (board[x, y] == ShotResult.UNKNOWN)
                    {
                        scanShots.Add(new ScanShot(new Point(x, y), OpenSpaces(x, y)));
                    }
                }
            }
            scanShots = scanShots.OrderByDescending(x => x.openSpaces).ToList();
            int maxOpenSpaces = scanShots.FirstOrDefault().openSpaces;
 
            List<ScanShot> scanShots2 = new List<ScanShot>();
            scanShots2 = scanShots.Where(x => x.openSpaces == maxOpenSpaces).ToList();
            shot = scanShots2[rand.Next(scanShots2.Count())].point;
 
            return shot;
        }
 
        int OpenSpaces(int x, int y)
        {
            int ctr = 0;
            Point p;
 
            // spaces to the left
            p = new Point(x - 1, y);
            while (p.X >= 0 && board[p.X, p.Y] == ShotResult.UNKNOWN)
            {
                ctr++;
                p.X--;
            }
 
            // spaces to the right
            p = new Point(x + 1, y);
            while (p.X < gameSize.Width && board[p.X, p.Y] == ShotResult.UNKNOWN)
            {
                ctr++;
                p.X++;
            }
 
            // spaces to the top
            p = new Point(x, y - 1);
            while (p.Y >= 0 && board[p.X, p.Y] == ShotResult.UNKNOWN)
            {
                ctr++;
                p.Y--;
            }
 
            // spaces to the bottom
            p = new Point(x, y + 1);
            while (p.Y < gameSize.Height && board[p.X, p.Y] == ShotResult.UNKNOWN)
            {
                ctr++;
                p.Y++;
            }
 
            return ctr;
        }
 
        public void NewMatch(string opponenet)
        {
            wins = 0;
            losses = 0;
        }
 
        public void OpponentShot(Point shot) { }
 
        public void ShotHit(Point shot, bool sunk)
        {
            board[shot.X, shot.Y] = ShotResult.HIT;
 
            if (!sunk)
            {
                hitDirection = lastShotDirection;
                if (shot.X != 0)
                {
                    this.nextShots.Add(new NextShot(new Point(shot.X - 1, shot.Y), Direction.HORIZONTAL));
                }
 
                if (shot.Y != 0)
                {
                    this.nextShots.Add(new NextShot(new Point(shot.X, shot.Y - 1), Direction.VERTICAL));
                }
 
                if (shot.X != this.gameSize.Width - 1)
                {
                    this.nextShots.Add(new NextShot(new Point(shot.X + 1, shot.Y), Direction.HORIZONTAL));
                }
 
                if (shot.Y != this.gameSize.Height - 1)
                {
                    this.nextShots.Add(new NextShot(new Point(shot.X, shot.Y + 1), Direction.VERTICAL));
                }
            }
            else
            {
                hitDirection = Direction.UNKNOWN;
                this.nextShots.Clear();     // so now this works like gangbusters ?!?!?!?!?!?!?!?!?
            }
        }
 
        public void ShotMiss(Point shot)
        {
            board[shot.X, shot.Y] = ShotResult.MISS;
        }
 
        public void GameWon()
        {
            wins++;
        }
 
        public void GameLost()
        {
            losses++;
        }
 
        public void MatchOver()
        {
            if (wins > maxWins)
            {
                maxWins = wins;
            }
 
            if (losses > maxLosses)
            {
                maxLosses = losses;
            }
 
            totalWins += wins;
            totalLosses += losses;
 
            if (wins >= losses)
            {
                matchWins++;
            }
            else
            {
                matchLosses++;
            }
        }
 
        public void FinalStats()
        {
            Console.WriteLine("Games won: " + totalWins.ToString());
            Console.WriteLine("Games lost: " + totalLosses.ToString());
            Console.WriteLine("Game winning percentage: " + (totalWins * 1.0 / (totalWins + totalLosses)).ToString("P"));
            Console.WriteLine("Game losing percentage: " + (totalLosses * 1.0 / (totalWins + totalLosses)).ToString("P"));
            Console.WriteLine();
            Console.WriteLine("Matches won: " + matchWins.ToString());
            Console.WriteLine("Matches lost: " + matchLosses.ToString());
            Console.WriteLine("Match winning percentage: " + (matchWins * 1.0 / (matchWins + matchLosses)).ToString("P"));
            Console.WriteLine("Match losing percentage: " + (matchLosses * 1.0 / (matchWins + matchLosses)).ToString("P"));
            Console.WriteLine("Match games won high: " + maxWins.ToString());
            Console.WriteLine("Match games lost high: " + maxLosses.ToString());
            Console.WriteLine();
        }
    }
}

The thing I find odd about this was that against the winning entry, Dreadnought, my AI was far and away the most successful, winning about 40% of the individual games. The next closest competitor to Dreadnought was BSKiller, crafted by my compatriot in crime, John Boker, winning 20% in the initial round robin and 12% and 14% in the knockout round.

And yet, BP7 stunk against most of the other real submissions, which is a bit mysterious to me. I understand that there is some random fortune involved here (for example, in the round robin, BSKiller defeated BP7 121 games to 80, even though in my own testing, BP7 was winning about 54% of the games over BSKiller), but to be defeated at almost every turn?

Oh well. Here is my VS2008 solution and class files, if you would care to try it out for yourself:

Battleship solution

Also, when I was first looking into this problem, I created some graph paper to help me visualize certain situations. Here is the PDF file of this graph paper:

Battleship Graph Paper

Happy Thanksgiving everyone! (For those outside the U.S., Happy November 26th.)

How to get the version number of a running process

I wanted to have my .NET based Palm OS conduit DLL be able to report the version of the HotSync Manager that the user has installed on their computer. Initially, I was going to try to read the version of the executable, but then I would first have to find the path to the executable, and hope that this would be a reliable enough method.

As it turns out, after I did a little investigation, I found out that it is not necessary to try and figure out where the HotSync Manager is installed by reading the appropriate registry key to get the HotSync Manager location and then trying to get the version number of the assembly at that path. Because the user is in the conduit code, the HotSync Manager (HOTSYNC.EXE) is already in the running processes list. It just so happens that in the System.Diagnostics namespace there is a handy dandy method that gets all of the running processes, along with a goodly amount of information about each process, including the version number.

So here is my VB.NET code that searches for the HotSync Manager process and returns the version number as a string.

Function GetHotSyncVersion() As String
 
    Dim versionString As String = "Unknown"
 
    Dim procList As List(Of Process) = Process.GetProcesses().ToList
    Dim hotSyncProcess As Process = Nothing
    For Each p In procList
        If p.ProcessName.ToUpper = "HOTSYNC" Then
            hotSyncProcess = p
        End If
    Next
 
    If hotSyncProcess IsNot Nothing Then
        versionString = hotSyncProcess.MainModule.FileVersionInfo.FileVersion
    End If
 
    Return versionString
 
End Function

Sorry I missed the CIDUG meeting tonight.

Two weeks with Droid

So far, I haven’t seen really anything yet from the Droid that is going to cause me to change my 4-and-a-half star rating. Especially after I actually found the question mark key on the slide out keyboard. (It’s just to the right of the L key and just above the period key, where the semicolon key would be on a normal QWERTY or TVQUIZ keyboard.)

On the plus side of the ledger, I traveled with the phone for the first time today, and it worked flawlessly on my drive to visit the folks. The navigation application is so much superior to my trusty old Alpine Blackbird GPS that it isn’t even funny.

I am not at all impressed with the battery life, however. During the week, I don’t think that I am using it excessively, but by the time I get home from work, the freshly charged battery is down to about 30% or 40%. This would seem to indicate to me that I better not try to squeeze two days worth of usage out of it before recharging. The problem here I think is that I would like the wi-fi to be on so that I am not burning through my 5GB unlimited data plan, but it is probably draining the battery quite a bit. More experimentation with the device is called for here.

On the application front, I have only downloaded free apps so far, and there are quite a few good ones. I do like the game Jewels, a Bejeweled clone. I wish I could figure out how to use Google Sky Map, it seems to be so jittery that I can’t get it to behave long enough to try and find anything.

If anyone has any suggestions about how to maximize battery life, please let me know.

Black Friday deal

I just got an ad in my e-mail inbox from CompUSA that included this amazing deal:

email_creativeb_22

Some things are best left unsaid.

Deuces wild???

As a baseball loving youth, I remember with great fondness watching and listening to baseball as called by the voice of baseball, Vin Scully, who is unquestionably one of the greatest baseball announcers.

One thing I can always remember him saying during his calls was “deuces wild”, which he used to describe a situation that occurs with a count of 2 balls, 2 strikes, and 2 outs.

So, I figured I would take a look at the raw statistics and see how often the deuces wild situation actually came up.  Here is the code from my Program.cs file:

using System;
using System.Collections.Generic;
using System.Linq;
 
namespace RetrosheetReader
{
    class Program
    {
        static List<Team> teamList;
        static List<Player> playerList;
        static List<Event> eventList;
 
        const string DATA = "c:\\baseball_data\\";
 
        static void Main(string[] args)
        {
            Console.WriteLine("Retrosheet Reader");
            Console.WriteLine();
 
            teamList = Team.GetTeamList(DATA);
            playerList = Player.GetPlayerList(DATA);
            eventList = Event.GetEventList(DATA);
 
            Console.WriteLine("Number of teams: " + teamList.Count().ToString());
            Console.WriteLine("Number of players: " + playerList.Count().ToString());
            Console.WriteLine("Number of events: " + eventList.Count().ToString());
 
            int[, ,] pitchCount = new int[4, 3, 3];
            int balls, strikes, totalPitches;
 
            totalPitches = 0;
            foreach (var ev in eventList)
            {
                balls = 0;
                strikes = 0;
                foreach (char c in ev.pitchSequence)
                {
                    if (Functions.IsBallOrStrike(c))
                    {
                        if (balls < 0 || balls > 3)
                        {
                            Console.WriteLine("Illegal number of balls (" + balls.ToString() + ") in pitch sequence " + ev.pitchSequence);
                        }
                        else
                        {
                            pitchCount[balls, strikes, ev.outs]++;
                            totalPitches++;
                            if (Functions.IsStrike(c))
                            {
                                if (strikes == 2)
                                {
                                    if (!Functions.IsFoul(c))
                                        strikes++;
                                }
                                else
                                    strikes++;
                            }
                            else
                            {
                                balls++;
                            }
                        }
                    }
                }
            }
 
            Console.WriteLine("Total pitches: " + totalPitches.ToString());
            for (int o = 0; o < 3; o++)
                for (int s = 0; s < 3; s++)
                    for (int b = 0; b < 4; b++)
                        Console.WriteLine(String.Format("Total pitches on B{0}-S{1}-O{2}: {3,8}  ({4,6:P})", b, s, o, pitchCount[b, s, o],
                                                    pitchCount[b, s, o] * 1.0 / totalPitches));
 
            Console.WriteLine();
            Console.Write("Strike any key to end...");
            Console.ReadKey();
        }
    }
}

By the way, there is a new Functions.cs file in the project that contains utility functions, and I had to modify the Event.cs file to take into account the fact that the BEVENT application creates duplicate records for a batter if there is some kind of on-base event that happens in the middle of the at-bat, such as a stolen base or pick off.

The results? I ran the application with the 2008 season data, and found that there were 700,242 total pitches. The deuces wild situation happened on only 17,141 pitches, or 2.45%. Of course, the highest percentage occurred with 0 balls, 0 strikes, and 0 outs (the first pitch to any batters that bat in an inning before the first out is recorded, including the first batter of each inning) with 65,050 pitches, or 9.29%.

Here is the zipped up solution:

RetrosheetReader.zip

Best way to not use an enumeration, ever!

So here is some more interesting stuff found in some code that needed some emergency modifications.

The enumeration of this code starts on line 26 of the class file:

public enum City
{
    CLINTON = 78,
    FRANKLIN = 1,
    FAIRVIEW = 59,
    GREENVILLE = 55,
    SALEM = 83,
    MADISON = 81,
    SPRINGFIELD = 14,
    ARLINGTON = 84,
    CLAYTON = 63,
    GEORGETOWN = 85,
    MARION = 15,
    OXFORD = 65,
    BURLINGTON = 5
}

And instead of using the MADISON enumeration, the if statement of this code starts on line 118 of the very same class file:

if (cityID == 0x51)
{
    actual = expected - actual;
}

The names were changed to protect the innocent, thanks to Wikipedia for having an easy to find list of common place names.

Motorola Droid first impressions

It was well past the time to replace my aging, not-quite-functioning-correctly LG enV phone that I have been using for the past 3 years or so. I have been keeping an eye out for an interesting phone to upgrade to, as I wanted to stay with Verizon Wireless.

My wife and I were just about to jump ship to a rival carrier due to a significant lack of good phones offered by Verizon, when the iDon’t commercials with the happy iPod-type music debuted. Instantly entranced by the prospect of a shiny new alternative to the iPhone and Crackberry drones, we decided to take the plunge and switch to the Droid phone when it came out.

I went to my local Verizon store on the morning of November 6th, and after a wait of about an hour, my friendly sales rep Mike had set me up with 2 shiny new Android phones.

Two thumbs up, 4-and-a-half star rating

I must say that I am thoroughly impressed with the fit and finish of the phone, and especially with all of the work that has gone into the Android 2.0 operating system. They have really done a nice job of making the operating system easy to use and very functional.

Once I put in my Gmail account information, it synchronized all of the information that I have put into my Gmail contacts and calendar. I now have all of my contacts instantly on my new phone, which has all of the options that you would expect it to have (along with quite a few features that you wish you had thought of).

Among the built-in apps, I especially like the Maps application, which provides both mapping and navigation information. I have not played with the navigation much, but it appeared that you can use the navigation along with a street view layer if you want. This is very cool. (I do need to get some kind of car dock/charger for this purpose, as I can see the screen turning off as a big problem, and I’m sure the battery runs down quite quickly when using the GPS receiver along with the 3G radio.)

I do have a few negatives about the phone, these largely mirror the thoughts of some of the other reviews that I have read. This is a heavy device compared to other devices. The camera takes utterly craptastic photos indoors, even with the flash turned on. And the volume of the ringer and notifications seems a bit weak to me. (Oh, and by the way, when you use the slide out keyboard, where is the question mark character???)

But all-in-all, I give this phone 2 huge thumbs up, or a 4.5 out of 5 star rating. Good job Verizon, Motorola, and Google, you have retained me as a customer for at least another 2 years.

Bill & Ted’s Realty Company

I am guessing that the Wyld Stallyns are having trouble getting gigs, and the guys have turned to selling houses for a living…

Gnarly "For Sale" sign

Sorry, I had to do it.  (Darn, maybe I should have gone with a Wayne’s World reference instead.)

Oh, and Happy All Saints’ Day everyone!