Battleship AI Algorithm Using Dynamic Programming


(image via Wikimedia)

My boys and I enjoy playing a mobile version of the classic battleship game when we are waiting our turn at the barbershop. However, the artificial intelligence algorithm this specific game uses is so feeble that even my youngest son can consistently beat the computer player. So, I started thinking about improving the algorithm. I searched the web to see if there was already an established, dominant algorithm. Although I found several clever implementations, including one that used probabilities and another based upon a checkerboard pattern, I did not find one that I particularly enjoyed. After thinking about the problem further I came to the conclusion that this problem would be well suited for a dynamic programming algorithm.

From my perspective, the best approach to take when searching for the opponent’s ship is to target a square that is in the center of the longest line of unmarked squares. It would be even better to find a target which is at the intersection of two long lines of unchecked squares. To me, this is an effective divide and conquer approach similar in spirit to the concept of binary trees, the problem is finding an efficient algorithm. The problem seems to lend itself perfectly to the dynamic programming approach.


ABAP Way of Replacing Internal String Spaces

Replacing characters in a string is a simple programming task which should be ridiculously easy, right? It turns out that is not always the case, especially if you have to write SAP ABAP code. Let us assume that there is a variable with a base type of CHAR30 (a string of 30 characters) which needs to have its internal spaces replaced with hyphens. In theory the following statement should work.

DATA: lv_char30 TYPE char30.
lv_char30 = 'AAAA BBBB CCC'.
REPLACE ALL OCCURRENCES OF ' ' IN lv_char30 WITH '-'.

Example SAP ABAP Program

SAP ABAP is a difficult programming language to learn; not only is it old and clunky, but there are also huge barriers to access the only programming environment available for it. To write ABAP programs you have to have a complete and working SAP system, and even professionally managed development systems are difficult to program on due to the lack of data in the systems. I think that this at least partially contributes to the lack of good online reference material. I know that it is possible search the SAP help forums, but the code there often looks like an giant glob of unformatted nonsense. Since I do not have time right now to create a decent site which can explain ABAP to people, I thought I would simply share an example program which shows many ABAP program/report programming techniques all in one spot.

This program should work exactly as it is, the GUI texts would have to be filled in using the development environment of course. Normally a program of this size would be broken into smaller files, and those demarcations are show in the embedded comments. If you read through this program and find something that could or should be handled in a better way, then please let me know.

Thoughts on String Guessing Algorithms

I recently proposed that an email address be simplified in order to improve the user experience, and I used mathematics to justify the idea. I proposed to replace the email address it-support-xyz-na@company.com with help@company.com. Ignoring the common ending, the chance of randomly discovering the first email address is 1 in 1,133,827,315,385,150,000,000,000 (2617 or 1.13 septillion), which means that you have a better chance of winning the super-lotto multiple times. With those odds it would make a better password than it does a customer service email address. The chance of randomly discovering the email address that I suggested is 1 in 456,976 (264), which seems much more sane.

As I thought about the problem it occurred to me that the chances of randomly discovering the email address that I suggested is probably better than stated above since it is a word that English speaking people already know (and readily associate with what they are looking). As far as I can tell there are less than 250,000 words in the English language, which nearly doubles the chances of discovering help@company.com. This idea made me think about string guessing algorithms and the assumptions that are made when evaluating them, specifically algorithms designed to guess passwords.

JavaScript Dynamic Programming Example

Despite its name, many programmers have never heard of dynamic programming. In all fairness, it is not really programming in that sense of the word, rather it is a mathematical method for dividing problems into smaller subproblems and then combing those parts to form an optimal solution. The “programming” portion of “dynamic programming” probably shares more in common with “television programming,” since they both involve using tables to organize data. The technique is taught in advanced computer science classes, so computer scientists and software engineers should be familiar with the technique.

Dynamic programming is a general technique which involves four basic steps: determine the structure of an optimal solution; recursively define values of the optimal solution; compute the optimal solution; and, if you need to know the optimal path in addition to the computed optimal solution value, construct the value formed by the path. The code on this page shows all of these parts, so it may help in understanding the technique.</div>


1936 Akron Rubber Strike

The world has recently experienced an economic depression the likes of which have not been seen since the Great Depression. World leaders have been struggling for over three years to keep this economic calamity from destroying social institutions and precipitating war as the last one did. Of the tools and techniques that were used in the 1930s to restore American economic prosperity there is one that has been neglected. Not only has this tool remained unused during the current depression, but it has been actively attacked. That tool is organized labor.

Like other labor movements, the American labor movement began to appear with the onset of industrialization. In its early years American labor was weak, decentralized, and probably not classifiable as a movement. It was not until the Great Depression that unionization gained the institutional acceptance that it needed to truly become a movement. However, as Americans learned with the “Nobel Experiment” of Prohibition, laws and institutional changes cannot alter society without the acceptance of the people. The 1936 Akron Rubber Strike marks the moment when the ideas of policy makers met the hands of labor and the American labor movement began its ascent.

It can be demonstrated that the 1936 Akron Rubber Strike was a pivotal event by examining the changed attitude of Goodyear’s management team. Prior to the rubber strike Goodyear felt that it had the upper hand, while afterwards management’s tone was much more conciliatory. The chronology of events will establish that this change in attitude was caused by the workers themselves and not simply foisted upon the company and its employees by “professional strike leaders” as Goodyear’s president at the time asserted.1