Math Is Fun Forum
  Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ -¹ ² ³ °

You are not logged in.

#1 2007-11-26 12:34:43

Ricky
Moderator
Registered: 2005-12-04
Posts: 3,791

Reversi

I wish to suggest a joint programming exercise.  The task is to create an AI for the game Reversi based somewhat upon a min-max algorithm.  The coding will be done in C++.  However, there will be a few twists.  Before I get into great detail, I want to hear about how many people would be interested.  Much of the work will be design, so if you don't know C++ but do understand coding, you're more than welcome.


"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."

Offline

#2 2007-11-26 12:46:02

MathsIsFun
Administrator
Registered: 2005-01-21
Posts: 7,534

Re: Reversi

I could use it in my version of Reversi.

Could you make the project "go" (http://en.wikipedia.org/wiki/Go_%28board_game%29) ... that is a much greater challenge! And I could then make a flash version for the website.


"The physicists defer only to mathematicians, and the mathematicians defer only to God ..."  - Leon M. Lederman

Offline

#3 2007-11-26 22:29:56

luca-deltodesco
Member
Registered: 2006-05-05
Posts: 1,470

Re: Reversi

I would be very interested. Im' a good programmer, but i havn't had much experiance with AI so this could be a good experiance for me.


The Beginning Of All Things To End.
The End Of All Things To Come.

Offline

#4 2007-11-27 05:24:50

esatpllana
Member
Registered: 2007-11-22
Posts: 12

Re: Reversi

this i great game can I contribute with Visual Basic .NET 2005 to prorgam it can anyone help with this bye


live your day
Mitrovica My City
tenth a class

Offline

#5 2007-11-27 07:04:47

bossk171
Member
Registered: 2007-07-16
Posts: 301

Re: Reversi

I'm not very good with C++, but I'd love to contribute any Ideas I can.


There are 10 types of people in the world, those who understand binary, those who don't, and those who can use induction.

Offline

#6 2007-11-27 09:04:50

TheDude
Member
Registered: 2007-10-23
Posts: 361

Re: Reversi

I'd be interested


Wrap it in bacon

Offline

#7 2007-11-27 10:16:03

mikau
Member
Registered: 2005-08-22
Posts: 1,504

Re: Reversi

I'm interested but I have finals coming up and lots of studying to do. I'd be willing to help wherever I can but I'm not sure how much assistance I can provide.


A logarithm is just a misspelled algorithm.

Offline

#8 2007-11-27 10:51:12

Ricky
Moderator
Registered: 2005-12-04
Posts: 3,791

Re: Reversi

I would like to do something, but upon deeper thought, Reversi is probably not the thing to do it on.  Min-max algorithm would really be almost trivial.

What I am looking for now is a large scale project that is mathematically related.  Something that will emphasize design principles would be best.  Suggestions are welcome. 

An idea is a combinatorics library, however I'm not certain what could go in there.  The reason I had this idea was a function I wrote which was a bijection between the integers modulo n! and the permutations of n objects.  This made it very easy to loop through all possible permutations of an array, making brute force combinatorics programing much simpler.


"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."

Offline

#9 2007-11-27 14:38:32

MathsIsFun
Administrator
Registered: 2005-01-21
Posts: 7,534

Re: Reversi

Sure ... Reversi is trivial because my version can do it smile

But an AI for "Go" is not trivial. From the Wikipedia article "Go poses a daunting challenge to computer programmers. While the strongest computer chess software has defeated top players (Deep Blue beat the world champion in 1997), the best Go programs only manage to reach an average amateur level."


"The physicists defer only to mathematicians, and the mathematicians defer only to God ..."  - Leon M. Lederman

Offline

#10 2007-11-28 01:05:12

mathsyperson
Moderator
Registered: 2005-06-22
Posts: 4,900

Re: Reversi

I'm not anywhere near being an expert, but that could possibly be because Chess AI has been given a lot more attention?

I'm at an amateurish level at both games, and I don't see what would make Go intrinsically harder to program an AI for.


Why did the vector cross the road?
It wanted to be normal.

Offline

#11 2007-11-28 01:44:54

NullRoot
Member
Registered: 2007-11-19
Posts: 162

Re: Reversi

I'd look forward to the challenge of designing a Go engine. I, like esatpllana, use VB, but I'd be willing to contribute to the design ideas. Might even be an excuse to finally learn C++.

I think one of the problems with Go is the fairly loose restriction on movement and the sheer size of the board. 19x19 is a lot of moves and sub-moves (and sub-sub-moves) to evaluate.


Trillian: Five to one against and falling. Four to one against and falling… Three to one, two, one. Probability factor of one to one. We have normality. I repeat, we have normality. Anything you still can’t cope with is therefore your own problem.

Offline

#12 2007-11-28 03:17:44

mikau
Member
Registered: 2005-08-22
Posts: 1,504

Re: Reversi

19x19 is a lot of moves and sub-moves (and sub-sub-moves) to evaluate.

ALL HAIL RECURSION!


A logarithm is just a misspelled algorithm.

Offline

#13 2007-11-28 09:02:56

mikau
Member
Registered: 2005-08-22
Posts: 1,504

Re: Reversi

this is kind of a different idea, but it might be interesting to have some sort of a contest. A virtual robot contest of some sort. Say we for instance, have a playing field, and each participant has a robot which have to accomplish some goal such as capturing a ball and bringing it back to your corner. Each robot is able to access the same amount of parameters from the environment as the others, what differs is how the robot handles the data and responds. Each participant submits the source code for their robot, and then we see how they compete!

You could do this by creating an abstract class Robot that contains a given set of accessors methods to gather information about their environment. All other info of the environment is hidden. Thus in the implementation of the abstract class you have to use only what information you can glean from your accessors methods. So each person would basically submit an implementation of the class Robot, and a mediator would combine and execute them.

Just an idea.


A logarithm is just a misspelled algorithm.

Offline

#14 2007-11-28 09:45:27

luca-deltodesco
Member
Registered: 2006-05-05
Posts: 1,470

Re: Reversi

We did something similar to that in the newgrounds flash forum a while back, only it was a robot wars thing.

we had a set of methods accesible to each robot that it could use to move, to detect opponnents and the obstacles and to fire its weapons etc, and the winner of each round went forward to a final battle between the robots tongue


The Beginning Of All Things To End.
The End Of All Things To Come.

Offline

#15 2007-11-28 12:07:19

mikau
Member
Registered: 2005-08-22
Posts: 1,504

Re: Reversi

so the idea would work then.

something you'd probably have to do though is multi-threading so each robot is given the same amount of time to work. Otherwise, the robot that takes the most time is likely to be the winner.


A logarithm is just a misspelled algorithm.

Offline

#16 2007-11-29 10:23:22

Ricky
Moderator
Registered: 2005-12-04
Posts: 3,791

Re: Reversi

I want to move away from AI.  The main reason for this is that AI is a complex field which thouseands of people have dedicated their lives toward researching.  We, amatures, have no hope of doing anything "new", unless someone gets really creative.  I don't see too much of a chance of that happening.

However, we can produce utilities that are useful.  So here is an idea.  When you use php in relation with a database to store content for generated web pages, it is very often to want web interfaces for maintaining this data.  This makes it so that anyone not familiar with databases/php can update the content with ease and no risk of dropping a table.  However, writing these html/php/javascript forms out by hand would be quite tedious.  We can create a program, which given a relation schema, will automatically generate said forms which allow users to insert, update, and remove tuples (rows).

Here is the general idea for such an application:

Enter in the domain of the database, username, and password.
Program looks at the database schema, determines all the tables, and lets the user select which tables to generate forms for.
User selects options on the creation of the forms, for example perhaps a field is to be left out (such as id).
When running the program, the html form will be spit out, as well as corresponding php code which will connect to and modify the database.  Also, javascript code will be generated which checks the html form for virtually all possible errors.

For people who don't know anything about server side scripts (PHP) or relations database management systmes (MySQL) I can provide assistance for getting you into it.  I would like to ask that you know at least one higher level programming language (Fortran, C, C++, Java, Python, Perl, etc), otherwise I think this would be too much to handle.

What I really like about this project is that it is (a) useful (especially to me tongue), (b) Invovles mutliple languages (Java, PHP, MySQL, HTML, possibly CSS, Javascript) and (c) can be subdivided into parts which will be great for team programming.  It is also a large enough project in which design can be emphasized.

But I'm not set on having this be the project.  I want to hear from everyone what they think about it and suggestions for other projects.  And if you really want to do AI, please speak up (because I really don't).


"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."

Offline

#17 2007-11-29 10:59:59

luca-deltodesco
Member
Registered: 2006-05-05
Posts: 1,470

Re: Reversi

Since this is a maths website, why don't we do something maths orientated in a programming project?


The Beginning Of All Things To End.
The End Of All Things To Come.

Offline

#18 2007-11-29 11:20:12

Ricky
Moderator
Registered: 2005-12-04
Posts: 3,791

Re: Reversi

Sure luca.  Got a suggestion? 

A graph theory library would be interesting.  It would include functions to construct, display, and traverse graphs.  It could be made to handle graphs, mutligraphs, directed graphs, weighted graphs, weighted directed graphs, trees, forests, and many more.  It would include algorithms to find minimal spanning trees, Euler paths/circuits, Hamiltonian paths/circuits, bridges, etc.  And additional requirement could be to design a file format which would handle input into the engine.  For example, Prufer's Algorithm could be used for trees.  There is a ton of different variations on graph, and it would require research to find out what exactly we want to include.  It would also be very expandable, and great for design and multiple people working on it.


"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."

Offline

#19 2007-11-29 20:32:47

luca-deltodesco
Member
Registered: 2006-05-05
Posts: 1,470

Re: Reversi

That sounds good.

Although to display, is that not something that is more GUI specific? Or do you simply mean supply a list of vertices and lines to be drawn by whatever GUI the user is using? Unless perhaps we create our own GUI to go with it, a little program where the library is used where people can graphically construct graphs and use the libraries methods aswell as having the library seperate? I've had little experiance with creating GUI's (which you've probably realised from all my examples in C++ etc where there was very little user interface at all tongue except for things like moving a camera around in space with keyboard and mouse tongue ) so that would be nice aswell

Last edited by luca-deltodesco (2007-11-29 20:33:30)


The Beginning Of All Things To End.
The End Of All Things To Come.

Offline

#20 2007-11-30 03:23:03

Ricky
Moderator
Registered: 2005-12-04
Posts: 3,791

Re: Reversi

I think it would be best if it were GUI, which would probably mean Java.  And just a reminder to the rest of you, other opinions would be nice.


"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."

Offline

#21 2007-11-30 03:27:16

luca-deltodesco
Member
Registered: 2006-05-05
Posts: 1,470

Re: Reversi

C++ > Java


The Beginning Of All Things To End.
The End Of All Things To Come.

Offline

#22 2007-11-30 05:36:34

Ricky
Moderator
Registered: 2005-12-04
Posts: 3,791

Re: Reversi

When it comes to coding style, I agree.  However Java has a built in graphics library which is platform independent.  C++ can't even begin to compare with that.  And since I'm on a Linux box and you guys are probably on Windows, Java is the way to go.  Java also has a very impressive api, which would be helpful when doing this sort of thing.  And to top it all off, we can make this an applet so that we can put it on a web page.


"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."

Offline

#23 2007-11-30 07:58:47

mikau
Member
Registered: 2005-08-22
Posts: 1,504

Re: Reversi

I don't know any php i'm afraid, but I have messed around with Java's GUI interfaces a good bit. I know how to use labels, buttons, radio buttons, combo boxes, text fields, text areas, scroll bars, radio buttons, checkboxes, dialog boxes, etc. I'm also familiar with applets and their various draw functions. I might be able to provide some assistance there.

Last edited by mikau (2007-11-30 08:00:10)


A logarithm is just a misspelled algorithm.

Offline

#24 2007-11-30 09:06:51

Ricky
Moderator
Registered: 2005-12-04
Posts: 3,791

Re: Reversi

mikau, you replied on how much you can do, but not on which project you like, or if you don't like either.  If you don't know an element of the project, then it is perhaps motivation for you to learn it through experience.  I'm not concerned with having people knowledgeable on what we use, only that the people involved have some programming experience.


"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."

Offline

#25 2007-11-30 09:18:41

mikau
Member
Registered: 2005-08-22
Posts: 1,504

Re: Reversi

Well frankly I'm just interested in participating in some sort of project and contributing whatever I can. Thats rewarding in itself. So I'm more or less indifferent as to what we do so long as its not over my head or dealing too much with something i know nothing about.

Last edited by mikau (2007-11-30 09:19:09)


A logarithm is just a misspelled algorithm.

Offline

Board footer

Powered by FluxBB