Computer Science Canada

Looking for help with my PHP Connect Four game.
Author:  rcad [ Fri Jul 11, 2008 12:56 pm ]
Post subject:  Looking for help with my PHP Connect Four game.
Hello everyone,
I'm working on a PHP Connect Four game. I've managed to do some of the basics, but when it comes to the AI, I'm completely lost. I'm wondering if there is an efficient way to rank each of the 7 potential moves (each column) in an effective way (for example, winning the game = highest, blocking opponent's 3 in a row = second highest, moving into a space that allows the opponent to win = lowest, etc). Does anybody know of a good way to detect this sort of thing? The game board is stored in a string with 42 numbers separated by commas so that it may easily be stored in a MySQL database. I've already written a few functions, enough to play out the first few moves. I don't have a win detection function yet, so I need to write one of those. (I think splitting the board into all the possible 4x columns, rows, and diagonals would work, and then scanning for $value . $value . $value . $value in that string could work, with $value being the color (1 being user, 2 being computer).

code:
<?php
        // Author's Notes
        // Connect Four PHP script written by services@rcadble.net
        // 1 represents user move, 2 represents computer move

        // MySQL Settings
        $mysql_server = 'localhost';       // MySQL server IP
        $mysql_user = 'root';       // MySQL username with appropriate permissions
        $mysql_password = '';       // MySQL username's password
        $mysql_database = 'connectfour';        // Database where the data is be stored.
        $conn = mysql_connect($mysql_server, $mysql_user, $mysql_password) or dieError(mysql_error());
        $db     = mysql_select_db($mysql_database, $conn) or dieError(mysql_error());
       
        // Session Settings
        session_start();
       
        // Functions
        function setPiece($boardString, $column, $value) {
                $values = explode(", ", $boardString);
                $row = 5 - colFillCount($boardString, $column);
                $pieceindex = ($row * 7) + $column;
                $values[$pieceindex] = $value;
                return implode(", ", $values);
        }
        function colFillCount($boardString, $column) {
                $values = explode(", ", $boardString);
                $counter = 0;
                $fillcount = 0;
                foreach ($values AS $value) {
                        if ($counter==$column) {
                                if ($value!=0) {
                                        $fillcount++;
                                }
                        }
                        $counter++;
                        if ($counter==7) {
                                $counter = 0;
                        }
                }
                return $fillcount;
        }
        function colFilled($boardString, $column) {
                $values = explode(", ", $boardString);
                $counter = 0;
                foreach ($values AS $value) {
                        if ($counter==$column) {
                                if ($value==0) {
                                        return false;
                                }
                        }
                        $counter++;
                        if ($counter==7) {
                                $counter = 0;
                        }
                }
                return true;
        }
        function drawBoard($boardString) {
                $values = explode(", ", $boardString);
                $return_html = '<table width="700" border="3" cellspacing="0" cellpadding="0" bordercolor="#0000FF">';
                $counter = 0;
                for ($i = 0; $i<=6; $i++) {
                        $filled[$i] = colFilled($boardString, $i);
                }
                foreach ($values AS $value) {
                        if ($counter==0) {
                                $return_html .= '<tr>';
                        }
                        if ($filled[$counter]==true) {
                                if ($value==0) {
                                        $return_html .= '<td height="100" width="100"><img src="images/empty.png"></td>';
                                } elseif ($value==1) {
                                        $return_html .= '<td height="100" width="100" background="images/empty.png"><img src="images/player.png"></td>';
                                } elseif ($value==2) {
                                        $return_html .= '<td height="100" width="100" background="images/empty.png"><img src="images/computer.png"></td>';
                                }
                        } else {
                                if ($value==0) {
                                        $return_html .= '<td height="100" width="100"><a href="?col=' . $counter . '"><img src="images/empty.png" style="border-style: none"></a></td>';
                                } elseif ($value==1) {
                                        $return_html .= '<td height="100" width="100" background="images/empty.png"><a href="?col=' . $counter . '"><img src="images/player.png" style="border-style: none"></a></td>';
                                } elseif ($value==2) {
                                        $return_html .= '<td height="100" width="100" background="images/empty.png"><a href="?col=' . $counter . '"><img src="images/computer.png" style="border-style: none"></a></td>';
                                }
                        }
                        $counter++;
                        if ($counter==7) {
                                $return_html .= '</tr>';
                                $counter = 0;
                        }
                }
                $return_html .= '</table>';
                return $return_html;
        }
        function dieError($mysql_error) {
                die("<b>A MySQL error has occurred!</b><br>" . $mysql_error);
        }
       
        // Script Actions
        $result = mysql_query("SELECT * FROM `games` WHERE `session_id` = '" . session_id() . "' AND `winner` = '0' LIMIT 1;", $conn) or dieError(mysql_error());
        if (mysql_num_rows($result)==1) {
                $row = mysql_fetch_array($result);
                $_SESSION['game_ID'] = $row['id'];
        }
        $result = mysql_query("SELECT * FROM `games` WHERE `session_id` = '" . session_id() . "' AND `id` = '" . $_SESSION['game_ID'] . "' LIMIT 1;", $conn) or dieError(mysql_error());
        if (mysql_num_rows($result)!=1) {
                $_SESSION['game_ID'] = '';
        }
        if ($_SESSION['game_ID']==''&&$_POST['act']!='newgame') {
                $content = '<b>Connect Four</b> by services@rcadble.net.<br>You are not currently in a game.<br><br><form action="" method="POST"><input type="hidden" name="act" value="newgame"><input type="submit" value="Start a New Game!"></form>';
        } elseif ($_SESSION['game_ID']==''&&$_POST['act']=='newgame') {
                $emptyboard = '0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0';
                $result = mysql_query("INSERT INTO `games` (`id`, `winner`, `moves`, `session_id`, `umcount`) VALUES (NULL, '0', '$emptyboard', '" . session_id() . "', '0');", $conn) or dieError(mysql_error());
                $result = mysql_query("SELECT * FROM `games` WHERE `session_id` = '" . session_id() . "' LIMIT 1;", $conn)  or dieError(mysql_error());
                $row = mysql_fetch_array($result);
                $_SESSION['game_ID'] = $row['id'];
                $content = drawBoard($emptyboard);
        } else {
                $result = mysql_query("SELECT * FROM `games` WHERE `session_id` = '" . session_id() . "' AND `id` = '" . $_SESSION['game_ID'] . "' LIMIT 1;", $conn) or dieError(mysql_error());
                $row = mysql_fetch_array($result);
                $column = $_GET['col'];
                if ($column<0||$column>6) {
                        $content = drawBoard($row['moves']);
                } else {
                        $board = setPiece($row['moves'], $column, 1);
                        $umcount = $row['umcount'] + 1;
                        if ($umcount==1) {
                                $board = setPiece($board, 3, 2);
                        } elseif ($umcount==2) {
                                $board = setPiece($board, 3, 2);
                        } elseif ($umcount==3) {
                                $colsafe = checkVertThree($board, 1);
                                if($colsafe!=-1) {
                                        $board = setPiece($board, $colsafe, 2);
                                } else {
                                        $board = setPiece($board, 3, 2);
                                }
                        } else {
                                $weight[0] =
                                $weight[1] =
                                $weight[2] =
                                $weight[3] =
                                $weight[4] =
                                $weight[5] =
                                $weight[6] =
                               
                        }
                        $result = mysql_query("UPDATE `games` SET `moves` = '" . $board . "' WHERE `id` = " . $row['id'] . " LIMIT 1", $conn) or dieError(mysql_error());
                        $result = mysql_query("UPDATE `games` SET `umcount` = '" . $umcount . "' WHERE `id` = " . $row['id'] . " LIMIT 1", $conn) or dieError(mysql_error());
                        $content = drawBoard($board);
                }
        }
       
        //Script Output
        echo '<center><br>' . $content . '</center>';
       
?>


Ignore my nubbiness please, I taught myself how to program. Any help will be greatly appreciated.
Author:  jernst [ Fri Jul 11, 2008 1:05 pm ]
Post subject:  Re: Looking for help with my PHP Connect Four game.
one way of doing it is letting the computer simulate every combination of every move into the future and then giving it a rank of 1 or -1 if it was a win or loss. Then it adds up the total for every move it made and picks the highest one for its next move. In most games this is unrealistic though, so you could have it play ahead to a certain "depth" and assign a value of 0 or something if it doesnt reach the end of the game by that depth. If it still can't figure out a move then you could have it make a random move, and as it gets closer to a win or loss it will be able to reach some end points eventually. To change the difficulty then all you would have to do is change the depth. You could also play around with something other than a random move as well.
Author:  Zeroth [ Fri Jul 11, 2008 10:01 pm ]
Post subject:  Re: Looking for help with my PHP Connect Four game.
I'd just want to caution against simulation to winning. In most cases that can become a huge amount of moves to explore. My professor does machine learning research, so here's a bit of knowledge. If you create a tree of possible moves, even half-way into the connect-4 game its still hundreds of branches wide, several layers deep. This can be extremely taxing to explore, especially in a language like PHP which is not designed for efficient processing of scads of data.

What can be done, and this has been shown to reduce an NP complete problem(like the connect 4 game) into a more manageable k*f(n) function. Instead of being O(n^5) or so, it is instead, O(k*O(f(n))) So, based on the derivative function f, which takes advantage of the reduction by k, to perform very speedily. One method, is to essentially randomly color the tree or graph. You want a path of say, 10 moves ahead, then you color the tree with 9 colors. When you find a path is this colored tree that has all unique colors, that path is shown to be a simple path, ie, a path of least complexity from point A, to wherever it ends up. Because there are only so many unique colorings of a tree, that forms the k value of the new algorithm. Exploring each of these colorings, it becomes simple to find all the simple paths from point A, to a chosen point B. By analyzing a few simple paths, you can quickly find local optimum moves. As well, it should be noted that using this method, and cycling through every possible coloring of the graph/tree will deliver every single simple path in the graph, indicating every shortest path from point A, to point B. This only works however, if you know how long of a path you want. In cases like the travelling salesman, testing a range of path lengths quickly grows it into exponential time again.

Locally optimum moves are moves that are the best move right now, but are not guaranteed to be the best move for the entire game. Typically, however, they do provide a much higher chance of winning, that picking random moves.

So, how do you analyze a sequence of moves?

First, you need a function that can infer intent, or mark threats, ie, possible lines. Given a grid, one of the best ways is what you stated, is divide it up into all the possible rows, columns, and diagonals. Then, looking at each of these, look at the rate of a color. Ie, a diagonal that has [red, red, blank, red] is a low-level threat. This will be delivered for more analysis. In that case, you would need to check the space directly below the blank. If it has a piece, then the low-level threat becomes a high level-threat. Otherwise, the AI "marks" that spot for watching, as well as to avoid putting a piece there. And so on for the variety of situations.

Given this information, the AI can then place the moves in, and see how it scores with stopping or avoiding threats. Then, it picks the sequence with the lowest advantage to the player. Every couple of moves, it recalculates the optimum paths.

I hope that helps! I know its a lot of information, but this AI stuff is fun. For me. And useful.

:


You can syndicate this boards posts using the file backend.php or view the topic map using sitemap.php.

Terms of Use | Privacy Policy